F-「LAOI-15」Graph_牛客挑战赛81

时间限制：C/C++/Rust/Pascal 10秒，其他语言20秒
空间限制：C/C++/Rust/Pascal 1024 M，其他语言2048 M
64bit IO Format: %lld

题目描述

$\hspace{15pt}$ 对于给定的 $k$ ，定义集合 $a$ 的价值为第 $k$ 小的 $x$ 满足 $x\in \mathbb{N},x\notin a$ 。
$\hspace{15pt}$ 现在，给定一张简单有向图（不保证连通），每个点有一个权值 $V_i$ 。有若干次询问，每次查询编号在 $[l,r]$ 之间的点所能到达的点（可以经过任意多步）的权值的组成的集合的价值。

$\hspace{15pt}$ 保证询问区间按如下方式随机生成：
$\hspace{15pt}$ 首先任意生成一个长为 $q$ 的序列 $p_i\in[1,n]$ （不保证随机），然后对于第 $i$ 组询问，在 $[1,p_i]$ 中等概率随机生成 $l$ ，在 $[p_i,n]$ 中等概率随机生成 $r$ 。

输入描述:

第一行输入四个正整数 ，表示图的节点数、边数、询问次数和定义价值的常数。
第二行输入  个整数 ，第  个整数表示第  个点的权值。
此后  行，第  行两个整数 ，表示第  条边从点  指向点 。
此后  行，第  行两个正整数 ，表示第  次询问的区间。

输出描述:

对于每一次询问，新起一行输出一个整数，表示答案。

示例1

输入

复制

6 7 3 3
0 2 3 4 6 8
1 2
2 3
3 1
3 4
4 5
5 6
6 4
2 4
1 3
4 6

输出

复制

7
7
2

说明

对于这个样例，图的结构如下：



前两次询问可以到达的的点集均为  ，其权值组成的集合为 ，其中没有出现的最小的三个元素分别为 ，故答案为 。
第三次询问可以到达的点集为 ，其权值组成的集合为 ，其中没有出现的最小的三个元素分别为 ，故答案为 。

示例2

输入

复制

7 7 5 2
0 2 3 1 3 5 0
1 2
2 3
3 1
4 5
5 6
5 7
4 7
1 2
3 3
4 6
6 7
3 5

输出

复制

备注:

本题略卡常，请注意常数因子对程序运行效率的影响。