Byteland vừa đóng cửa biên giới do phát hiện một chủng bytebacterium mới ở các nước láng giềng. Nghiên cứu cho thấy chủng mới không chỉ rất dễ lây lan mà còn không gây ra bất kỳ phản ứng nào từ hệ miễn dịch của người dân Byteland, nên một người đã nhiễm sẽ tiếp tục nhiễm — và tiếp tục lây cho người khác — suốt đời (hoặc ít nhất là cho đến khi tìm ra cách chữa trị hiệu quả).

Để ngăn chặn sự lây lan của bytebacterium, chính phủ Byteland đã áp dụng những hạn chế sâu rộng và triển khai Hệ thống Giám sát Quốc gia, cho phép theo dõi mọi tương tác xã hội trong nước. Chính phủ thông báo rằng các hạn chế chỉ được dỡ bỏ khi chắc chắn rằng không ai, ngoài những người đã bị cách ly, nhiễm bytebacterium. Là chuyên gia khoa học dữ liệu nổi tiếng nhất nước, bạn được giao nhiệm vụ phân tích dữ liệu từ hệ thống giám sát và xác định khi nào thực sự có thể dỡ bỏ các hạn chế.

Byteland có $n$ người và ban đầu, mỗi người đều có thể khỏe mạnh hoặc đã nhiễm bytebacterium. Sau khi biên giới đóng cửa, $k$ sự kiện diễn ra lần lượt, thuộc các loại sau:

• Bạn biết được từ hệ thống giám sát rằng một nhóm người gặp nhau. Nếu bất kỳ ai trong số họ đã nhiễm thì tất cả đều bị nhiễm (và sẽ tiếp tục nhiễm vô thời hạn). Tiếp xúc xã hội như vậy là cách duy nhất có thể mắc bệnh (trái với những thông tin ban đầu trên báo chí, thực ra không thể mắc bệnh do chạm vào các bề mặt nhiễm mầm bệnh).

• Một người thực hiện xét nghiệm bytebacterium và nhận kết quả âm tính.

• Một người thực hiện xét nghiệm bytebacterium và nhận kết quả dương tính. Người đó lập tức bị cách ly và từ đó không tham gia bất kỳ tiếp xúc xã hội nào nữa (mặc dù có thể sau này họ vẫn được xét nghiệm thêm lần nữa [1]).

• Bạn nhận được một truy vấn từ bộ trưởng y tế để xác định liệu đã có thể bãi bỏ các hạn chế hay chưa, tức là liệu toàn bộ thông tin thu được đến lúc đó có cho phép chứng minh rằng không ai — ngoài những người bị cách ly — có thể đang nhiễm hay không. Nếu vẫn có người có khả năng đang nhiễm, bạn cần đưa ra một ví dụ về người như vậy, tuân theo hướng dẫn của bộ (được mô tả trong phần Dữ liệu ra).

Lời giải của bạn phải triển khai một thuật toán trực tuyến: bạn phải có khả năng trả lời mỗi truy vấn ngay sau khi nhận được nó, mà không đọc bất kỳ phần nào phía sau của dữ liệu vào.

[1] Bạn có thể thắc mắc tại sao lại có người thực hiện xét nghiệm bytebacterium cho một người như vậy, khi rõ ràng kết quả chắc chắn phải là dương tính. Tác giả bài toán đã gửi câu hỏi liên quan đến Bộ Y tế Byteland, nhưng được thông báo rằng thời hạn trả lời theo luật định đã được gia hạn thêm ba tháng do tính chất phức tạp của vụ việc.

Dữ liệu vào

Việc diễn giải chính xác dữ liệu vào phụ thuộc vào giá trị hiện tại của biến $\mathit{shift}$. Khi bắt đầu mỗi bộ kiểm thử, biến $\mathit{shift}$ được khởi tạo bằng $0$, còn các giá trị sau đó phụ thuộc vào những câu trả lời mà chương trình của bạn đưa ra. Định dạng dữ liệu vào này nhằm đảm bảo rằng chương trình trả lời mỗi truy vấn ngay sau khi đọc nó.

Hàm giải mã được định nghĩa như sau:

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

Ở đây, $p$ là một số nguyên thỏa mãn $1 \le p \le n$, còn $\bmod$ là phép lấy phần dư của phép chia nguyên.

Dòng đầu tiên của dữ liệu vào chứa số bộ kiểm thử $z$ ($1 \le z \le 1\,000$). Tiếp theo là mô tả các bộ kiểm thử.

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ ($1 \le n \le 500\,000$, $1 \le k \le 1\,000\,000$), lần lượt là số người và số sự kiện. Mọi người được đánh số từ $1$ đến $n$.

Tiếp theo là $k$ dòng mô tả các sự kiện liên tiếp, mỗi dòng có một trong các dạng sau:

• Chữ cái K và một số nguyên $c$ ($2 \le c \le n$), theo sau bởi $c$ số nguyên phân biệt $p_1,\ldots,p_c$ ($1 \le p_i \le n$): một cuộc tiếp xúc xã hội có $c$ người với các mã số $\operatorname{decode}(p_1),\ldots,\operatorname{decode}(p_c)$ tham gia.

• Chữ cái N theo sau bởi một số nguyên $p$ ($1 \le p \le n$): người số $\operatorname{decode}(p)$ thực hiện xét nghiệm bytebacterium và nhận kết quả âm tính.

• Chữ cái P theo sau bởi một số nguyên $p$ ($1 \le p \le n$): người số $\operatorname{decode}(p)$ thực hiện xét nghiệm bytebacterium và nhận kết quả dương tính. Người đó lập tức bị cách ly và từ thời điểm đó không tham gia bất kỳ tiếp xúc xã hội nào nữa (đồng thời mọi xét nghiệm tiếp theo được thực hiện cho người đó tất yếu cũng cho kết quả dương tính).

• Chữ cái Q theo sau bởi một số nguyên $p$ ($1 \le p \le n$): truy vấn của bộ với giá trị bắt đầu (xem phần Dữ liệu ra) bằng $\operatorname{decode}(p)$.

Tổng các giá trị $n$ và $k$ trên tất cả các bộ kiểm thử lần lượt không vượt quá $500\,000$ và $1\,000\,000$. Tổng các giá trị $c$ trên tất cả các truy vấn của tất cả các bộ kiểm thử không vượt quá $1\,000\,000$.

Dữ liệu ra

Với mỗi bộ kiểm thử, in ra một dòng cho mỗi truy vấn (sự kiện loại Q) xuất hiện trong bộ kiểm thử đó.

Nếu tại thời điểm truy vấn thứ $i$, có thể chứng minh rằng không thể có ai (ngoài những người bị cách ly) đang nhiễm, thì dòng thứ $i$ phải chứa từ TAK [2]. Trong trường hợp này, biến $\mathit{shift}$ đổi giá trị thành $0$.

Ngược lại, dòng thứ $i$ phải chứa từ NIE theo sau bởi một số nguyên. Nếu $\operatorname{decode}(p)$ là giá trị bắt đầu của truy vấn, thì số nguyên đó phải là mã số của người đầu tiên trong dãy $(\operatorname{decode}(p),\operatorname{decode}(p)+1,\ldots,n,1,2,\ldots,\operatorname{decode}(p)-1)$ có thể đang nhiễm bytebacterium nhưng không bị cách ly. Số này trở thành giá trị mới của biến $\mathit{shift}$.

[2] Có thể đến một thời điểm nào đó, tất cả người dân Byteland đều bị cách ly. Tất nhiên, khi đó mệnh đề này hiển nhiên đúng và chương trình của bạn phải in TAK.

Nhận xét

• Biến $\mathit{shift}$ không thay đổi giá trị trong các sự kiện loại K, N hoặc P.

• Các kết quả xét nghiệm dương tính và âm tính luôn mô tả một kịch bản có thể xảy ra. Tức là, với mỗi bộ kiểm thử, tồn tại ít nhất một tập hợp những người nhiễm ban đầu sao cho chuỗi sự kiện được mô tả trong dữ liệu vào không có bất kỳ mâu thuẫn nào.

Ví dụ

Dữ liệu vào 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

Dữ liệu ra 1

NIE 5
NIE 1
TAK
TAK

• Sau khi giải mã, dữ liệu vào ở trên có dạng như sau:

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

Ghi chú

• Trước truy vấn đầu tiên, những người 3, 4 và 5 gặp nhau, sau đó những người 5 và 6 gặp nhau, rồi người 3 nhận kết quả xét nghiệm âm tính. Khi nhận truy vấn đầu tiên, từ toàn bộ thông tin thu thập được đến lúc đó, ta có thể rút ra các kết luận sau (bắt đầu từ giá trị bắt đầu của truy vấn là 3). Người 3 chắc chắn khỏe mạnh (anh ấy vừa nhận kết quả xét nghiệm âm tính). Người 4 cũng chắc chắn khỏe mạnh (cô ấy không thể đã nhiễm vào thời điểm cuộc gặp đầu tiên, vì nếu không thì cô ấy đã lây cho những người 3 và 5, mâu thuẫn với kết quả xét nghiệm âm tính mà người 3 nhận được sau đó; kể từ đó, người 4 không có khả năng nào bị lây nhiễm, nên hiện tại cô ấy chắc chắn khỏe mạnh). Người 5 có thể đang nhiễm (anh ấy chắc chắn khỏe mạnh khi gặp 3 và 4, nhưng sau đó đã gặp người 6, người mà ta không thể suy ra tình trạng sức khỏe từ thông tin hiện có). Vì vậy, câu trả lời là NIE 5 và $\mathit{shift}$ đổi giá trị thành $5$.

• Sau truy vấn đầu tiên, người 6 nhận kết quả xét nghiệm dương tính, sau đó những người 1 và 5 gặp nhau, rồi người 5 nhận kết quả xét nghiệm dương tính. Khi nhận truy vấn thứ hai, từ toàn bộ thông tin thu thập được đến lúc đó, ta có thể rút ra các kết luận sau (bắt đầu từ giá trị bắt đầu của truy vấn là 3). Những người 3 và 4 chắc chắn khỏe mạnh. Những người 5 và 6 đang bị cách ly. Người 1 có thể đang nhiễm (thực ra, ta thậm chí có thể chắc chắn rằng cô ấy phải đang nhiễm, nhưng chương trình của bạn không cần phân biệt hai trường hợp này). Vì vậy, câu trả lời là NIE 1 và $\mathit{shift}$ đổi giá trị thành $1$.

• Sau đó, người 1 nhận kết quả xét nghiệm dương tính, rồi những người 2 và 4 gặp nhau, rồi người 4 nhận kết quả xét nghiệm âm tính. Khi nhận truy vấn thứ hai, ta có thể rút ra các kết luận sau (bắt đầu từ giá trị bắt đầu là 5). Những người 5, 6 và 1 đang bị cách ly. Người 2 chắc chắn khỏe mạnh do kết quả xét nghiệm âm tính mà người 4 nhận được. Những người 3 và 4 cũng chắc chắn khỏe mạnh. Vì vậy, câu trả lời là TAK, vì có thể chứng minh rằng tất cả những người không bị cách ly (2, 3 và 4) chắc chắn khỏe mạnh. Biến $\mathit{shift}$ đổi giá trị thành $0$.

• Sau truy vấn thứ ba, người 2 nhận kết quả xét nghiệm âm tính. Như bạn có thể dễ dàng nhận thấy, phần dữ liệu vào này thực ra không có ý nghĩa: sau câu trả lời TAK đầu tiên, các câu trả lời tiếp theo phải đều là TAK cho đến hết bộ kiểm thử đó.