비밀

Anna는 비밀 이항 연산 ★를 고안했다. 1 000 000 000 이하의 음이 아닌 정수 x, y에 대해 1 000 000 000 이하의 음이 아닌 정수 x ★ y가 정해진다. 이 연산 ★는 결합법칙을 만족한다. 즉, 1 000 000 000 이하의 음이 아닌 정수 x, y, z에 대해 (x ★ y) ★ z = x ★ (y ★ z)가 성립한다. 이 값을 간단히 x ★ y ★ z로 쓴다.

Anna는 Bruno와 게임을 하려고 했다. 그녀는 그에게 연산 ★를 맞혀 달라고 했다. 그녀는 N개의 정수 A0, A1, . . . , AN−1을 그에게 보여 주었다. 그리고 다음과 같은 형태의 질의를 여러 개 그에게 주었다. “AL ★ AL+1 ★ · · · ★ AR의 값은 무엇인가?”

Bruno는 힌트 없이 이 게임을 하기 어렵다고 말했다. Anna는 그에게 힌트를 주기로 했다. 각 힌트는 다음과 같이 주어진다. 그가 x, y를 골라 x ★ y의 값을 물으면, 그녀가 x ★ y의 값을 알려 준다. 그는 게임 초반에 정수 A0, A1, . . . , AN−1이 주어졌을 때 힌트를 요청할 수 있다. 또한 그녀가 질의를 줄 때도 힌트를 요청할 수 있다. 물론 그는 힌트의 수를 줄이고 싶어 한다. 연산 ★에 대해 거의 모든 것을 아는 것처럼 행동하고 싶어 하므로, 특히 질의를 받은 뒤의 힌트 수를 줄이고 싶어 한다.

Bruno의 전략을 구현하여 힌트를 요청하고 Anna의 질의에 정확히 답하는 프로그램을 작성하시오.

샘플 그레이더는 다음 데이터를 표준 입력에서 읽는다.

• 첫째 줄에는 Anna가 보여 준 정수의 개수 N이 주어진다.
• 둘째 줄에는 Anna가 보여 준 정수 A0, A1, . . . , AN−1이 공백으로 구분되어 주어진다.
• 셋째 줄에는 Anna가 주는 질의의 개수 Q가 주어진다.
• 다음 Q개의 줄 중 (j + 1)번째 줄 (0 ≤ j ≤ Q − 1)에는 Lj와 Rj (0 ≤ Lj ≤ Rj ≤ N − 1)가 공백으로 구분되어 주어진다. 이는 (j + 1)번째 질의에서 Anna가 ALj ★ ALj+1 ★ · · · ★ ARj의 값을 묻는다는 뜻이다.

프로그램이 성공적으로 종료되면, 샘플 그레이더는 Query가 반환한 값을 표준 출력에 한 줄에 하나씩 쓴다. 또한 다음 정보를 표준 오류에 쓴다.

• 프로그램이 Wrong Answer [1]로 판정되면 “Wrong Answer [1]”을 쓴다. (따옴표는 실제로 쓰지 않는다.)
• 프로그램이 Wrong Answer [1]로 판정되지 않으면, Init 프로시저에서 Secret을 호출한 횟수와 Query 프로시저를 호출할 때마다 Secret을 호출한 최대 횟수를 쓴다.

• 1 ≤ N ≤ 1 000.
• 0 ≤ Ai ≤ 1 000 000 000 (0 ≤ i ≤ N − 1).
• Query를 호출한 횟수는 10 000 이하이다.