Contest Day 2 - JOI Open Contest

Anna invented a secret binary operation $\star$. For non-negative integers $x$, $y$ less than or equal to $1000000000$, a non-negative integer $x\star y$ less than or equal to $1000000000$ 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 $1000000000$. 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.

• Copy

  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.

• Copy

  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\le L\le R\le N-1)$.

The following procedure can be called by your program.

• Copy

  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 satisfying $0\le X\le 1000000000$ and $0\le Y\le 1000000000$. 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$.

Constraints

All input data satisfy the following conditions.

• $1\le N\le 1000$.
• $0\le A_i\le 1000000000$ $(0\le i\le N-1)$.
• The number of calls to Query is less than or equal to $10000$.

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).