Migrated from Lutece 1649 暴力随便过的数据结构大水题

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

$AutSky\_JadeK$今天又给各位$dalao$带来了一道数据结构大水题！他有一个神秘的序列，他会多次询问在某个区间内出现次数第$k_1$少的权值是多少，可能多个不同的权值出现次数均为第$k_1$少，输出其中第$k_2$小的。
秦××$dalao$听说以后，瞬间秒了这道题，那么同样聪明的你能不能做出来，拿到本周的奖励呢？

保证输入合法，注意内存限制。

例如：对于一个区间而言(当然不一定是有序的):
$1,2,3,4,5,5,6,6,7,7,7,7,8,8,8,8,9,9,9,9,10,10,10,10,11,11,11,11,11,11,12,12,12,12,12,12,12,12,12,12$

若$k_1=3$，$k_2=2$，代表询问这个区间里出现次数第$3$少的权值中第$2$小的，则应该输出$8$。
若$k_1=5$，$k_2=1$，代表询问这个区间里出现次数第$5$少的权值中第$1$小的，则应该输出$12$。
若$k_1=1$，$k_2=3$，代表询问这个区间里出现次数第$1$少的权值中第$3$小的，则应该输出$3$。

Input

第一行包括一个整数$n$，代表序列的长度。
第二行包括$n$个整数$a_1...a_n$，代表该序列。
第三行包括一个整数$m$，代表询问的次数。
接下来$m$行，每行包括$4$个整数$l,r,k_1,k_2$，询问$a_l...a_r$中出现次数第$k_1$少的权值中第$k_2$小的。

Output

对于每个询问，仅输出一行，包括一个整数，代表你的回答。

Samples

10
3 6 6 8 3 10 1 6 5 6
10
4 7 1 2
5 7 1 1
5 6 1 2
2 6 2 1
8 9 1 1
6 9 1 2
1 2 1 1
1 4 2 1
5 7 1 3
2 6 1 3

3
1
10
6
5
5
3
6
10
10

20
14 18 19 11 15 13 9 10 5 13 3 14 14 12 12 8 4 17 8 8
20
8 9 1 2
6 19 2 2
7 11 1 1
8 12 1 4
9 13 2 1
14 15 1 1
6 11 1 4
5 7 1 3
8 18 2 1
2 4 1 3
4 16 1 1
5 14 1 5
13 14 1 2
15 15 1 1
12 17 1 1
3 12 2 1
14 17 1 1
6 13 1 4
11 11 1 1
2 4 1 3

10
12
3
13
14
12
10
15
12
19
3
12
14
12
4
13
4
10
3
19

Note

$1{\leq}n{\leq}40000$，
$1{\leq}a_i{\leq}n (1{\leq}i{\leq}n)$，
$1{\leq}m{\leq}40000$，
$1{\leq}l{\leq}r{\leq}n$，
保证$k_1$,$k_2$合法。

Resources

每周一题 div1 By AutSky_JadeK 原创