在一个几乎无限大的实验区域内，一项将激光转化为通用可用能源的超大规模项目已经启动，该区域内布满了激光放大玻璃板。

实验通过在一个房间内放置激光发射器来进行。随后，在房间坐标 $(x_i, y_i)$ 处放置了 $N$ 个激光接收器；每个房间在相邻房间之间共享垂直和水平侧的玻璃板。

• 当激光穿过每块垂直玻璃板时，激光强度增加 $A$ 个单位。
• 当激光穿过每块水平玻璃板时，激光强度增加 $B$ 个单位。

我们可以选择仅激活 1 个激光接收器，当激光在该接收器处停止时，它会进一步将激光强度增加 $c_i$ 个单位，从而产生与最终激光强度成比例的能量。为防止实验造成意外损坏，所有设备必须放置在房间中心，激光必须以水平或垂直轨迹开始，且激光路径必须在激活的激光接收器处结束。

此外，项目管理员提供了一个 L 型反射器，用于将激光的轨迹从水平变为垂直，或反之亦然。你想要进行 $Q$ 次模拟测试，以提供在给定激光起始坐标 $(s_i, t_i)$ 的情况下，最小可能激光强度的相关信息；你的任务是计算出最终的激光强度。

输入格式

第一行包含四个整数 $N, Q, A, B$ ($0 \le A, B \le 10^9, 1 \le N, Q \le 100\,000$)，分别表示激光接收器的数量、模拟次数，以及垂直和水平玻璃板的放大倍率。

接下来的 $N$ 行包含 $x_i, y_i, c_i$ ($0 \le x_i, y_i \le 10^9, 0 \le c_i \le 10^{18}$)，表示笛卡尔坐标系中激光接收器的坐标及其激光放大倍率。

接下来的 $Q$ 行包含 $s_i, t_i$ ($0 \le s_i, t_i \le 10^9$)，表示每次模拟中笛卡尔坐标系内激光发射器的起始坐标。

输出格式

输出 $Q$ 行，每行包含一个整数，表示该次模拟中最小可能的激光强度。

样例

输入 1

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

输出 1

3
2
7

说明

设红点和蓝点分别为每次模拟中的激光接收器和激光发射器。

对于第一次模拟，L 型反射器可以放置在坐标 $(3,4)$ 处；通过激活第二个接收器，最小最终激光强度为 $1 + 2 + 0 = 3$。

对于第二次模拟，不使用 L 型反射器；通过激活第二个接收器，最小最终激光强度为 $2 + 0 = 2$。

对于第三次模拟，L 型反射器可以放置在坐标 $(1,5)$ 处；通过激活第五个接收器，最小最终激光强度为 $2 + 1 + 1 + 1 + 2 = 7$。