花花是个爱动脑子的孩子，在她的生日的时候，她的爸爸给她准备了个礼物。但是，她的爸爸并不想让她轻易得到礼物，他把礼物放在了一个箱子里面，只有输入正确的密码才能打开箱子，而她的爸爸告诉了她这个礼物该怎么得到：

他们所在的城市可以看成有n个点，m条边的无向图，每个点上有一个权值ai，每条边有一个权值w。

我们定义两个点x，y关于k联通当且仅当存在一条从x到y的路径，满足这条路径上的w的最大值小于等于k。

而密码就是和节点x关于k联通的所有节点的ai构成的集合B的summex。

我们定义一个可重复数集B的summex为无法用B集合的子集的和表示的正整数的最小值。

例如，B= {1, 1, 3, 7}，他能表示0{}，1{1}，2{1,1}，3{3}，4{1+3}，5{1+1+3}，但是他不能表示6，所以summex{1, 1, 3, 7}是6。

由于她的爸爸有点健忘，他可能会记错，所以会有多组（Q组）询问。对于每组询问，你都要给一个正确的答案。

为了提高难度，我们会对数据加密，对于一个给定的数S，解密输入中的C++代码是：

inline void decode(int &x, int &y){

x = (lstans & S) ^ x;

y = (lstans & S) ^ y;

}

其中的lstans是上次询问的答案。

第一行四个整数分别表示n,m,Q,S。

接下来一行n个数，第i个数表示ai。

接下来m行，每行三个数x y w，表示有一条边(x,y)，权值是w。

接下来Q行，每行两个整数x k，表示加密前的x和k。

Q行，每行一个整数表示答案。

样例输入

【样例输入1】

5 5 5 0

1 2 2 4 5

1 3 1

2 3 4

3 5 2

2 4 3

2 5 5

1 1

1 2

2 3

1 4

5 2

样例输出

【样例输出1】

4

4

1

15

4