一天 rin 来到了一个遥远的都市。这个都市有 n 个建筑，编号从 1 到 n，其中市中心编号为 1，这个都市有 m 条双向通行的街道，每条街道连接着两个建筑，其中某些街道首尾相连连接成了一个环。

rin 通过长时间的走访，已经清楚了这个都市的两个特点：

1. 从市中心出发可以到达所有的建筑物。
2. 任意一条街道最多存在与一个简单环中。令 rin 心花怒放的是，每个建筑物都会有拉面售卖。拉面有很多不同的种类，但对于 rin 而言只有油腻程度的不同，因此我们把油腻程度相同的拉面看做同一种拉面。

由于不同建筑物的拉面的油腻程度可能不同，我们用一个正整数来表示拉面的油腻程度。

要知道，拉面可是 rin 的最爱，但是现在到了下班高峰期，都市的交通变得非常的堵塞。 rin 只能通过没有被堵死的街道通行，去品尝所在建筑物的拉面。

现在 rin 想知道，如果她正在编号为 x 的建筑物，那么在从市中心到 x 的所有简单路径经过的街道都被堵死的情况下，rin 可以品尝到的拉面中（注意没有出现的拉面是不能算在里面的）：

1. 油腻程度 \leq y 且品尝次数为奇数次的拉面有多少种？
2. 油腻程度 \leq y 且品尝次数为偶数次的拉面有多少种？

第一行两个正整数 n, m，含义如题所示。

第二行一共 N 个正整数，第 i 个数 A_i 表示第 i 个建筑物出售的拉面的油腻程度。

接下来 M 行，每行两个正整数 x, y，表示在建筑物 x, y 之间有一条双向通行的街道。数据保证 1 \leq x < y \leq N。

接下来一行一个正整数 Q，表示询问个数。

接下来 Q 行每行三个非负整数 ty, x, y，ty=0 时表示询问偶数，ty=1 表示询问奇数。

N \leq 100000, M \leq 150000, Q \leq 100000, A_i \leq 10^6。

提示：请注意数据范围中的 \leq，特殊条件中提到的??均为询问中的 y，对于所有的数据，有 y \leq 10^6。

一共 Q 行，对于每个询问输出一个答案。

河南省选