3939. Vera 与现代艺术

【题目描述】

 在受到大画家毕加索的启发后， Vera 决定创造她的杰作。她有一张可以被简化成无限大的二维平面的画布。 Vera 喜欢 $2$ 的整数次幂 $(1,\, 2,\, 4,\, 8,\, 16,\, \ldots)$，并且将以 $2$ 的整数幂为步长给一些点染色。

 Vera 将会染 $N$ 次，第 $i$ 次染色可以用三个整数 $x_i,\, y_i,\, v_i$ 描述。令 $a_i$ 为最大的不大于 $x_i$ 的 $2$ 的整数次幂， $b_i$ 为最大的不大于 $y_i$ 的 $2$ 的整数次幂， Vera 会用第 $v_i$ 种颜色在所有坐标满足 $(x_i + a_ip,\, y_i + b_iq)$ 的点上染色（$p,\, q$ 为非负整数）。一个点可以被不同的颜色分别染多次，也可以被同种颜色重复染多次，一个点的颜色为所有染过这个点的颜色之和。

 接下来 Vera 将提出 $Q$ 个问题。对于第 $j$ 个问题，她希望知道坐标为 $(r_j,\, c_j)$ 的点是什么颜色。如果一个点没有被染过色，这个点的颜色就为 $0$。

 因为你被迫做 Vera 的助手，你不得不回答 Vera 的问题。

【输入格式】

第一行包括两个整数 $N,\, Q$ ，用一个空格分隔。 

接下来 $N$ 行，每行三个空格隔开的整数 $x_i,\, y_i,\, v_i$，表示用第 $v_i$ 种颜色进行题目中的染色操作，参数为 $x_i$ 和 $y_i$。 

再接下来 $Q$ 行，每行两个空格隔开的整数 $r_j,\, c_j$，表示询问点 $(r_j,\, c_j)$ 的颜色。

【输出格式】

输出共有 $Q$ 行，每行一个整数，第 $j$ 行的整数表示点 $(r_j,\, c_j)$ 的颜色。

【样例输入】

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
8
0
6
4
3

【样例说明】

令颜色 $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$。

【数据规模与约定】

对于 $20\%$ 的数据， $N,\, Q\le 2000$； 

对于另外 $20\%$ 的数据， $y_i = 1(1\le i\le N)$； 

对于另外 $20\%$ 的数据， $N,\, Q\le 10^5$ 且 $1\le r_j,\, c_j\le 10^9(1\le j\le Q)$。

对于全部的数据，$ 1\le N,\, Q\le 2\cdot 10^5，i\le i\le N;\, 1\le v_i\le 10\, 000;\, 1\le x_i,\, y_i\le 10^{18}$，$1\le j\le Q;\, 1\le r_j\le 10^{18};\, 1\le c_j\le 10^{18}$。

【来源】

在此键入。