PROG0074 - Frequency of subsequences

no tags 

In the analysis of DNA sequences the initial main target is often shorter sequences that occur repeatedly within a longer sequence. Suppose we want to investigate the DNA sequence ATAGGCCTTATGCCATTAC. We want to know if a given subsequence of a maximum of 4 bases occurs at least once or twice or not at all in the longer sequence.

Input

A line containing a short DNA sequence of at least one and up to four bases long.

Output

A line containing "not", "once" or "at least twice", depending on the the frequency of the short sequence from the input within the longer DNA sequence ATAGGCCTTATGCCATTAC.

Example

Input:

TT

Output:

at least twice

Bij de analyse van DNA sequenties wordt in eerste instantie vaak gezocht naar kortere sequenties die herhaaldelijk voorkomen binnen een langere sequentie. Stel dat we de DNA sequentie ATAGGCCTTATGCCATTAC willen onderzoeken. We willen daarbij weten of een gegeven deelsequentie van maximaal 4 basen niet, eenmaal of minstens tweemaal voorkomt in de langere sequentie.

Invoer

Een regel met daarop een korte DNA sequentie van minstens één en maximaal vier basen lang.

Uitvoer

Een regel met daarop "niet", "eenmaal" of "minstens tweemaal", naargelang de frequentie van de korte sequentie uit de invoer binnen de langere DNA sequentie ATAGGCCTTATGCCATTAC.

Voorbeeld

Invoer:

TT

Uitvoer:

minstens tweemaal


Added by:Peter Dawyndt
Date:2011-08-01
Time limit:10s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:PY_NBC
Resource:None