Có một hoán vị ẩn \(a_1, a_2,\dots, a_n\) của các số nguyên \(1, 2,\dots, n\). Nhiệm vụ của bạn là sắp xếp hoán vị bằng cách đảo các đoạn con.

Ở mỗi lượt, bạn có thể đảo một đoạn con của hoán vị. Sau đó, bạn sẽ được thông báo số nghịch thế trong hoán vị. Nếu số nghịch thế là \(0\) (tức là hoán vị đã được sắp xếp), bạn thắng.

Interaction

Đây là một bài toán tương tác. Chương trình của bạn sẽ tương tác với trình chấm bằng chuẩn vào và chuẩn ra. Bạn cần bắt đầu bằng cách đọc một số nguyên \(n\): độ dài của hoán vị.

Ở lượt của mình, hãy in hai số nguyên \(i\) và \(j\): đảo đoạn con giữa hai chỉ số \(i\) và \(j\).

Sau đó, dòng nhập tiếp theo chứa một số nguyên: số nghịch thế sau thao tác. Nếu số này là \(0\), bạn thắng và chương trình của bạn phải kết thúc sau đó.

Constraints

• \(1\leq n\leq 1000\)

• bạn được thực hiện tối đa \(4n\) thao tác

Example

3
1 2
1
2 3
0

Giải thích: Ở đây hoán vị ban đầu là \([3,1,2]\). Sau thao tác đầu tiên, hoán vị là \([1,3,2]\) và số nghịch thế là \(1\). Sau thao tác thứ hai, hoán vị là \([1,2,3]\) và số nghịch thế là \(0\).