룩 백

그림을… 더 잘 그리고 싶으니까.

— 쿄모토, 「룩 백」

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

$2N \times 2N$ 크기의 체스판 위에 룩이 $N(N = {\color{ForestGreen}{100}})$개 올려져 있다. 각 칸에는 최대 한 개의 룩만 있을 수 있다. 체스판의 $i$행 $j$열$(1 \leq i, j \leq 2N)$의 칸은 $(i, j)$와 같이 나타낸다. 하지만 당신은 체스판을 볼 수 없다.

룩은 같은 행 또는 같은 열에 있는 다른 룩을 공격할 수 있다. 단, 룩은 다른 룩을 넘어 공격할 수 없다. 즉, 같은 행 또는 같은 열에 있는 두 룩 사이에 다른 룩이 존재하지 않을 때에만 두 룩은 서로 공격 가능하다.

당신의 목표는 다음과 같은 질문을 최대 $3N$번 하여 서로 공격 가능한 룩 쌍의 수를 알아내는 것이다. 여기서 같은 두 룩으로 이루어진 쌍은 순서와 관계없이 한 번만 센다.

• $?$ $x_1\, y_1\, x_2\, y_2$: 체스판에서 행 번호가 $x_1$ 이상 $x_2$ 이하이고, 열 번호가 $y_1$ 이상 $y_2$ 이하인 칸들로 이루어진 직사각형 영역 안에 존재하는 룩의 개수를 반환한다.

당신의 프로그램은 아래의 과정을 통해 표준입력과 표준출력으로 인터랙터와 상호작용해야 한다.

입력은 하나 이상의 테스트 케이스로 이루어져 있다. 먼저, 첫 번째 줄에 테스트 케이스의 개수 $T$가 주어진다. 각 테스트 케이스에 대해서 아래와 같이 상호작용해야 한다. $(1 \leq T \leq 100)$

테스트 케이스의 첫 번째 줄에 정수 $N$이 주어진다. $(N = 100)$

아래 쿼리를 출력하면, 다음 줄에 질문의 답을 나타내는 정수가 주어진다. 이 쿼리는 하나의 테스트 케이스에서 최대 $3N$번만 사용할 수 있다.

• $?$ $x_1\, y_1\, x_2\, y_2$ ㅤ(단, $1 \leq x_1 \leq x_2 \leq 2N;\ 1 \leq y_1 \leq y_2 \leq 2N;\ x_1, y_1, x_2, y_2$는 정수)

위 쿼리에 대해 인터랙터는 행 번호가 $x_1$ 이상 $x_2$ 이하이고, 열 번호가 $y_1$ 이상 $y_2$ 이하인 칸들로 이루어진 직사각형 영역 안에 존재하는 룩의 개수를 반환한다.

아래 쿼리를 출력해서 문제의 답 $x$를 제출할 수 있다. 이 쿼리는 질문에 포함되지 않으며, 출력한 직후 해당 테스트 케이스에 대한 인터랙션은 종료된다.

• $!$ $x$

인터랙터는 적응적이다. 즉, 인터랙션이 진행 중일 때 룩의 위치가 정해져 있지 않을 수 있지만, 모든 쿼리의 응답과 모순되지 않는 위치가 항상 존재한다.

마지막이 아닌 테스트 케이스에 대한 상호작용이 종료되었다면 즉시 다음 테스트 케이스에 대한 상호작용으로 넘어가야 하고, 마지막 테스트 케이스에 대한 상호작용이 종료되었다면 즉시 프로그램을 종료해야 한다.

각 채점 데이터에 대하여, 모든 테스트 케이스에서 제출한 답이 정답이라면 AC, 적어도 하나의 테스트 케이스에서 제출한 답이 오답이라면 WA 결과를 받는다. 단, 문제의 제한 안에 올바른 상호작용을 통해 답을 출력하지 못하면 예상치 못한 채점 결과를 받을 수 있다.

당신의 프로그램은 무언가를 출력한 후 즉시 출력 버퍼를 비워야 한다. 다음은 언어별 출력 버퍼를 비우는 방법이다.

• C : fflush(stdout)
• C++ : std::cout.flush()
• Python : sys.stdout.flush()
• Java : System.out.flush()
• 그 외의 언어는 각 언어의 Documentation을 참고한다.