Description

Anna invented a secret binary operation $\star$. For non-negative integers $x, y$ less than or equal to $1\,000\,000\,000$, a non-negative integer $x \star y$ less than or equal to $1\,000\,000\,000$ is determined. This operation $\star$ is associative. Namely, the equality $(x \star y) \star z = x \star (y \star z)$ holds for non-negative integers $x, y, z$ less than or equal to $1\,000\,000\,000$. This value is simply denoted by $x \star y \star z$.

Anna planned to play a game with Bruno. She asked him to guess the operation $\star$. She showed $N$ integers $A_0, A_1, \dots, A_{N-1}$ to him. She gave to him a number of queries of the following form: “What is the value of $A_L \star A_{L+1} \star \cdots \star A_R$?”

Bruno said it is difficult to play this game without hints. Anna decided to give hints to him. Each hint is given as follows: he will choose $x, y$ to ask the value of $x \star y$, and she will tell him the value of $x \star y$. He can ask for hints when the integers $A_0, A_1, \dots, A_{N-1}$ are given in the beginning of the game. He can also ask for hints when she gives a query to him. Of course, he would like to reduce the number of hints. Because he would like to behave as if he knows almost everything about the operation $\star$, he would especially like to reduce the number of hints after a query is given to him.

Task

Write a program which implements Bruno’s strategy to ask for hints and answer Anna’s queries correctly.

Implementation Details

You should write a program which implements the strategy to ask for hints and answer Anna’s queries. Your program should include the header file secret.h by #include "secret.h".

Your program should implement the following procedures.

• void Init(int N, int A[])

  This procedure is called only once in the beginning. The parameter $N$ is the number $N$ of the integers shown by Anna. The parameter $A$ is an array of length $N$. The elements $A[0], A[1], \dots, A[N-1]$ are the integers $A_0, A_1, \dots, A_{N-1}$ shown by her.

• int Query(int L, int R)

  This procedure is called when Anna gives a query to Bruno. This means she is asking the value of $A_L \star A_{L+1} \star \cdots \star A_R$ ($0 \leq L \leq R \leq N - 1$).

  This procedure should return the value of $A_L \star A_{L+1} \star \cdots \star A_R$.

The following procedure can be called in your program.

• int Secret(int X, int Y)

  This procedure is called when Bruno asks for a hint. This means he is asking about the value of $X \star Y$. The parameters $X$ and $Y$ should be integers $X$ and $Y$ satisfying $0 \leq X \leq 1\,000\,000\,000$ and $0 \leq Y \leq 1\,000\,000\,000$. If this procedure is called with parameters not satisfying this condition, your program is considered as Wrong Answer [1] and terminated.

  This procedure returns the value of $X \star Y$.

Compilation and Test Run

You can download an archive file from the contest webpage which contains a sample grader to test your program. The archive file also contains a sample source file of your program.

A sample grader consists of one source file which is either grader.c or grader.cpp. For example, if your program is secret.c or secret.cpp, you run the following commands to compile your program.

• C

  gcc -O2 -std=c11 -o grader grader.c secret.c -lm
  

• C++

  g++ -O2 -std=c++11 -o grader grader.cpp secret.cpp
  

When the compilation succeeds, the executable file grader is generated.

Note that the actual grader is different from the sample grader. The sample grader will be executed as a single process, which will read input data from the standard input and write the results to the standard output.

Specification of the sample grader

The sample grader assumes that Anna’s secret binary operation $\star$ is $x \star y = \min\left\{x + 2\left\lfloor \frac{y}{2} \right\rfloor, 1\,000\,000\,000\right\}$. Here, $\lfloor r \rfloor$ denotes the largest integer less than or equal to $r$. Note that this is different from the behavior of the actual grader.

Input Format

The sample grader reads the following data from the standard input.

• The first line contains an integer $N$, the number of the integers shown by Anna.
• The second line contains space separated integers $A_0, A_1, \dots, A_{N-1}$, the integers shown by Anna.
• The third line contains an integer $Q$, the number of queries given by Anna.
• The $(j+1)$-st line ($0 \leq j \leq Q - 1$) of the following $Q$ lines contains space separated integers $L_j$ and $R_j$ ($0 \leq L_j \leq R_j \leq N - 1$). This means, in the $(j+1)$-st query, Anna asks the value of $A_{L_j} \star A_{L_j+1} \star \cdots \star A_{R_j}$.

Output Format

When the program terminates successfully, the sample grader writes to the standard output the values returned by Query one per line. It also writes the following information to the standard error.

• If your program is considered as Wrong Answer [1], it writes “Wrong Answer [1]”. (The quotation mark is not written actually.)
• If your program is not considered as Wrong Answer [1], it writes the number of calls to Secret in the procedure Init, and the maximum number of calls to Secret in each call to the procedure Query.

Hint

Sample interaction

Here is a sample input for the sample grader and examples of interactions between the procedures. Note that the following return values are correct if the sample grader is used.

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

Call	Return
Init(8, [1, 4, 7, 2, 5, 8, 3, 6])	None
Query(0, 3)	13
Query(1, 7)	32
Query(5, 5)	8
Query(2, 4)	13

The procedure Secret can be called in the procedure Init or the procedure Query. For example, when Secret(4, 7) is called, the return value is 10 because $4 \star 7 = 10$ if the sample grader is used.

The value of $1 \star 4 \star 7 \star 2$ is asked in the first query. Since

$$1 \star 4 \star 7 \star 2 = (1 \star (4 \star 7)) \star 2 = (1 \star 10) \star 2 = 11 \star 2 = 13$$

holds if the sample grader is used, the procedure Query should return 13.

Constraints

All input data satisfy the following conditions.

• $1 \leq N \leq 1000$.
• $0 \leq A_i \leq 1\,000\,000\,000$ ($0 \leq i \leq N - 1$).
• The number of calls to Query is less than or equal to $10\,000$.

Grading

The score will be given to your program if your program terminates successfully for each test case, it is not considered as Wrong Answer [1], and it returns the correct value for each call to Query.

Your score is calculated as follows.

(1) Your score is 100 if the following two conditions are satisfied for each test case:

• In Init, the number of calls to Secret is less than or equal to 8000.

• In each call to Query, the number of calls to Secret is less than or equal to 1.

(2) Your score is 30 if your program does not satisfy (1), and the following two conditions are satisfied:

• In Init, the number of calls to Secret is less than or equal to 8000.

• In each call to Query, the number of calls to Secret is less than or equal to 20.

(3) Your score is 6 if your program does not satisfy (1) or (2).