Đây là một bài toán tương tác!

Có một mảng ẩn $a_1, a_2, \dots, a_N$ gồm $N$ số nguyên dương phân biệt (trong đó $N$ là số lẻ); một bản sao bị lỗi của mảng này được lưu trong một mảng ẩn khác $b$. Mỗi phần tử của mảng $b$ được định nghĩa như sau:

• $b_1 = a_2$
• $b_N = a_{N-1}$
• $b_i = a_{i-1}$ hoặc $b_i = a_{i+1}$ với mỗi $i$ thỏa mãn $1 < i < N$ (một trong hai phần tử kề cạnh)

Bạn cần xác định xem có tồn tại hai chỉ số $i$ và $j$ ($i \neq j$, $1 \le i, j \le N$) sao cho $b_i = b_j$ hay không. Nếu tồn tại các chỉ số như vậy, hãy trả về chúng; ngược lại, hãy chỉ ra rằng không tồn tại các chỉ số như vậy.

Bạn có thể truy vấn các phần tử của mảng $a$ và $b$ bằng các thao tác sau:

• 1 i: trả về giá trị của $a_i$ ($1 \le a_i \le 10^9$)
• 2 i: trả về giá trị của $b_i$ ($1 \le b_i \le 10^9$)

Bạn có thể hỏi tối đa 20 truy vấn.

Giao thức tương tác

Đầu tiên, bạn phải đọc một dòng chứa một số nguyên duy nhất $T$ ($1 \le T \le 100$) biểu thị số lượng bộ dữ liệu.

Sau đó là phần tương tác cho $T$ bộ dữ liệu.

Với mỗi bộ dữ liệu, trước tiên bạn phải đọc một dòng chứa một số nguyên $N$ ($3 \le N \le 2\,001$, $N$ là số lẻ).

Sau đó quá trình tương tác bắt đầu. Bạn có thể in ra một dòng chứa:

• 1 x (Hỏi về $a_x$): Sau đó, đọc một dòng gồm một số nguyên $a_x$.
• 2 x (Hỏi về $b_x$): Sau đó, đọc một dòng gồm một số nguyên $b_x$.
• 3 i j (Câu trả lời: hai chỉ số $i, j$ thỏa mãn $b_i = b_j$, hoặc -1 -1 nếu không có hai chỉ số như vậy): Sau đó, chuyển sang bộ dữ liệu tiếp theo nếu có; ngược lại, kết thúc chương trình.

Sau khi xuất mỗi dòng, đừng quên làm rỗng bộ đệm đầu ra (flush). Ví dụ:

• fflush(stdout) trong C/C++;
• System.out.flush() trong Java;
• sys.stdout.flush() trong Python;
• flush(output) trong Pascal;
• Xem tài liệu hướng dẫn cho các ngôn ngữ khác.

Ví dụ

Dữ liệu vào 1

1
7
2
2

Kết quả 1

2 3
2 1
3 1 3