TopCoder

Thumb
1.6449
Rolling in the DeeP?

User's AC Ratio

87.5% (7/8)

Submission's AC Ratio

25.0% (12/48)

Description

你有聽過Massacre at Camp Happy這個遊戲嗎?

有一個很快樂的營隊,叫做快樂營。快樂營的參與者都十分快樂,他們絲毫不知道接下來會變成一盤盤人肉沙西米。

因為外星生物食肉蚯登陸地球了!

食肉蚯非常喜歡吃肉,舉凡小松鼠、烏龜、黃鼠狼、小山豬都吃得很開心。

但是他很怕吃到同伴,畢竟食肉蚯在地球上十分稀少。

我們假定地球上每一種生物長相都可以用一個小寫字母字串表示。

而對兩種生物甲和乙"k-完全相同"的定義是把生物乙前k個字母"搬移"最尾端,然後兩個字串會長得一模一樣。

例如aaab和baaa就是"1-完全相同"。

可是任兩隻食肉蚯是不可能"完全相同"的。他們頂多是"幾乎相同"。

"k-幾乎相同"意即把生物乙前k個字母"搬移"最尾端時,會和生物甲恰好一個字元不一樣。

現在食肉蚯看到了一隻獵物,他知道如果獵物和他"幾乎相同"的話就表示不能吃,因為獵物應該也是食肉蚯。

當然幾乎相同也可能不只一種。

例如aaa和aab就是0-幾乎相同、1-幾乎相同、2-幾乎相同。食肉蚯想要求出所有的k使得他跟獵物"k-幾乎相同"。

如果是"完全相同"或是不同,那就吃了獵物吧。

Input Format

輸入第一行有一個正整數N,表示生物長相字串的長度(1<=N<=1,000,000)。

接下來有兩行,各包含N個字元小寫英文字母字串,表示食肉蚯的長相和獵物的長相。

Output Format

如果該生物跟食肉蚯幾乎相同,

第一行輸出一個字串"TAK"(不含雙引號,在食肉蚯語中表示"同類")、
第二行由小到大輸出許多個以空白分隔、[0, N-1]內的整數,表示所有可能的k。

反之僅輸出一行包含一個字串"NIE"(不含雙引號,在食肉蚯語中表示"吃了他!")

Sample Input

Sample Input 1:
5
ababa
aaaab

Sample Input 2:
5
ababa
bbbbb

Sample Input 3:
5
aaaab
caaaa

Sample Output

Sample Output 1:
TAK
2 4

Sample Output 2:
NIE

Sample Output 3:
TAK
4

Hints

Problem Source

原TIOJ1725 / Adapted From PA 2007 Round 6 Prawie równoważne słowa

Subtasks

For Testdata: 0 ~ 0, Score: 3
For Testdata: 1 ~ 1, Score: 3
For Testdata: 2 ~ 2, Score: 3
For Testdata: 3 ~ 3, Score: 3
For Testdata: 4 ~ 4, Score: 3
For Testdata: 5 ~ 5, Score: 3
For Testdata: 6 ~ 6, Score: 3
For Testdata: 7 ~ 7, Score: 3
For Testdata: 8 ~ 8, Score: 3
For Testdata: 9 ~ 9, Score: 3
For Testdata: 10 ~ 10, Score: 3
For Testdata: 11 ~ 11, Score: 3
For Testdata: 12 ~ 12, Score: 3
For Testdata: 13 ~ 13, Score: 3
For Testdata: 14 ~ 14, Score: 3
For Testdata: 15 ~ 15, Score: 3
For Testdata: 16 ~ 16, Score: 3
For Testdata: 17 ~ 17, Score: 3
For Testdata: 18 ~ 18, Score: 3
For Testdata: 19 ~ 19, Score: 3
For Testdata: 20 ~ 20, Score: 3
For Testdata: 21 ~ 21, Score: 3
For Testdata: 22 ~ 22, Score: 3
For Testdata: 23 ~ 23, Score: 3
For Testdata: 24 ~ 24, Score: 3
For Testdata: 25 ~ 25, Score: 3
For Testdata: 26 ~ 26, Score: 3
For Testdata: 27 ~ 27, Score: 3
For Testdata: 28 ~ 28, Score: 3
For Testdata: 29 ~ 29, Score: 3
For Testdata: 30 ~ 30, Score: 3
For Testdata: 31 ~ 31, Score: 3
For Testdata: 32 ~ 32, Score: 4
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 4000 65536 65536
1 4000 65536 65536
2 4000 65536 65536
3 4000 65536 65536
4 4000 65536 65536
5 4000 65536 65536
6 4000 65536 65536
7 4000 65536 65536
8 4000 65536 65536
9 4000 65536 65536
10 4000 65536 65536
11 4000 65536 65536
12 4000 65536 65536
13 4000 65536 65536
14 4000 65536 65536
15 4000 65536 65536
16 4000 65536 65536
17 4000 65536 65536
18 4000 65536 65536
19 4000 65536 65536
20 4000 65536 65536
21 4000 65536 65536
22 4000 65536 65536
23 4000 65536 65536
24 4000 65536 65536
25 4000 65536 65536
26 4000 65536 65536
27 4000 65536 65536
28 4000 65536 65536
29 4000 65536 65536
30 4000 65536 65536
31 4000 65536 65536
32 4000 65536 65536