Byteland 啱啱封咗邊境，原因係鄰國發現咗一種新嘅 bytebacterium 菌株。研究顯示，新菌株唔單止傳染性極高，仲完全唔會引起 Byteland 人免疫系統嘅反應，所以任何人一旦感染，就會成世都帶菌，亦會繼續傳染畀其他人（或者，至少喺搵到有效療法之前都係咁）。

為咗遏止 bytebacterium 傳播，Byteland 政府實施咗大範圍限制，仲啟用咗 National Invigilation System，監察國內所有社交互動。政府宣布，只有確定咗除已隔離嘅人之外，冇人感染 bytebacterium，先會解除限制。你係全國最出名嘅數據科學專家，受託分析監察系統嘅資料，判斷幾時真係可以解除限制。

Byteland 有 $n$ 個人，最初每個人都可能健康，亦可能已經感染 bytebacterium。封關之後，會依次發生 $k$ 個事件，類型如下：

• 你從監察系統得知有一班人見面。如果當中有任何一個人已感染，所有參與者都會感染（而且會永遠保持感染狀態）。呢類社交接觸係唯一可能嘅感染途徑（同最初嘅新聞報道相反，掂到受污染嘅表面其實唔可能令人染病）。

• 某個人接受 bytebacterium 檢測，結果係陰性。

• 某個人接受 bytebacterium 檢測，結果係陽性。呢個人即刻被隔離，之後唔再參與任何社交接觸（但之後仍然可能再接受檢測 [1]）。

• 你收到衞生部長嘅查詢，要判斷係咪已經可以解除限制，即係根據到目前為止得到嘅所有資訊，可唔可以證明除隔離者之外，冇人可能已感染。如果仲有任何人可能已感染，你要按照衞生部嘅指引（見「輸出格式」一節），畀一個符合條件嘅人做例子。

你嘅解法必須實作在線演算法，即係每次收到查詢後都要即刻回答，唔可以讀取輸入後面嘅任何部分。

[1] 你可能會諗，既然結果明顯一定係陽性，點解仲有人會幫呢啲人做 bytebacterium 檢測。出題者已經向 Byteland 衞生部作出相關查詢，但收到通知，話因為個案複雜，法定回覆期限已經延長三個月。

輸入格式

要正確解讀輸入資料，就要用變數 $\mathit{shift}$ 嘅目前值。每組測試資料開始嗰陣，$\mathit{shift}$ 會初始化為 $0$，之後嘅值就由你程式回傳嘅答案決定。呢種輸入格式係要確保你嘅程式讀完每個查詢之後即刻回答。

解碼函數定義如下：

$$ \operatorname{decode}(p)=((p-1+\mathit{shift})\bmod n)+1. $$

當中 $p$ 係滿足 $1 \le p \le n$ 嘅整數，而 $\bmod$ 係求整數除法餘數嘅運算。

輸入第一行有測試資料組數 $z$（$1 \le z \le 1\,000$）。跟住係每組測試資料嘅描述。

第一行有兩個整數 $n$ 同 $k$（$1 \le n \le 500\,000$，$1 \le k \le 1\,000\,000$），分別代表人數同事件數目。各人嘅編號由 $1$ 到 $n$。

跟住 $k$ 行依次描述各個事件，每個事件有以下其中一種形式：

• 字母 K 同一個整數 $c$（$2 \le c \le n$），之後有 $c$ 個互不相同嘅整數 $p_1,\ldots,p_c$（$1 \le p_i \le n$）：一次社交接觸，由編號為 $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$ 嘅 $c$ 個人參與。

• 字母 N，之後有一個整數 $p$（$1 \le p \le n$）：編號為 $\operatorname{decode}(p)$ 嘅人接受 bytebacterium 檢測，結果係陰性。

• 字母 P，之後有一個整數 $p$（$1 \le p \le n$）：編號為 $\operatorname{decode}(p)$ 嘅人接受 bytebacterium 檢測，結果係陽性。呢個人即刻被隔離，之後唔再參與任何社交接觸（而之後對佢做嘅任何檢測都一定會係陽性）。

• 字母 Q，之後有一個整數 $p$（$1 \le p \le n$）：衞生部嘅一次查詢，起始值（見「輸出格式」一節）係 $\operatorname{decode}(p)$。

所有測試資料嘅 $n$ 值總和同 $k$ 值總和分別唔超過 $500\,000$ 同 $1\,000\,000$。所有測試資料入面所有查詢嘅 $c$ 值總和唔超過 $1\,000\,000$。

輸出格式

對每組測試資料，每個查詢（Q 類事件）都要各自輸出一行。

如果喺第 $i$ 個查詢嗰陣，可以證明除隔離者之外，任何人都唔可能已感染，第 $i$ 行就應該有單字 TAK [2]。喺呢種情況下，變數 $\mathit{shift}$ 嘅值會變成 $0$。

否則，第 $i$ 行應該有單字 NIE，後面跟一個整數。如果查詢嘅起始值係 $\operatorname{decode}(p)$，呢個整數就應該係序列 $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ 入面，第一個可能已感染 bytebacterium 而又未被隔離嘅人嘅編號。呢個編號會成為變數 $\mathit{shift}$ 嘅新值。

[2] 有可能喺某個時刻，所有 Byteland 人都已經被隔離。當然，呢種情況下個敘述顯然成立，你嘅程式應該輸出 TAK。

備註

• 發生 K、N 或 P 類事件嗰陣，變數 $\mathit{shift}$ 嘅值唔會改變。

• 陽性同陰性檢測結果一定會構成一個合理嘅情境。即係對每組測試資料，都至少有一組最初感染嘅人，令輸入所描述嘅事件序列冇任何矛盾。

例子

輸入格式 1

1
6 14
K 3 3 4 5
K 2 6 5
N 3
Q 3
P 1
K 2 6 2
P 6
Q 4
P 6
K 2 1 3
N 3
Q 4
N 2
Q 1

輸出格式 1

NIE 5
NIE 1
TAK
TAK

• 解碼之後，上面嘅輸入如下：

1
6 14
K 3 3 4 5
K 2 6 5
N 3
Q 3
P 6
K 2 5 1
P 5
Q 3
P 1
K 2 2 4
N 4
Q 5
N 2
Q 1

說明

• 第一次查詢之前，3、4、5 號先見面，跟住 5、6 號見面，之後 3 號得到陰性檢測結果。收到第一次查詢嗰陣，我哋可以用目前收集到嘅所有資訊，由查詢起始值 3 開始得出以下結論。3 號一定健康（佢啱啱得到陰性結果）。4 號亦一定健康（佢喺第一次見面嗰陣唔可能已感染，否則佢會傳染畀 3、5 號，同 3 號之後得到嘅陰性結果矛盾；自此之後 4 號冇機會感染，所以目前一定健康）。5 號可能已感染（佢同 3、4 號見面嗰陣一定健康，但後來佢見咗 6 號，而現有資訊推斷唔到 6 號嘅健康狀況）。所以答案係 NIE 5，$\mathit{shift}$ 嘅值變成 $5$。

• 第一次查詢之後，6 號得到陽性檢測結果，跟住 1、5 號見面，之後 5 號得到陽性檢測結果。收到第二次查詢嗰陣，我哋可以用目前收集到嘅所有資訊，由查詢起始值 3 開始得出以下結論。3、4 號一定健康。5、6 號已被隔離。1 號可能已感染（其實甚至可以肯定佢一定已感染，但你嘅程式唔需要分辨呢兩種情況）。所以答案係 NIE 1，$\mathit{shift}$ 嘅值變成 $1$。

• 之後，1 號得到陽性檢測結果，跟住 2、4 號見面，之後 4 號得到陰性檢測結果。收到第二次查詢嗰陣，我哋可以由起始值 5 開始得出以下結論。5、6、1 號已被隔離。因為 4 號得到陰性結果，2 號一定健康。3、4 號亦一定健康。所以答案係 TAK，因為可以證明所有未被隔離嘅人（2、3、4 號）一定健康。變數 $\mathit{shift}$ 嘅值變成 $0$。

• 第三次查詢之後，2 號得到陰性檢測結果。好容易睇得出，呢部分輸入實際上無關緊要：第一次答 TAK 之後，直到嗰組測試資料結束，之後嘅答案都一定係 TAK。