위치 복원하기

이 문제는 인터랙티브 문제입니다.

수직선 상에 $N$개의 서로 다른 정수 좌표 $x\_1, x\_2, \cdots, x\_N$이 존재한다. 여러분은 이 값을 알지 못하며, $x\_1 = 0 < x\_2$이고 모든 $x\_i$가 $|x\_i| \le 10^9$를 만족한다는 사실만 알고 있다.

채점기에 다음 질문을 $\lfloor\frac{3}{2}N\rfloor$번 이하로 하여 $x\_1, x\_2, \cdots, x\_N$을 복원하자.

• ? $i$ $j$: $x\_i, x\_j$에 대해 $|x\_i - x\_j|$를 질문한다.

첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. $(1 \le T \le 500)$

각 테스트 케이스의 시작에 정수 좌표의 개수를 나타내는 정수 $N$이 주어진다. $(2 \le N \le 1\\,000)$

모든 테스트 케이스에 대한 $N$의 총합은 $1\\,000$을 넘지 않는다.

여러분은 다음 두 가지 유형의 질문을 채점기에 할 수 있다.

• ? $i$ $j$

  • $x\_i, x\_j$에 대해 $|x\_i - x\_j|$를 질문한다. $(1 \leq i < j \leq N$, $i, j$는 정수$)$
  • 이 유형의 질문은 최대 $\lfloor\frac{3}{2}N\rfloor$번 할 수 있다.

• ! $x\_1$ $x\_2$ $\cdots$ $x\_N$

  • $x\_1, x\_2, \cdots, x\_N$이 정답인지 질문한다. $(|x\_i| \le 10^9$, $x\_i$는 정수$)$
  • 별도의 반환값은 없고, 출력이 정답과 불일치한다면 틀렸습니다 판정을 받는다.
  • 출력이 정답과 일치하며 남은 테스트 케이스가 있다면 다음 테스트 케이스의 인터랙션이 이어서 진행된다.
  • 출력이 정답과 일치하며 남은 테스트 케이스가 없다면 맞았습니다!! 판정을 받는다.

모든 출력 이후에는 반드시 표준 출력 버퍼를 flush해야 한다. 언어 별로 표준 출력 버퍼를 flush하는 방법은 다음과 같다.

• C: fflush(stdout)
• C++: std::cout << std::flush
• Java: System.out.flush()
• Python: sys.stdout.flush()

기타 언어의 경우 각 언어의 documentation을 참조하자.

출력 형식을 지키지 않거나 첫 번째 유형의 질문을 $\lfloor\frac{3}{2}N\rfloor$번 초과로 한 경우에는 예상치 못한 채점 결과를 받을 수 있음에 유의하자.

모든 테스트 케이스를 해결한 뒤 프로그램은 즉시 종료되어야 한다.