Contest Day 2 - JOI Open Contest

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 \dots \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 \dots \star A_R~ ~(0 \le L \le R \le N - 1)~.

The following procedure can be called by 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 satisfying ~0 \le X \le 1\,000\,000\,000~ and ~0 \le Y \le 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~.

Constraints

All input data satisfy the following conditions.

• ~1 \le N \le 1\,000~.
• ~0 \le A_i \le 1\,000\,000\,000~ ~(0 \le i \le 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 ~8\,000~.
   • 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 ~8\,000~.
   • 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).