問題文

$N$ 要素の整数列 $A = (A_1, A_2, \dots, A_N)$ と、整数 $K, L$ が与えられます。

以下の形式のクエリが $Q$ 個与えられるので、それぞれについて答えを求めてください。

• 整数 $l, r$ が与えられる。整数列 $B = (A_l, A_{l + 1}, \dots, A_r)$ の $L$ 番目の $K$ 番目の数 を求めよ。

入力

入力は以下の形式で標準入力から与えられる。

$N$ $K$ $L$  
$A_1$ $A_2$ $\cdots$ $A_N$  
$Q$  
$\text{Query}_1$  
$\text{Query}_2$  
$\vdots$  
$\text{Query}_Q$ 

ただし、$\text{Query}_i$ ($1≤i≤Q$) は $i$ 個目のクエリを表す。各クエリは以下の形式で与えられる。

$l$ $r$

• 入力は全て整数
• $1≤N≤2.5\times 10^3$
• $1≤K≤N$
• $1≤L$
• $1≤A_i≤N$ ($1≤i≤N$)
• $1≤Q≤2.5\times 10^5$
• 各クエリについて、$1≤l≤r≤N,\ \ r - l + 1≥K,\ \ L≤\frac{(r-l-K+2)(r-l-K+3)}{2}$

また、$N = 5000$ の evil ケースが存在する。このテストケースは提出結果には影響しない。

出力

$Q$ 行出力せよ。$i$ 行目 ($1≤i≤Q$) には $i$ 個目のクエリに対する答えを出力せよ。

サンプル

4 3 2
3 1 2 4
1
1 4

3

4 3 1
3 1 2 4
3
1 3
2 4
1 4

3
4
3

15 4 6
8 5 6 6 2 1 14 8 9 3 5 4 2 1 7
12
1 6
4 15
7 15
5 13
3 13
3 8
6 11
6 13
2 12
3 11
8 14
1 7

8
3
4
5
4
14
14
5
5
6
5
6

出典