“그는 무법자이고 이름난 자라네, 용감한 Andrii Popa.

밤낮으로 말을 달리며, 큰길에서 통행세를 거두니 온 나라 어디에서나 도둑잡이들이 죽을힘을 다해 도망치네”

— “Andrii Popa”, Phoenix

Ghiță에게는 $N$개의 양의 정수 가중치로 이루어진 $0$-기반 수열 $S$가 있습니다. 그는 카르파티아 산맥의 왕이므로, 정점들의 번호가 $0, 1, \ldots, N - 1$이고 다음 조건을 만족하는 이진 트리를 구성하고자 합니다:

• 트리의 중위 순회(inorder traversal) 결과는 정점들을 번호가 증가하는 순서대로 나열한 것이다. 이진 트리의 중위 순회는 루트의 왼쪽 자식을 루트로 하는 서브트리의 중위 순회(왼쪽 자식이 존재하는 경우), 그 다음 루트의 번호, 그 다음 루트의 오른쪽 자식을 루트로 하는 서브트리의 중위 순회(오른쪽 자식이 존재하는 경우)로 이루어진다.
• 정점 $x$가 정점 $y$의 부모이면 $S_x$는 $S_y$의 약수이다.

이진 트리란 각 정점이 최대 두 개의 자식을 가지며, 이들을 각각 왼쪽 자식과 오른쪽 자식이라고 부르는 트리 자료구조임을 상기합시다.

불행히도 유명한 무법자 Andrii Popa가 수열 $S$를 훔쳐 갔기 때문에, Ghiță는 더 이상 수열에 직접 접근할 수 없습니다. 첨단 기술(그의 휴대전화)을 사용하면, 그는 $S$의 임의의 두 연속 부분 수열 $[a, b]$와 $[c, d]$에 대해 $\gcd[a, b]$와 $\gcd[c, d]$가 같은지 알아낼 수 있습니다. 여기서 $\gcd[x, y]$는 $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$의 최대공약수입니다. 안타깝게도 이 기술은 꽤 비싸서, Ghiță가 이를 $Q$번 초과하여 사용하면 거액의 벌금을 내야 합니다. 이 기술을 최대 $Q$번 사용하여 원하는 트리를 구성할 수 있도록 그를 도와주십시오. 이것이 항상 가능함이 보장됩니다. 올바른 해라면 어떤 것이든 정답으로 인정됩니다.

인터랙션

참가자는 헤더 popa.h(C / C++)를 포함하거나 popa.pas(Pascal)를 구현해야 합니다. 참가자는 다음 함수를 구현해야 합니다:

int solve(int N, int* Left, int* Right);

function solve(N: LongInt, var Left, Right: array of LongInt): LongInt;

이 함수는 트리의 루트를 반환해야 하며, $\text{Left}_i$와 $\text{Right}_i$를 각각 정점 $i$의 왼쪽 자식과 오른쪽 자식으로 설정해야 합니다. 정점 $i$에 왼쪽 자식이 없다면 $\text{Left}_i$는 $-1$이어야 합니다. 정점 $i$에 오른쪽 자식이 없다면 $\text{Right}_i$는 $-1$이어야 합니다. Left와 Right는 이미 할당된 크기가 정확히 $N$인 두 배열을 가리킵니다.

solve 함수는 한 번의 실행 동안 최대 $5$번 호출될 수 있습니다. 전역 변수 사용에 주의할 것을 권장합니다.

참가자는 다음 함수를 사용할 수 있습니다:

int query(int a, int b, int c, int d);

function query(a, b, c, d: LongInt): LongInt;

이 함수는 $0 \le a \le b < N$이고 $0 \le c \le d < N$일 때, $\gcd[a, b]$가 $\gcd[c, d]$와 같으면 $1$을 반환하고, 그렇지 않으면 $0$을 반환합니다.

서브태스크

서브태스크 1 (37점)

• $N = 100$
• $Q = 10000$

서브태스크 2 (24점)

• $N = 1000$
• $Q = 20000$

서브태스크 3 (39점)

• $N = 1000$
• $Q = 2000$

예제

$S = [12, 4, 16, 2, 2, 20]$에 대한 인터랙션의 예시는 다음과 같습니다:

참고

앞선 예제에 대해 Ghiță가 원하는 종류의 트리 중 하나는 다음과 같습니다: