#29 「 摆摊 」

统计

T校的校门口有一条路,这条路上有一些摊位,按照离校门的远近关系标号为$1,2,3,\ldots,n$。

R君打算暑假在这条路上摆摊卖东西。

这些摊位有些已经被占用,有些没有被占用。

R君为了方便生意,需要占用$k$个连续的没有被占用的摊位来摆摊。

R君希望摊位离学校越近越好,所以R君希望占用的$k$个连续摊位的编号越小越好。

现在你得到了一个长度为$m$的序列$a_1,a_2,...,a_m$。

请你回答Q个询问,每次询问独立、之间没有关联,每个询问有两个参数$L$,$R$,问:当$a_L,a_{L+1},...,a_R$这些摊位被占用的时候R君应该选择哪$k$个编号的摊位。

输入格式

第一行四个整数,n,m,Q,k,分别表示摊位的编号范围,a序列的长度,询问次数,需要占用的摊位长度。

第二行m个整数表示a序列。

之后Q行,每行两个整数L,R。

输出格式(注意update)

输出一共Q行,每行k个空格隔开的整数,表示你占用的连续k个摊位,如果没有找到合适摊位请输出k个-1。

update: 考虑到输出量,所以每行只用输出第一个数字即可(参见样例)。

样例数据

input

10 5 15 2
3 1 6 7 5
1 1
1 2
1 3
1 4
1 5
2 2
2 3
2 4
2 5
3 3
3 4
3 5
4 4
4 5
5 5

output

1
4
4
4
8
2
2
2
2
1
1
1
1
1
1

数据规模与约定

$1\le n,m,Q \le 200000, 1 \le L \le R \le m,1 \le a_i \le n, 1\le k \le 10$。

时间限制:1s

空间限制:512MB

Author: zrt