|시간 제한||메모리 제한||제출||정답||맞은 사람||정답 비율|
|1 초||128 MB||0||0||0||0.000%|
Strictly thinking, the word almost is equivalent to the word no. On the other hand, these words are not exactly synonyms. More precisely, the word almost is closer in meaning to the word yes than to the word no.
We say that two words are conjugates if we can modify the first word to obtain the second one, by repeatedly moving one letter from the beginning of the first word to its end. For instance, words
abaab are conjugates, but words
baaab are not. We say that two words are almost conjugates if:
For instance, words
aaaab are almost conjugates, but words
bbbbb are not.
Write a program which:
The first line of input contains one integer n (1 ≤ n ≤ 1 000 000), representing the length of each of the words. The second line contains the first word and the third line contains the second word. Each word is a sequence of n small letters of English alphabet.
The first line of output should contain one word -
TAK (i.e. yes in Polish) if the words from the input are almost conjugates or
NIE (i.e. no in Polish) otherwise. If the first line contains the word
TAK, then the second line should contain an increasing sequence of non-negative integers, each from the range [0,n - 1], separated with single spaces. The sequence should contain all possible numbers of operations of moving one letter from the beginning of the first word to its end, after which the resulting word differs from the second word at exactly one position.
5 ababa aaaab
TAK 2 4
because after 2 repetitions of the move operation, the first word becomes abaab, after 4 repetitions - aabab.
5 ababa bbbbb