middle

给定一个长度为 $n$ 的序列。对于任意长度为 $m$ 的序列，将其元素按从小到大的顺序排序，得到下标从 $0$ 开始的序列 $b$，则其中位数定义为 $b[\lfloor m/2\rfloor]$。

现给定一个长度为 $n$ 的序列 $s$，下标从 $0$ 开始。你需要回答 $Q$ 次询问。每次询问给定 $a,b,c,d$，满足 $a<b<c<d$。你可以在区间 $[a,b]$ 中选择子序列的左端点，并在区间 $[c,d]$ 中选择子序列的右端点。求所有满足条件的连续子序列中，中位数的最大值。

为了强制在线处理，输入中的询问需要根据上一次询问的答案进行解码，具体方式见输入格式。

输入格式

第一行包含一个整数 $n$，表示序列长度。

接下来 $n$ 行，每行包含一个整数，按顺序给出序列 $s$ 中的元素。

接下来一行包含一个整数 $Q$，表示询问次数。

随后 $Q$ 行，每行包含四个整数 $a,b,c,d$。设上一次询问的答案为 $x$；如果当前询问是第一次询问，则令 $x=0$。

构造数组：

$$q=\{(a+x)\bmod n,\ (b+x)\bmod n,\ (c+x)\bmod n,\ (d+x)\bmod n\}。$$

将 $q$ 从小到大排序后，当前询问真正的参数为：

$$a=q[0],\quad b=q[1],\quad c=q[2],\quad d=q[3]。$$

输入保证解码后的参数满足 $a<b<c<d$。

输出格式

输出 $Q$ 行，第 $i$ 行包含第 $i$ 次询问的答案。

样例输入

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0

样例输出

271451044
271451044
969056313

数据范围

• $n\le 20000$；
• $Q\le 25000$。

来源与许可

本题题面与测试数据整理自 BZOJ 2653。

样例 1

输入

5
170337785
271451044
22430280
969056313
206452321
3
3 1 0 2
2 3 1 4
3 1 4 0

输出

271451044
271451044
969056313