“Hắn là kẻ ngoài vòng pháp luật và lừng danh, Andrii Popa dũng cảm.

Ngày đêm hắn phi ngựa, Thu cống nạp trên đường cái Và khắp mọi nơi trong cả nước Đám thợ săn trộm đang tháo chạy nhanh hết sức có thể”

— “Andrii Popa”, Phoenix

Ghiță có một dãy $S$ được đánh số từ $0$ gồm $N$ trọng số nguyên dương. Vì là vua của dãy núi Carpathian, anh muốn xây dựng một cây nhị phân có các đỉnh mang chỉ số $0, 1, \ldots, N - 1$ sao cho:

• Phép duyệt trung thứ tự (inorder) của cây cho ra các đỉnh theo thứ tự chỉ số tăng dần. Phép duyệt trung thứ tự của một cây nhị phân được tạo thành từ phép duyệt trung thứ tự của cây con có gốc là con trái của gốc (nếu con đó tồn tại), tiếp theo là chỉ số của gốc, rồi đến phép duyệt trung thứ tự của cây con có gốc là con phải của gốc (nếu con đó tồn tại).
• Nếu đỉnh $x$ là cha của đỉnh $y$ thì $S_x$ là ước của $S_y$.

Nhắc lại rằng cây nhị phân là một cấu trúc dữ liệu dạng cây, trong đó mỗi đỉnh có tối đa hai con, được gọi là con trái và con phải.

Thật không may, tên cướp lừng danh Andrii Popa đã đánh cắp dãy $S$, và Ghiță không còn có thể truy cập trực tiếp vào nó nữa. Sử dụng công nghệ tiên tiến (điện thoại di động của mình), với hai dãy con liên tiếp bất kỳ $[a, b]$ và $[c, d]$ của $S$, anh có thể biết được $\gcd[a, b]$ có bằng $\gcd[c, d]$ hay không, trong đó $\gcd[x, y]$ là ước chung lớn nhất của $S_x, S_{x+1}, S_{x+2}, \ldots, S_y$. Đáng tiếc là công nghệ này khá đắt đỏ — nếu Ghiță sử dụng nó quá $Q$ lần, anh sẽ phải nộp một khoản tiền phạt lớn. Hãy giúp anh ấy sử dụng công nghệ này nhiều nhất $Q$ lần để xây dựng cây mong muốn. Dữ liệu đảm bảo rằng điều này luôn thực hiện được. Mọi lời giải hợp lệ đều sẽ được chấp nhận.

Giao tiếp

Thí sinh cần khai báo thư viện popa.h (C / C++) hoặc cài đặt popa.pas (Pascal). Thí sinh cần cài đặt hàm sau:

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

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

Hàm này phải trả về gốc của cây, đồng thời gán $\text{Left}_i$ và $\text{Right}_i$ lần lượt là con trái và con phải của đỉnh $i$. Nếu đỉnh $i$ không có con trái thì $\text{Left}_i$ phải bằng $-1$. Nếu đỉnh $i$ không có con phải thì $\text{Right}_i$ phải bằng $-1$. Left và Right trỏ tới hai mảng có kích thước đúng bằng $N$ đã được cấp phát sẵn.

Hàm solve có thể được gọi nhiều nhất $5$ lần trong suốt một lần chạy. Chúng tôi khuyên bạn nên cẩn thận khi sử dụng biến toàn cục.

Thí sinh có thể sử dụng hàm sau:

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

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

Hàm này sẽ trả về $1$ khi và chỉ khi $\gcd[a, b]$ bằng $\gcd[c, d]$, với $0 \le a \le b < N$ và $0 \le c \le d < N$, và trả về $0$ trong trường hợp ngược lại.

Nhiệm vụ con

Nhiệm vụ con 1 (37 điểm)

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

Nhiệm vụ con 2 (24 điểm)

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

Nhiệm vụ con 3 (39 điểm)

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

Ví dụ

Một ví dụ về quá trình giao tiếp với $S = [12, 4, 16, 2, 2, 20]$ như sau:

Ghi chú

Một ví dụ về cây thỏa mãn yêu cầu của Ghiță cho ví dụ trên là: