题目背景

3s，256MB

题目描述

很久以前，在萨满之岛上，所有人都住在一个如天一样高的豆茎上。每位萨满都有一个独一无二的编号，编号的范围在 $0$ 和 $N-1$ 之间。第 $i$ 位萨满居住的高度用 $H_i$ 表示。定义两位萨满间的距离为其高度差的绝对值。

所有的萨满之间本来和谐共处，直到一天权力药水的配方被盗。为了掩盖他的行径，那位小偷给整座岛施加了诅咒，大多数居民不再彼此信任了。

虽然情况非常复杂，但是经过调查，某组织还是获得了如下信息：

• 诅咒刚生效时，所有的萨满停止彼此信任。
• 诅咒本身是不稳定的，在每天将要结束时（准确来说是午夜），某一对萨满将会建立信任或是停止信任。
• 不幸地是，一位萨满在任意时刻最多信任 $D$ 位萨满。

该组织还重建了萨满间的信任变化日志，该日志记录了在每个半夜，哪对萨满的信任关系发生了变化（从不信任到信任，或是从信任到不信任）。

该组织的成员相信，小偷还向一位邪恶的萨满通过隔空传话的方式泄露了配方。为了避免被发现，他们俩都各自拜访了一位信任的萨满的家，在拜访的过程中，小偷透过窗户向邪恶的萨满泄露配方。需要注意的是，那位信任的朋友当时不必在家中，事实上，两位萨满可能互相前往对方的家。毕竟萨满都很奇怪。

幸运的是，因为萨满们的听力有限，声音并不能传出太远，这意味着两位朋友（小偷的朋友和邪恶的萨满的朋友）之间的距离必须尽可能近。

现在该组织决定让你来协助调查。他们想要验证自己的猜想：当小偷为 $x$，邪恶的萨满为 $y$，泄露配方的日子为 $v$ 时，隔空传话的声音需要行进的最小值是多少？也即，你需要在第 $v$ 天时，在 $x$ 信任的所有萨满中找到一位萨满 $x'$，在 $y$ 信任的所有萨满中找到一位萨满 $y'$，使 $x'$ 和 $y'$ 间的距离最小。

你已经获得了求出答案所需的所有信息，但你需要实时回答每一组询问。

输入格式

仅提供 IO 交互。

输入第一行包含四个整数 $N,D,U,Q$，分别代表萨满的数量，一位萨满最多信任的朋友数，日志包含的天数，以及需要回答的询问数。

下一行包含 $N$ 个整数，两两间以一个空格隔开。其中第 $i$ 个整数代表第 $i-1$ 只萨满居住的高度 $H_{i-1}$。

接下来 $U$ 行，第 $i$ 行包含两个整数 $A_i,B_i$，代表编号为 $A_i$ 和 $B_i$ 的萨满在第 $i-1$ 天结束的时候，他们之间的信任状态发生了变化。即，如果 $A_i$ 和 $B_i$ 在第 $i-1$ 天互相信任，则他们自第 $i$ 天起不再互相信任，反之同理。

接下来你需要回答 $Q$ 组询问。询问必须实时回答，即你必须回答完一组询问后才能读入下一组询问。

每组询问包含三个整数 $x,y,v$，代表小偷为 $x$，邪恶的萨满为 $y$，泄露配方的日子为第 $v$ 天。

输出格式

对于每组询问，你需要在第 $v$ 天时，在 $x$ 信任的所有萨满中找到一位萨满 $x'$，在 $y$ 信任的所有萨满中找到一位萨满 $y'$，使 $x'$ 和 $y'$ 间的距离最小，并输出这个最小值。

特别地，

• 若存在一位萨满同时被 $x$ 和 $y$ 信任，输出 $0$。
• 若 $x$ 或 $y$ 在第 $v$ 天无信任的朋友，输出 $1000000000$（$10^9$）。

在回答完一组询问后，你需要立刻刷新缓冲区。

对于 C++ 选手，可以通过 fflush(stdout); 或 cout.flush() 来刷新缓冲区。

6 5 11 4
2 42 1000 54 68 234
0 1
2 0
3 4
3 5
3 5
1 3
5 3
0 5
3 0
1 3
3 5
0 3 4
3 0 8
0 5 5
3 0 11

26
0
1000000000
14

提示

样例解释

下面是询问的情况：

下面是每一天时信任关系的变化情况：

子任务

所有数据均满足：$2 \leq N \leq 10^5$，$1 \leq D \leq 500$，$0 \leq U \leq 2 \times 10^5$，$1 \leq Q \leq 5 \times 10^4$。

各子任务的约束条件如下：