受伟大画家 Picowso 的启发，Vera 决定创作属于她自己的杰作。她拥有一个空白的画布，可以建模为一个无限大的二维坐标平面。Vera 喜欢 2 的幂（$1, 2, 4, 8, 16, \dots$），并会以 2 的幂作为步长，以重复的方式在画布上绘制一些点。

Vera 将进行 $N$ 次绘制。第 $i$ 次绘制由三个整数 $x_i, y_i, v_i$ 描述。令 $a_i$ 为不超过 $x_i$ 的最大 2 的幂，令 $b_i$ 为不超过 $y_i$ 的最大 2 的幂。Vera 会在所有形式为 $(x_i + a_i p, y_i + b_i q)$ 的点上添加颜色为 $v_i$ 的颜料滴，其中 $p, q$ 为非负整数。一个点上可能存在多个颜料滴，也可能存在多个相同颜色的颜料滴。

随后，Vera 会提出 $Q$ 个问题。对于第 $j$ 个问题，她想知道点 $(r_j, c_j)$ 处的颜色。该点的颜色等于该点上所有颜料滴颜色之和。如果某点上没有颜料滴，则该点的颜色为 0。

作为她的艺术助手，你需要回答 Vera 的问题。

输入格式

第一行包含两个整数 $N, Q$，由一个空格分隔（$1 \le N, Q \le 2 \cdot 10^5$）。

接下来的 $N$ 行，每行包含三个由空格分隔的整数 $x_i, y_i, v_i$，表示颜色为 $v_i$ 的颜料滴（$1 \le i \le N; 1 \le v_i \le 10\,000; 1 \le x_i, y_i \le 10^{18}$）。

接下来的 $Q$ 行，每行包含两个由空格分隔的整数 $r_j, c_j$，表示关于点 $(r_j, c_j)$ 的 $Q$ 个问题（$1 \le j \le Q; 1 \le r_j \le 10^{18}; 1 \le c_j \le 10^{18}$）。

对于 25 分中的 5 分，$N, Q \le 2000$。

对于另外 25 分中的 5 分，$y_i = 1$（$1 \le i \le N$）。

对于另外 25 分中的 5 分，$N, Q \le 10^5$ 且 $1 \le r_j, c_j \le 10^9$（$1 \le j \le Q$）。

输出格式

输出共 $Q$ 行。第 $j$ 行（$1 \le j \le Q$）应包含一个整数，即点 $(r_j, c_j)$ 处的颜色。

样例

输入 1

5 6
1 2 1
3 4 2
4 5 3
6 3 4
7 1 5
2 6
7 8
5 9
11 2
10 7
4 5

输出 1

1
8
0
6
4
3

说明 1

令颜色 1, 2, 3, 4, 5 分别为红、蓝、绿、橙、紫。 令 $p, q$ 为非负整数，则： 点 $(1 + p, 2 + 2q)$ 有一个红色颜料滴。 点 $(3 + 2p, 4 + 4q)$ 有一个蓝色颜料滴。 点 $(4 + 4p, 5 + 4q)$ 有一个绿色颜料滴。 点 $(6 + 4p, 3 + 2q)$ 有一个橙色颜料滴。 * 点 $(7 + 4p, 1 + q)$ 有一个紫色颜料滴。

从 $(0, 0)$ 到 $(11, 11)$ 的绘画情况如下所示：

我们可以看到： $(2, 6)$ 有一个红色颜料滴，因此颜色为 1。 $(7, 8)$ 有红、蓝、紫三个颜料滴，因此颜色为 $1 + 2 + 5 = 8$。 $(5, 9)$ 没有颜料滴，因此颜色为 0。 $(11, 2)$ 有红、紫两个颜料滴，因此颜色为 $1 + 5 = 6$。 $(10, 7)$ 有一个橙色颜料滴，因此颜色为 4。 $(4, 5)$ 有一个绿色颜料滴，因此颜色为 3。