이 문제는 인터랙티브 문제입니다!
서로 다른 $N$개의 양의 정수로 이루어진 숨겨진 배열 $a_1, a_2, \dots, a_N$이 있습니다 (여기서 $N$은 홀수입니다). 이 배열의 잘못된 복사본이 또 다른 숨겨진 배열 $b$에 저장되어 있습니다. 배열 $b$의 각 원소는 다음과 같이 정의됩니다:
- $b_1 = a_2$
- $b_N = a_{N-1}$
- $1 < i < N$인 각 $i$에 대해 $b_i = a_{i-1}$ 또는 $b_i = a_{i+1}$ (인접한 원소 중 하나)
$b_i = b_j$를 만족하는 두 인덱스 $i$와 $j$ ($i \neq j$, $1 \le i, j \le N$)가 존재하는지 판별해야 합니다. 그러한 인덱스가 존재하면 그 인덱스들을 반환하고, 그렇지 않으면 그러한 인덱스가 존재하지 않음을 나타내야 합니다.
다음 연산을 사용하여 배열 $a$와 $b$의 원소를 질의할 수 있습니다:
1 i: $a_i$의 값을 반환합니다 ($1 \le a_i \le 10^9$)2 i: $b_i$의 값을 반환합니다 ($1 \le b_i \le 10^9$)
최대 20번까지 질의할 수 있습니다.
상호작용 프로토콜
먼저 테스트 케이스의 수를 나타내는 단일 정수 $T$ ($1 \le T \le 100$)가 포함된 한 줄을 읽어야 합니다.
그다음 $T$개의 테스트 케이스에 대한 상호작용이 이어집니다.
각 테스트 케이스마다 먼저 하나의 정수 $N$ ($3 \le N \le 2\,001$, $N$은 홀수)이 포함된 한 줄을 읽어야 합니다.
그 후 상호작용이 시작됩니다. 다음 중 하나를 포함하는 한 줄을 출력할 수 있습니다:
1 x($a_x$에 대해 질문): 그다음 하나의 정수 $a_x$로 이루어진 한 줄을 읽습니다.2 x($b_x$에 대해 질문): 그다음 하나의 정수 $b_x$로 이루어진 한 줄을 읽습니다.3 i j(정답: $b_i = b_j$인 두 인덱스 $i, j$, 그러한 두 인덱스가 없으면-1 -1): 그다음 다음 테스트 케이스가 있으면 계속 진행하고, 없으면 종료합니다.
각 줄을 출력한 후 출력 버퍼를 비우는(flush) 것을 잊지 마세요. 예를 들어:
- C/C++의
fflush(stdout); - Java의
System.out.flush(); - Python의
sys.stdout.flush(); - Pascal의
flush(output); - 다른 언어는 해당 문서를 참고하세요.
예제
입력 1
1 7 2 2
출력 1
2 3 2 1 3 1 3