Background

这片大陆上一共有n个城市，m条双向道路，每条道路都有一个体力消耗值。每个城市会属于某个国家。

你每次都会从s号国家出发，尝试环游世界。

一次旅行的精彩程度定义为本次旅行中经过的城市属于多少个不同的国家。

假如你的体力上限为t，那么你无法经过体力消耗值大于t的道路（注意经过道路不会消耗体力,体力上限决定了哪些道路能经过，哪些不能经过）

定义f(t)为：体力上限为t时，一次旅行的最大精彩程度。

给出q次询问，每次询问给出两个整数li,ri，求出$\sum_{t=li}^{ri}f(t)$

Format

Input

第一行5个整数n,m,q,s,opt

如果opt为1，接下来输入M，表示强制在线的模数。

第二行n个整数，分别表示n个城市所属的国家,第i个城市所属的国家为ci

接下来m行，每行三个整数ui,vi,wi 表示一条道路的两端点和体力消耗。

接下来q行，每行两个整数li,ri。

如果opt=1，$li = (li \oplus lastans) \bmod M + 1$ ,$ri = (ri \oplus lastans) \bmod M + 1$，lastans表示上次输出的答案，初始为0, 如果li>ri 那么交换li,ri

Output

对于每个询问输出一个整数表示答案

Samples

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

5
8
7

6 6 3 3 1
1000007
1 1 1 2 2 3
1 6 1
1 2 5
2 3 4
3 6 3
3 4 6
5 6 2
0 2
5 6
9 11

5
8
7

Limitation

对于第一组数据的第一个询问，当t=1,t=2时精彩程度最大为1，当t=3时精彩程度最大为3

对于10%的数据，$n,m,q \leq 10, ci,li,ri \leq 10, opt=0$

对于20%的数据，$n,m,q \leq 100, opt=0$

对于40%的数据，$n,m,q \leq 10^3,opt=0$

对于另外15%的数据，$li=ri \leq 10^9,opt=0$

对于另外15%的数据，$li,ri,wi \leq 10^5,opt=0$

对于100%的数据，$n,m \leq 5 *10^5,q \leq 10^5, ci \leq 500,0\leq wi,li,ri \leq 10^9$