Pigetown 是一个拥有 $n$ 个路口和 $m$ 条双向道路的城市。Pigetown 即将举办一场大型赛车活动。城市中有 $k$ 种赛道类型，每条道路都被视为一种特定类型的赛道。

在比赛中，每位参赛者需要选择一个整数 $i$（满足 $1 \le i \le q$），从路口 $S_i$ 出发，访问每种类型的赛道次数相同，并最终到达路口 $T_i$ 以完成比赛。

Grammy 想知道对于每一个整数 $i$，是否有可能完成比赛。请编写一个程序来帮助她解决这个问题。

输入格式

第一行包含 4 个整数 $n, m, k, q$（$1 \le n, m, q \le 200\,000$，$1 \le k \le 30$），分别表示路口数量、道路数量、赛道类型数量以及所选整数 $i$ 的上限。

接下来的 $m$ 行，每行包含 3 个整数 $u, v, t$（$1 \le u, v \le n$，$1 \le t \le k$），表示在路口 $u$ 和路口 $v$ 之间有一条类型为 $t$ 的双向道路。

接下来的 $q$ 行，每行包含 2 个整数 $S_i, T_i$（$1 \le S_i, T_i \le n$），表示起点和终点的一种可能组合。

输出格式

输出 $q$ 行。

在第 $i$ 行中，如果选择整数 $i$ 可以完成比赛，则输出 “Yes”，否则输出 “No”（不含引号）。

样例

输入 1

7 9 3 4
1 2 1
2 3 1
3 1 2
1 4 3
5 6 2
6 7 1
6 7 3
7 7 2
5 5 1
6 7
1 4
2 4
2 5

输出 1

Yes
No
Yes
No