Anna nghĩ ra một phép toán hai ngôi bí mật \(\star\). Với mọi số nguyên không âm \(x,y\le 1\,000\,000\,000\), giá trị \(x\star y\) cũng là một số nguyên không âm không vượt quá \(1\,000\,000\,000\). Phép toán này có tính kết hợp:

Anna cho Bruno xem \(N\) số \(A_0,A_1,\ldots,A_{N-1}\), sau đó đặt nhiều truy vấn yêu cầu tính:

Bruno không biết phép toán \(\star\), nhưng có thể hỏi giá trị \(x\star y\) thông qua hàm Secret. Hãy cài đặt chiến lược trả lời đúng mọi truy vấn với số lần gọi Secret nhỏ nhất có thể.

Chi tiết cài đặt

Bài nộp phải khai báo:

#include "secret.h"

và cài đặt chính xác hai hàm:

void Init(int N, int A[]);
int Query(int L, int R);

Hàm Init được gọi đúng một lần lúc bắt đầu.

• N là số phần tử.
• A là mảng độ dài \(N\), chứa \(A_0,A_1,\ldots,A_{N-1}\).

Hàm Query được gọi cho mỗi truy vấn.

• \(0\le L\le R\le N-1\).
• Hàm phải trả về \(A_L\star A_{L+1}\star\cdots\star A_R\).

Bài nộp có thể gọi hàm do bộ chấm cung cấp:

int Secret(int X, int Y);

• X và Y phải nằm trong đoạn \([0,1\,000\,000\,000]\). Gọi hàm với tham số ngoài đoạn này sẽ bị chấm sai ngay lập tức.
• Hàm trả về \(X\star Y\).

Bài nộp không được cài đặt hàm main.

Bộ chấm mẫu

Trong bộ chấm mẫu, phép toán được định nghĩa là:

Phép toán của bộ chấm chính thức có thể khác.

Bộ chấm mẫu đọc:

• Dòng đầu chứa \(N\).
• Dòng thứ hai chứa \(A_0,A_1,\ldots,A_{N-1}\).
• Dòng thứ ba chứa số truy vấn \(Q\).
• \(Q\) dòng tiếp theo, mỗi dòng chứa \(L_j,R_j\).

Bộ chấm mẫu in giá trị trả về của mỗi lời gọi Query, mỗi giá trị trên một dòng. Nó cũng báo số lần gọi Secret trong Init và số lần gọi lớn nhất trong một lời gọi Query.

Ràng buộc

• \(1 \le N \le 1\,000\).
• \(0 \le A_i \le 1\,000\,000\,000\).
• Số lần gọi Query không vượt quá \(10\,000\).

Chấm điểm

Điểm chỉ được trao nếu chương trình kết thúc bình thường, mọi lời gọi Secret đều hợp lệ và tất cả giá trị trả về bởi Query đều đúng.

• 100 điểm: trong mỗi bộ kiểm thử, Init gọi Secret không quá \(8\,000\) lần và mỗi lời gọi Query gọi Secret không quá một lần.
• 30 điểm: nếu không đạt điều kiện 100 điểm, nhưng Init gọi Secret không quá \(8\,000\) lần và mỗi lời gọi Query gọi Secret không quá \(20\) lần.
• 6 điểm: lời giải đúng nhưng không đạt hai mức trên.

Ví dụ

8
1 4 7 2 5 8 3 6
4
0 3
1 7
5 5
2 4

13
32
8
13