Byteland は、近隣諸国で bytebacterium の新たな菌株が検出されたため、国境を閉鎖したばかりです。研究によると、この菌株は非常に感染力が高いだけでなく、Byteland の人々の免疫系にまったく反応を引き起こしません。そのため、一度感染した人は生涯感染したままになり、他人に感染させ続けます（少なくとも、有効な治療法が発見されるまではそうなります）。

bytebacterium の拡散を抑えるため、Byteland 政府は広範な制限を導入し、国内のすべての社会的交流を監視できる National Invigilation System を稼働させました。隔離された人を除いて誰も bytebacterium に感染していないと確実に判断できた時点でのみ、制限を解除すると発表されました。国内で最も著名なデータ科学の専門家であるあなたは、監視システムのデータを分析し、実際にいつ制限を解除できるかを判定する任務を与えられました。

Byteland には $n$ 人の人がいて、初めは各人が健康である可能性も、bytebacterium に感染している可能性もあります。国境の閉鎖後、次の種類のイベントが合計 $k$ 回、順番に発生します。

• ある集団が会ったことが監視システムから分かります。その中に感染者が 1 人でもいれば、全員が感染し、その後ずっと感染したままになります。このような社会的接触が、この病気に感染する唯一の方法です（当初の報道とは異なり、汚染された表面に触れて発病することは実際にはありません）。

• ある人が bytebacterium の検査を受け、陰性の結果が出ます。

• ある人が bytebacterium の検査を受け、陽性の結果が出ます。その人は直ちに隔離され、以後いかなる社会的接触にも参加しません（ただし、その後さらに検査を受けることはあります [1]）。

• 保健大臣から、すでに制限を解除してよいかというクエリを受け取ります。つまり、それまでに得られたすべての情報から、隔離された人以外には感染している可能性のある人がいないと証明できるかを判定します。まだ感染している可能性のある人がいるなら、保健省の指針（「出力」の節を参照）に従い、そのような人の例を 1 人示す必要があります。

解法はオンラインアルゴリズムでなければなりません。つまり、各クエリを受け取った直後に、それより後の入力を一切読むことなく回答できなければなりません。

[1] 結果が陽性になることは明らかなのに、なぜそのような人に bytebacterium の検査を行うのか、不思議に思うかもしれません。出題者は Byteland の保健省にこの件を問い合わせましたが、案件の複雑さを理由に、法定の回答期限を 3 か月延長したと通知されました。

入力

入力を正しく解釈するには、変数 $\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$）が与えられます。その後に各テストケースの記述が続きます。

最初の行には、人数とイベント数をそれぞれ表す 2 つの整数 $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 のイベント）に対し 1 行ずつ出力してください。

$i$ 番目のクエリの時点で、隔離された人以外は誰も感染している可能性がないと証明できる場合、$i$ 行目には単語 TAK を出力してください [2]。この場合、変数 $\mathit{shift}$ の値は $0$ になります。

そうでない場合、$i$ 行目には単語 NIE と、その後に 1 つの整数を出力してください。クエリの開始値が $\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

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 番の人に陽性の検査結果が出ます。2 回目のクエリを受け取った時点で、それまでに集めたすべての情報から、クエリの開始値 3 から順に次の結論を導けます。3、4 番の人は必ず健康です。5、6 番の人は隔離されています。1 番の人は感染している可能性があります（実際には、必ず感染していることまで分かりますが、プログラムはこの 2 つの場合を区別する必要はありません）。したがって回答は NIE 1 で、$\mathit{shift}$ の値は $1$ になります。

• その後、1 番の人に陽性の検査結果が出て、次に 2、4 番の人が会い、その後 4 番の人に陰性の検査結果が出ます。2 回目のクエリを受け取ったとき、開始値 5 から順に次の結論を導けます。5、6、1 番の人は隔離されています。4 番の人の検査結果が陰性なので、2 番の人は必ず健康です。3、4 番の人も必ず健康です。したがって回答は TAK です。隔離されていない全員（2、3、4 番の人）が必ず健康だと証明できるからです。変数 $\mathit{shift}$ の値は $0$ になります。

• 3 回目のクエリの後、2 番の人に陰性の検査結果が出ます。簡単に分かるように、この部分の入力は実質的には無関係です。最初に TAK と回答した後は、そのテストケースの最後まで、回答はすべて TAK となるからです。