Ghiță's Binary Tree Construction

King Ghiță has a positive integer sequence (S) with indices starting from 0. He wants to construct a binary tree with nodes numbered (0,1,\ldots,N-1) satisfying the following conditions:

1. The inorder traversal of the tree visits nodes in increasing order of their indices. Recall that the inorder traversal of a binary tree is obtained by concatenating the inorder traversal of the left subtree (if it exists), the root node, and then the inorder traversal of the right subtree (if it exists).

2. For every edge in the tree, if (x) is the parent of (y), then (S_x) divides (S_y) (i.e. (S_x \mid S_y)).

Unfortunately, the infamous Andrii Popa has stolen the sequence (S), so King Ghiță cannot access it directly. Instead, he is allowed to use an expensive gadget that, given any two consecutive subarrays ([a,b]) and ([c,d]), answers whether (\gcd(S_a,S_{a+1},\ldots,S_b)=\gcd(S_c,S_{c+1},\ldots,S_d)) (here the notation (\gcd[x,y]) stands for the greatest common divisor of (S_x, S_{x+1}, \ldots, S_y)). However, he is allowed to use this gadget at most (Q) times, or face a steep penalty.

Your task is to help him construct such a binary tree by implementing the function below. The tree you construct must satisfy the two conditions above. It is guaranteed that under the given constraints it is possible to construct at least one valid tree. Any valid construction is accepted.

Interaction

This is an interactive problem that supports function interaction in C++ only. You are to implement the following function:

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

The function should return the root of the tree, and you must set the arrays (Left) and (Right) (of length exactly (N)) so that for every node (i), if it has no left child, then (Left[i] = -1), and if it has no right child, then (Right[i] = -1).

You are allowed to call the following function in your solution (make sure to declare it in your code):

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

This function returns (1) if and only if (\gcd(S_a,S_{a+1},...,S_b)=\gcd(S_c,S_{c+1},...,S_d)) (with (0 \le a \le b < N, ; 0 \le c \le d < N)); otherwise it returns (0). The function solve may be called up to 5 times in a single run; please use global variables with care.

Sample

For example, suppose \(S=[12, 4, 16, 2, 2, 20]\). A possible interaction is shown below:

Call	Action	Result
solve(6, Left, Right)
	query(0, 1, 3, 5)	Returns 0
	query(4, 5, 1, 3)	Returns 1
		After the call, solve returns 3; \(Left = [-1, 0, -1, 1, -1, -1]\); \(Right = [-1, 2, -1, 4, 5, -1]\).

The tree corresponding to this sample is illustrated below:

Note

Since the interactive environment and the hidden sequence \(S\) make the problem quite involved, even a solution that uses few or no queries (for instance, a trivial construction that always produces a right‐skewed tree) is acceptable as long as it meets the required conditions for the hidden \(S\). For the purpose of testing, you may assume that \(S\) is chosen in such a way that, for example, if you construct a right-skewed tree (i.e. each node \(i\) (except the last) points to \(i+1\) as its right child and has no left child), it will be a valid plan (this is the case if all elements of \(S\) are equal to 1).

inputFormat

This is an interactive problem. In the implementation you are provided with the function solve(int N, int* Left, int* Right). For testing purposes, you can assume that the input is a single integer \(N\) (\(1 \le N \le 10^5\)) representing the number of nodes. In our sample tests, the hidden sequence \(S\) is chosen, for instance, as \([1,1,\ldots,1]\), so that a trivial tree construction is valid.

outputFormat

Your function should output the root of the tree on the first line, followed by a line with \(N\) integers representing the Left array, and a third line with \(N\) integers representing the Right array. For a node \(i\), if it does not have a left child, then Left[i] = -1, and if it does not have a right child then Right[i] = -1.

sample

1

0
-1
-1

</p>