琪琪接下了一份在全世界送面包的奇特工作！

她目前正在穿过赤道上的一组城市。赤道的总长度为 $D$，位置标记为 $0$ 到 $D - 1$。琪琪每次只向正方向移动一步，除非她处于位置 $D - 1$，此时她会回到位置 $0$。

在这 $D$ 个位置中，有 $N$ 个顾客。每个顾客可以用其在赤道上的位置 $d_i$ 以及他们想要的面包类型 $k_i$（介于 $0$ 到 $K - 1$ 之间的数字）来描述。保证每种类型的面包都至少有一个顾客想要。琪琪可以在不移动任何距离的情况下拜访同一位置的多个顾客。

琪琪和她的扫帚

琪琪拥有每一种类型的面包，但由于不同的面包类型是堆叠在一起的，她只能配送她栈顶的那种面包。此外，琪琪只能通过将面包配送给顾客来将其从栈顶移除。

栈中下一个面包的类型总是比上一个面包的类型多 1，除非上一个面包的类型是 $K - 1$，在这种情况下，接下来的面包类型将是 0。更正式地，如果琪琪面包栈顶的面包类型为 $D$，那么下一个面包的类型将是 $(D + 1) \bmod K$。如果在一个位置存在多个符合要求的面包顾客，琪琪可以在不移动的情况下在该位置配送多块面包。

琪琪目前正在考虑 $Q$ 条路线。在第 $q$ 次查询中，她从某个初始位置 $d'_q$ 出发，其栈顶初始面包类型为 $k'_q$，并且她希望总共配送 $n'_q$ 块面包。

对于每次查询，计算琪琪为了配送她期望数量的面包所必须移动的距离。

输入格式

第一行包含 $4$ 个空格分隔的整数 $N$ ($1 \le N \le 10^5$)、$K$ ($1 \le K \le N$)、$D$ ($1 \le D \le 10^9$) 和 $Q$ ($1 \le Q \le 10^5$)。$N$ 表示顾客数量，$K$ 表示面包类型数量，$D$ 表示赤道上的位置数量，$Q$ 表示路线数量。

第二行包含 $N$ 个空格分隔的整数 $d_1, d_2, \dots, d_N$ ($0 \le d_i \le D - 1$)，详细说明顾客的位置。

第三行包含 $N$ 个空格分隔的整数 $k_1, k_2, \dots, k_N$ ($0 \le k_i \le K - 1$)，详细说明每个顾客想要的面包类型。

接下来是 $Q$ 行，每行描述一条路线。每行包含三个空格分隔的整数，分别表示琪琪在这条路线上的起点 $d'_q$ ($0 \le d'_q \le D - 1$)、开始这条路线时她栈顶的面包类型 $k'_q$ ($0 \le k'_q \le K - 1$)，以及她在这条路线中希望配送的面包总数 $n'_q$ ($0 \le n'_q \le K$)。

输出格式

对于每次查询，输出琪琪必须移动的距离。在单独的一行中输出每次查询的答案，顺序与给出的查询顺序相同。

样例

输入样例 1

5 3 10 3
1 3 5 7 9
2 1 2 0 1
6 2 2
8 2 1
0 0 3

输出样例 1

11
3
11