You have ~n~ bolts and ~n~ nuts of different sizes that are randomly mixed together. Each bolt has exactly one matching nut of the same size. Your task is to find which nut matches which bolt.

There's a constraint: you cannot directly compare a bolt with another bolt, nor can you compare a nut with another nut. However, you can try fitting a nut onto a bolt to determine their relative sizes.

Your goal is to find all matching pairs using as few comparisons as possible.

Input/Output (Interactive)

This is an interactive problem. Your program must interact with the judge by reading input and writing output in turns.

Initial Input

• The first line contains a single integer ~n~ ~(1 ≤ n ≤ 10^5)~ - the number of bolts and nuts.
• Both bolts and nuts are numbered from ~1~ to ~n~.

Interaction Protocol

• After reading n, your program should repeatedly make comparison queries until you have found all matching pairs:
  1. Output a query: Print b n where b is a bolt index and ~n~ is a nut index ~(1 ≤ b, n ≤ n)~
  2. Flush the output: Use System.out.flush() in Java
  3. Read the response: Read an integer from input, which will be one of:
     • -1 - The bolt is smaller than the nut
     • 0 - The bolt matches the nut (perfect fit!)
     • 1 - The bolt is larger than the nut
     • Once you have determined all matching pairs, output your answer:
  4. Output the answer: Print ! p_1 p_2 ... p_n where p_i is the index of the nut that matches bolt ~i~

Important: You must flush the output buffer after each query, otherwise the judge won't receive your output and the program will hang.

Scoring

• Each test case is scored based on the number of comparisons you make. Solutions using fewer comparisons will receive better scores. The total score is the sum across all test cases.

Example Interaction

Judge: 3
You:   1 1
Judge: 0
You:   2 2
Judge: 1
You:   2 3
Judge: 0
You:   3 2
Judge: -1
You:   3 1
Judge: 1
You:   1 2
Judge: -1
You:   ! 1 3 2

In this example:

• Bolt 1 matches Nut 1
• Bolt 2 matches Nut 3
• Bolt 3 matches Nut 2

The solution made 6 comparisons to find all matching pairs.

Constraints

• ~1 ≤ n ≤ 10^5~
• You can make at most 200 × n comparisons per test case
• All bolts and nuts have distinct sizes
• Each bolt has exactly one matching nut