Background

Translated from BalkanOI 2018 Day 2 T2 “Popa”.

"He's an outlaw and he's famous
Andrii Popa the courageous.
Day and night he rides,
He takes his tribute from the main road
And everywhere in the country
The thief catchers are running away as fast as they can"

- "Andrii Popa", Phoenix

Problem Description

Ghiță has a sequence $S$ of positive integers indexed from $0$. Since he is the King of the Carpathians, he wants to construct a binary tree with nodes numbered $0,1,\ldots,N-1$ such that:

• The inorder traversal of the tree lists the node indices in increasing order. The inorder traversal of a binary tree is the concatenation, in order, of the inorder traversal of the subtree rooted at the left child of the root (if it exists), the index of the root, and the inorder traversal of the subtree rooted at the right child of the root (if it exists).
• If $x$ is the parent of node $y$, then $S_x$ divides $S_y$.

A binary tree is a tree structure where each node has at most two children, called the left child and the right child.

Unfortunately, the famous outlaw Andrii Popa stole the sequence $S$, so Ghiță cannot access it directly. However, for any two contiguous subarrays $[a,b]$ and $[c,d]$, he can use the most advanced technology (his phone) to determine whether $\gcd[a,b]$ is equal to $\gcd[c,d]$, where $\gcd[x,y]$ denotes the greatest common divisor of $S_x,S_{x+1},S_{x+2},\ldots,S_y$. Unfortunately, this technology is very expensive—if Ghiță uses it more than $Q$ times, he will have to pay a huge fine. Please help him construct the desired tree using this technology at most $Q$ times. It is guaranteed that this is possible. Any valid construction will be accepted.

Interaction

This problem only supports interactive solutions via functions in C++. The contestant’s code does not need to and must not include popa.h.

You need to implement the following function:

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

The function must return the root of the tree, and set Left[i] and Right[i] to be the left child and the right child of node $i$, respectively. If node $i$ has no left child, then Left[i] should be set to $-1$. If node $i$ has no right child, then Right[i] should be set to $-1$. Left and Right point to two already-allocated arrays of length exactly $N$.

The function solve will be called at most $5$ times in a single run. We suggest using global variables carefully.

You may call the following function (note that you must declare this function in your code):

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

This function returns $1$ if and only if $\gcd[a,b]=\gcd[c,d]$, where $0\le a\le b<n,0\le c\le d<N$. Otherwise it returns $0$.

Example

For example, if $S=[12, 4, 16, 2, 2, 20]$, one possible interaction process is as follows:

In the example, the tree King Ghiță wants is shown in the figure below.

Input Format

See “Interaction”.

Output Format

See “Interaction”.

Hint

Constraints

Translated by ChatGPT 5