Byteland 刚刚关闭了边境，原因是邻国检测到了一种新型的 bytebacterium 菌株。研究表明，这种新菌株不仅具有高度传染性，而且不会触发 Byteland 人免疫系统的任何反应，因此一旦感染，终身携带（或者至少在发现有效疗法之前）。

为了遏制 bytebacterium 的传播，Byteland 政府采取了深远的限制措施，并启动了国家监视系统，以监测国内的所有社交互动。政府宣布，只有在确定除了被隔离的人员外，没有人感染 bytebacterium 时，才会解除限制。作为该国最著名的数据科学专家，你被委托分析来自监视系统的数据，并确定何时可以真正解除限制。

Byteland 有 $n$ 个人，最初，每个人要么是健康的，要么感染了 bytebacterium。边境关闭后，会依次发生 $k$ 个事件，事件类型如下：

• 你从监视系统中得知某一群人进行了会面。如果其中任何一人已感染，则所有人都会被感染（并将无限期保持感染状态）。这种社交接触是感染该疾病的唯一可能途径（与最初的新闻报道相反，通过接触受污染的表面而患病实际上是不可能的）。
• 某人进行了 bytebacterium 测试，结果为阴性。
• 某人进行了 bytebacterium 测试，结果为阳性。此人立即被隔离，此后将不再参与任何社交接触（尽管之后可能仍会对该人进行测试）。
• 你收到卫生部长的查询，以确定限制是否可以解除，即目前获得的所有信息是否足以证明除了被隔离的人员外，没有人可能被感染。如果仍有任何个人可能被感染，你需要根据卫生部的指导方针（在“输出格式”部分描述）提供此类人的示例。

你的程序必须实现一个在线算法——也就是说，你需要在收到每个查询后立即回答，而无需读取输入的后续部分。

输入格式

输入数据的正确解释取决于变量 shift 的当前值。在每个测试用例开始时，变量 shift 初始化为 0，其后续值将取决于你的程序返回的答案。这种输入格式旨在确保你的实现能在读取每个查询后立即回答。

解码函数定义如下：

decode (p) = ((p - 1 + shift) mod n) + 1

其中 $p$ 是满足 $1 \le p \le n$ 的整数，mod 是取模运算。

输入的第一行包含测试用例的数量 $z$ ($1 \le z \le 1000$)。接下来是各测试用例的描述。

每个测试用例的第一行包含两个整数 $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, \dots, p_c$ ($1 \le p_i \le n$) —— 一次社交接触，其中 $c$ 个标识符为 decode(p_1), ..., decode(p_c) 的人参与。
• 字母 N 后跟一个整数 $p$ ($1 \le p \le n$) —— 编号为 decode(p) 的人进行了 bytebacterium 测试，结果为阴性。
• 字母 P 后跟一个整数 $p$ ($1 \le p \le n$) —— 编号为 decode(p) 的人进行了 bytebacterium 测试，结果为阳性。此人立即被隔离，此后将不再参与任何社交接触（虽然之后对此人进行的任何进一步测试也将不可避免地给出阳性结果）。
• 字母 Q 后跟一个整数 $p$ ($1 \le p \le n$) —— 卫生部的查询，其起始值（见输出格式部分）等于 decode(p)。

所有测试用例中 $n$ 和 $k$ 的总和分别不超过 $500\,000$ 和 $1\,000\,000$。所有测试用例中所有查询的 $c$ 值之和不超过 $1\,000\,000$。

输出格式

对于每个测试用例，为该测试用例中出现的每个查询（Q 型事件）输出一行。

如果在第 $i$ 次查询时，可以证明除了被隔离的人员外，不可能有任何人被感染，则第 $i$ 行应包含单词 TAK。在这种情况下，变量 shift 的值变为 0。

否则，第 $i$ 行应包含单词 NIE 后跟一个整数。如果 decode(p) 是查询的起始值，则该整数应是序列 (decode(p), decode(p) + 1, ..., n, 1, 2, ..., decode(p) - 1) 中第一个可能感染 bytebacterium 但未被隔离的人的标识符。此数字成为变量 shift 的新值。

说明

• 变量 shift 在 K、N 或 P 型事件中不会改变其值。
• 阳性和阴性测试结果总是描述一个可信的场景。也就是说，对于每个测试用例，至少存在一组初始感染者，使得输入中描述的事件序列不包含任何矛盾。

样例

样例输入 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