Đoán hai món đã đặt

Đây là một bài toán tương tác (interactive).

Thực đơn của nhà hàng gồm $n$ món ăn, đánh số từ $1$ đến $n$. Nội đã gọi đúng $k$ món khác nhau; tập các món đã gọi được giữ bí mật, gọi là $S$.

Bạn được phép hỏi Nội bằng cách đưa ra hai số nguyên $x$ và $y$ ($1\le x,y\le n$). Khi đó:

• Với số $x$, Nội chọn một món $a\in S$ sao cho $|x-a|$ nhỏ nhất có thể (có thể $a=x$).
• Với số $y$, Nội chọn một món $b\in S$ sao cho $|y-b|$ nhỏ nhất có thể.
• Nội trả lời TAK nếu $|x-a|\le |y-b|$, và trả lời NIE trong trường hợp ngược lại.

Bằng không quá $60$ truy vấn, hãy chỉ ra hai món khác nhau bất kỳ thuộc $S$.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên $n$ và $k$ — số món trong thực đơn và số món Nội đã gọi.

Sau mỗi truy vấn, đọc một dòng chứa xâu TAK hoặc NIE — câu trả lời cho truy vấn vừa in.

Dữ liệu ra

Mỗi truy vấn in trên một dòng theo dạng 1 x y với $1\le x,y\le n$.

Khi đã sẵn sàng trả lời, in ra một dòng dạng 2 x y với $x\ne y$ và cả hai đều là món thuộc $S$, rồi kết thúc chương trình.

Sau mỗi lần in, bạn phải flush output (ví dụ cout << endl hoặc cout.flush() trong C++, flush=True trong Python).

Bạn sẽ nhận kết quả sai nếu dùng quá $60$ truy vấn, in ra số nằm ngoài đoạn $[1,n]$, hoặc đưa ra hai món không hợp lệ.

Ràng buộc

• $2\le k\le n\le {10}^5$
• Tối đa $60$ truy vấn loại $1$

Ví dụ