전염병

Byteland은 국경을 막 봉쇄했다. 이웃 나라에서 새로운 변종 바이트박테리움이 발견되었기 때문이다. 연구에 따르면 새 변종은 전파력이 매우 강할 뿐 아니라 Bytelander의 면역 체계가 어떤 반응도 일으키지 않는다. 따라서 한 번 감염된 사람은 평생(또는 효과적인 치료법이 발견될 때까지) 감염된 상태로 남고, 다른 사람을 계속 감염시킨다.

정부는 확산을 막기 위해 강력한 제한 조치를 도입하고, 나라 안의 모든 사회적 접촉을 감시하는 전국 감시 시스템(National Invigilation System)을 가동했다. 정부는 격리되지 않은 사람 중에 감염자가 없다는 것이 확실해질 때에만 제한을 해제하겠다고 발표했다. 당신은 이 시스템의 데이터를 분석해 제한을 언제 해제할 수 있는지 판단하는 데이터 과학 담당자다.

Byteland에는 $n$명이 있다. 처음에는 각 사람이 건강하거나 감염되어 있을 수 있다. 국경이 봉쇄된 뒤 $k$개의 사건이 차례로 일어난다.

사회적 접촉은 한 무리의 사람들이 만나는 것이다. 그중 한 명이라도 감염되어 있으면 모두 감염되고, 그 상태는 계속 유지된다. 이것이 질병에 걸리는 유일한 경로다. 감염된 표면을 만지는 것으로는 전파되지 않는다.

음성 검사는 특정 사람이 검사를 받고 음성 결과를 얻는 것이다.

양성 검사는 특정 사람이 검사를 받고 양성 결과를 얻는 것이다. 이 사람은 즉시 격리되며, 그 이후로는 어떤 사회적 접촉에도 참여하지 않는다. 이후에 이 사람에게 다시 검사를 할 수도 있다. 결과가 이미 양성인 사람에게 왜 검사를 하는지에 대해 저자가 보건부에 문의했지만, 사안이 복잡하다는 이유로 회신이 3개월 연기되었다고 통보받았다.

질의는 보건부 장관이 제한을 해제할 수 있는지 묻는 것이다. 즉, 지금까지 얻은 정보로 격리된 사람을 제외하고는 아무도 감염될 수 없다는 것을 증명할 수 있는지를 묻는다. 여전히 감염되었을 수 있는 사람이 있다면, 출력 절의 지침에 따라 그 사람을 지목해야 한다.

해법은 온라인 알고리즘이어야 한다. 입력의 뒤쪽 부분을 읽지 않고, 각 질의를 읽는 즉시 답해야 한다.

입력의 해석은 변수 $shift$의 현재 값에 따라 달라진다. 각 테스트 케이스가 시작될 때 $shift$는 0이다. 이후 값은 프로그램의 답에 따라 정해진다.

복호화 함수는 decode(p) = ((p - 1 + shift) mod n) + 1로 정의한다. 여기서 $1 \le p \le n$이다.

첫 줄에는 테스트 케이스 수 $z$ ($1 \le z \le 1000$)가 주어진다. 각 테스트 케이스는 사람 수 $n$과 사건 수 $k$ ($1 \le n \le 500000$, $1 \le k \le 1000000$) 두 정수로 시작한다. 사람들은 1부터 $n$까지 번호가 매겨져 있다.

이어지는 $k$개의 줄은 다음 형식 중 하나로 사건을 설명한다.

K c p_1 ... p_c ($2 \le c \le n$)는 decode(p_1), ..., decode(p_c) 번호의 $c$명이 참여하는 사회적 접촉이다. $p_i$들은 서로 다르다.

N p는 decode(p)번 사람이 음성 결과가 나오는 검사를 받는다는 뜻이다.

P p는 decode(p)번 사람이 양성 결과가 나오는 검사를 받는다는 뜻이다. 이 사람은 그 순간부터 격리되며, 이후 이 사람에 대한 모든 검사는 양성이 된다.

Q p는 시작값이 decode(p)인 보건부 장관의 질의다.

모든 테스트 케이스의 $n$ 합은 500000을, $k$ 합은 1000000을 넘지 않는다. 모든 질의의 $c$ 합은 1000000을 넘지 않는다.

각 질의(Q 사건)마다 한 줄을 출력한다.

격리된 사람을 제외하고는 아무도 감염될 수 없다는 것을 증명할 수 있으면 TAK를 출력한다. 이때 변수 $shift$는 0이 된다.

그렇지 않으면 NIE와 정수 하나를 출력한다. 시작값을 $s = decode(p)$라고 하자. 이 정수는 수열 $s, s+1, ..., n, 1, 2, ..., s-1$에서 감염되었을 가능성이 있으면서 격리되지 않은 첫 번째 사람의 번호다. 이 번호가 새로운 $shift$ 값이 된다.

K, N, P 사건에서는 $shift$가 바뀌지 않는다. 각 테스트 케이스에서 양성과 음성 결과는 항상 모순 없는 시나리오를 나타낸다. 즉, 사건들에 모순이 없도록 하는 초기 감염자 집합이 적어도 하나 존재한다.