Bài toán này và Trò chơi trên lá bài (easy version) là hai bài hoàn toàn khác nhau.

Đây là bài toán tương tác.

"Ái chà, thú vị đấy."

Đó là lời tán thưởng của noodles0428 khi bạn đã hoàn thành Trò chơi trên lá bài một cách hoàn toàn thuyết phục. Chính vì thế, cô ấy quyết định rủ bạn chơi một trò chơi nữa để thử thách khả năng suy luận của bạn.

Luật chơi như sau:

Trên tay noodles0428 đang có hai loại lá bài - trắng và đen. Nhiệm vụ của bạn là hãy xác định vị trí của một lá bài màu trắng bất kỳ.

Để có thể xác định màu của lá bài, bạn có thể đặt câu hỏi dưới dạng 1 i j với ý nghĩa như sau:

• Nếu lá bài thứ ~i~ là lá bài màu trắng, noodles0428 sẽ nói thật về màu của lá bài thứ ~j~.
• Nếu lá bài thứ ~i~ là lá bài màu đen, noodles0428 sẽ nói ngẫu nhiên về màu của lá bài thứ ~j~. Tức là cũng có thể là nói thật, và cũng có thể là nói dối. Tuy vậy, với mỗi lá bài ~i~ màu đen, bất luận bạn hỏi bao nhiêu lần, noodles0428 cũng sẽ nói dối hết, hoặc nói thật hết. Điều này có nghĩa, với mỗi lá bài ~i~ màu đen, việc nói dối hay thật là cố định.
• Máy chấm sẽ trả về ~1~ nếu noodles0428 nói lá bài thứ ~j~ là lá bài màu đen, và ~0~ nếu cô ấy nói lá bài thứ ~j~ là lá bài màu trắng.

Bạn biết được một thông tin cực kì quan trọng: số lá bài màu trắng nhiều hơn số lá bài màu đen. Ví dụ, có ~5~ lá bài, sẽ có ít nhất ~3~ lá bài màu trắng. Bạn sẽ chiến thắng nếu bạn xác định được vị trí của một lá bài màu trắng bất kỳ mà không hỏi noodles0428 quá ~5000~ truy vấn.

TƯƠNG TÁC

• Đầu tiên, bạn cần nhập số nguyên dương ~n~ (~1 \le n \le 1000~), là số lá bài mà noodles0428 đang cầm.
• Nếu là lượt của bạn, bạn có hai lựa chọn sau:
  • Nếu bạn chưa biết đáp án: bạn có quyền đặt câu hỏi cho noodles0428 có dạng 1 i j, trên một dòng.
  • Nếu bạn đã có đáp án: bạn hãy in ra một dãy số có dạng như sau: 2 x với ~x~ là vị trí của một lá bài màu trắng mà bạn đoán, trên một dòng. Kết thúc lượt này, chương trình sẽ ngắt.
• Nếu là lượt của noodles0428, cô ấy sẽ trả lời truy vấn của bạn dưới dạng ~0~ hoặc ~1~.

SAMPLE