TopCoder

icube
baluteshih 好強 <(_ _)>

User's AC Ratio

100.0% (3/3)

Submission's AC Ratio

47.1% (8/17)

Tags

Description

尋找妁艷的妤嬌一行人, 來到了木星.
太空船進入了木星大氣層.

“好懷念呀, 木星!” 妤嬌嘆道.

“什麼, 妤嬌你有來過木星嗎?” 姊姊問.

“啊, 當然不是啦~ 我是說我已經好久沒有讀地科了!” 妤嬌答應道, 並開始向太空船的其他人說明

“木星是solar system中最大的planet, Latin名叫Jupiter,” 妤嬌首先炫耀了自己的英文能力,

“它有64顆衛星, 也就是26顆, 質量約1/1047個太陽大,” 妤嬌津津樂道地說著.

“當然, 木星上面連細菌都沒有不可能會有敵人啦哇哈哈~” 雖然沒有人想聽妤嬌自high, 但他還是繼續說下去.

“木星的主要成份是氫氣佔了90%, 氫叫hydrogen, 原子序1, 有三種同位素, 原子量1的叫氫, 2的叫氘, 3...”

話還沒說完, 太空船起了劇烈的震蕩.
太空船被吸進木星核裡了, 一點也不意外, 畢竟木星是由氣體組成的.

“糟糕, 太空船的推進器力不足以抵抗木星的萬有引力啊, 木星的質量可是地球的318倍呢!” 剝剝火姬解釋

這時, 妤嬌姊姊已經開始暈船了. “啊~~~ 裡面(なかに)好熱~”

“妤嬌的在裡面, 沢山!” 妤嬌姊姊的語言功能已經失調了.

“只有姊姊這樣, 太狡猾了!” 妁艷妹妹也開始出現暈船症狀了, “呵呵呵, 我也要吃熱狗!!”

“哈哈哈-吞下了, 吞下了!!妤嬌, 現在你感覺如何? 感覺如何了!?” 妤嬌姊姊在一旁和道.

再這樣下去, 妤嬌可能會受不了!!! 可能會跟著暈船!! “啊, 我快到達極限了!!!”
現在的妤嬌腦中已一片空白, 不可能再作複雜的演算了!

“有了, 這裡有一個瞬間移動器, 好好用的話應該可以脫離木星大氣圈.” 剝剝火姬說.

瞬間移動器的使用方法很複雜, 移動器的操作盤是個圓盤, 圓盤上有n個燈連成一圈.
這n個燈由逆時針方向編號1~n, 其中第n個燈和第1個燈相鄰, 每個燈有紅色或綠色兩種狀態.
燈剛開始全都是綠色的, 要啓動瞬間移動器, 必須把所有的燈調成某種固定的圖樣.
但是, 每將一個燈改變狀態, 周圍的燈也可能跟著變. 燈泡之間有某種依賴關係.
在剝剝火姬的記憶中, 有許多可能的圖樣, 她不太記得是哪一種了.
你要幫她檢查她說的圖樣是否有可能達成.

燈泡之間的依賴關係可以用一個0-1序列S[0..m-1]來描述.
若按一下第i個燈泡, 那麼對於序列中S[j]=1的那些j, 第i+j個燈砲都會改變狀態, 而其它燈泡維持不變.
這邊為了方便我們規定第i個燈砲=第i+n個燈砲, 對所有i. (即表示這些燈泡是環狀的)

Input Format

本題有多筆測資. 第一行有一個數字t(t ≤ 10), 代表有幾筆測資.
每筆測資第一行有兩個數字n, m, 如上文所述.
接下來有n行, 第i行有一個數字0 or 1: 0代表剝剝火姬記得的圖樣的第i燈泡是緑色, 1代表紅色.
接下來有m行, 每i行有一個數字S[i-1]=0 or 1.

對30%的測資3≤n,m≤10
對60%的測資3≤n,m≤100
對100%的測資3≤n,m≤2000

Output Format

對每筆測資輸出一行, 若剝剝火姬所說的圖樣有可能達成, 輸出TAK, 否則輸出NIE.

Sample Input 1

3
3 3
1
0
1
1
0
0
3 3
1
1
1
0
1
1
3 3
0
0
0
0
0
0

Sample Output 1

TAK
NIE
TAK

Hints

Problem Source

原TIOJ1791 / problem setter: willyliu

Subtasks

No. Testdata Range Score
1 0 10
2 1 10
3 2 10
4 3 10
5 4 10
6 5 10
7 6 10
8 7 10
9 8 10
10 9 10

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 65536 262144 1
1 3000 65536 262144 2
2 3000 65536 262144 3
3 3000 65536 262144 4
4 3000 65536 262144 5
5 3000 65536 262144 6
6 3000 65536 262144 7
7 3000 65536 262144 8
8 3000 65536 262144 9
9 3000 65536 262144 10