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。