背景

    法法塔和wyl8899都喜欢玩游戏。但是每次玩游戏法法塔都被wyl8899虐。

    为了安慰可怜的法法塔,wyl8899决定大发慈悲,修改了一下游戏规则。

描述

    是这样的,这儿有一堆石子排成一列,每次wyl8899让hza选择一个区间进行游戏。游戏嘛,就是采用最普通的规则:两人轮流操作,每次选择一堆石子,取掉不为0的石子数,没法操作者失败。法法塔要做的是这样的:

    我们现在定义一个区间的弱菜值:表示如果法法塔先取石子,而且法法塔第一步取的石子规定是最右边的那堆的话,为了必胜,第一步需要取的石子数。如果没法获胜的话,那么弱菜值就是-1。

    法法塔要选择一个区间[l,r],使得r为wyl8899给定的某个数,l属于[a,b],a,b也是wyl8899给定的,要求这个区间的弱菜值是满足前面的条件中最大。请给出这个最大的弱菜值。

    如果最大弱菜值不为-1,法法塔就会马上取走该区间最右端的石子堆最大弱菜值数量的石子。

输入格式

    第一行一个正整数n,描述了石子的堆数,接下来一行n个数,描述每堆石子的数目。

    接下来一行m,表示将进行要进行m次游戏,每次游戏由三个值刻画,r,a,b。r表示被选定的右端点,[a,b]表示选择的区间的左端点的范围

输出格式

    对于每个询问输出最大的弱菜值。
 

样例输入

样例输入1:
12
662 477 125 483 17 560 232 59 176 928 807 659
5
5 2 5
4 4 4
2 1 2
6 4 6
6 2 3
样例输入2:
7
230 883 456 1020 966 899 610
2
7 1 2
2 1 2
样例输入3:
11
392 808 14 71 393 79 11 74 713 232 142
5
8 3 8
9 5 9
3 1 1
8 2 8
7 4 6

样例输出

样例输出1:
17
483
477
560
-1
样例输出2:
352
883
样例输出3:
74
713
-1
-1
-1

数据范围与约定

    n<=100000,m<=10000,每堆的石子数<=1000。