Pesley has randomly generated two hidden permutations ~A~ and ~B~ of length ~N~ (or at least as random as a computer can). The permutation contains distinct values from ~1~ to ~N~. He wants you to find any indices ~i~ and ~j~ such that ~A_i = B_j~. Of course, he won't make it that easy and will only give you ~10\,000~ guesses to do so. After making a guess, he will respond with the values of ~A_i~ and ~B_j~. Can you find any such pair of indices?

Constraints

For this problem, you will NOT be required to pass ANY of the samples in order to receive points.

For all subtasks:

~1 \le N \le 300\,000~
~A~ and ~B~ are selected uniformly at random (subject to the limitations of a computer).

Subtask 1 [15%]

~1 \le N \le 10~

Subtask 2 [17%]

~1 \le N \le 10\,000~

Subtask 3 [68%]

No additional constraints.

Interaction

The first line contains the integer ~N~, the length of the permutations.

You will then begin making guesses. For each guess, output two space-separated integers ~i~, ~j~ on a single line terminated by a \n character. ~1 \le i \le N~ and ~1 \le j \le N~ must be satisfied. Pesley will then respond with two space-separated integers ~A_i~, ~B_j~ (followed by a \n character), representing the values in the first and second permutations at indices ~i~ and ~j~. If ~A_i = B_j~, then you have found the indices and will receive an Accepted verdict. Otherwise, you can continue to make more guesses until you run out, in which case, you will receive a Wrong Answer verdict.

If at any point you attempt an invalid operation (such as an invalid output format, failure to provide any output, or index out of bounds), -1 will be outputted (followed by a \n character). When this happens, you should terminate your program to avoid reading from a closed input stream, and you will receive a verdict of Wrong Answer (Presentation Error). Otherwise, the verdict may be undefined.

Please note that you may need to flush stdout after each operation. In C++, this can be done with fflush(stdout) or cout << flush (depending on whether you use printf or cout). In Java, this can be done with System.out.flush(). In Python, you can use sys.stdout.flush().

Sample Interaction

>>> denotes your output. Do not print this out.

4
>>> 1 2
3 4
>>> 4 3
4 2
>>> 3 1
1 1

Sample Explanation

In this example, ~A = [3, 2, 1, 4]~ and ~B = [1, 4, 2, 3]~. ~(1, 3)~ is one possible pair of indices as ~A_3 = B_1 = 1~.