#2752. 「CCO 2017」Vera 与现代艺术

内存限制:256 MiB 时间限制:4000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: Mingqi_H

题目描述

译自 CCO 2017 Day1 「Vera and Modern Art

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

Vera 将会染 NNN 次,第 iii 次染色可以用三个整数 xi, yi, vix_i,\, y_i,\, v_ixi,yi,vi 描述。令 aia_iai 为最大的不大于 xix_ixi222 的整数次幂, bib_ibi 为最大的不大于 yiy_iyi222 的整数次幂, Vera 会用第 viv_ivi 种颜色在所有坐标满足 (xi+aip, yi+biq)(x_i + a_ip,\, y_i + b_iq)(xi+aip,yi+biq) 的点上染色(p, qp,\, qp,q 为非负整数)。一个点可以被不同的颜色分别染多次,也可以被同种颜色重复染多次,一个点的颜色为所有染过这个点的颜色之和。

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

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

输入格式

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

接下来 NNN 行,每行三个空格隔开的整数 xi, yi, vix_i,\, y_i,\, v_ixi,yi,vi,表示用第 viv_ivi 种颜色进行题目中的染色操作,参数为 xix_ixiyiy_iyi

再接下来 QQQ 行,每行两个空格隔开的整数 rj, cjr_j,\, c_jrj,cj,表示询问点 (rj, cj)(r_j,\, c_j)(rj,cj) 的颜色。

输出格式

输出共有 QQQ 行,每行一个整数,第 jjj 行的整数表示点(rj, cj)(r_j,\, c_j)(rj,cj) 的颜色。

样例

样例输入

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, 51,\, 2,\, 3,\, 4,\, 51,2,3,4,5 分别为红色、蓝色、绿色、橙色和紫色。

p, qp,\, qp,q为非负整数,则:

  • 坐标为 (1+p, 2+2q)(1 + p,\, 2 + 2q)(1+p,2+2q) 的点被染成了红色;
  • 坐标为 (3+2p, 4+4q)(3 + 2p,\, 4 + 4q)(3+2p,4+4q) 的点被染成了蓝色;
  • 坐标为 (4+4p, 5+4q)(4 + 4p,\, 5 + 4q)(4+4p,5+4q) 的点被染成了绿色;
  • 坐标为 (6+4p, 3+2q)(6 + 4p,\, 3 + 2q)(6+4p,3+2q) 的点被染成了橙色;
  • 坐标为 (7+4p, 1+q)(7 + 4p,\, 1 + q)(7+4p,1+q) 的点被染成了紫色;

(0, 0)(0,\, 0)(0,0)(11, 11)(11,\, 11)(11,11) 的坐标纸如图所示:

我们可以发现:

  • (2, 6)(2,\, 6)(2,6) 被染成了红色,所以它的颜色为 111
  • (7, 8)(7,\, 8)(7,8) 被染成了红色、蓝色和紫色,所以它的颜色为 1+2+5=81 + 2 + 5 = 81+2+5=8
  • (5, 9)(5,\, 9)(5,9) 没有被染色,所以它的颜色为 000
  • (11, 2)(11,\, 2)(11,2) 被染成了红色和紫色,所以它的颜色为 1+5=61 + 5 = 61+5=6
  • (10, 7)(10,\, 7)(10,7) 被染成了橙色,所以它的颜色为 444
  • (4, 5)(4,\, 5)(4,5) 被染成了绿色,所以它的颜色为 333

数据范围与提示

对于 20%20\%20% 的数据, N, Q⩽2000N,\, Q\leqslant 2000N,Q2000
对于另外 20%20\%20% 的数据, yi=1(1⩽i⩽N)y_i = 1(1\leqslant i\leqslant N)yi=1(1iN)
对于另外 20%20\%20% 的数据, N, Q⩽105N,\, Q\leqslant 10^5N,Q1051⩽rj, cj⩽109(1⩽j⩽Q)1\leqslant r_j,\, c_j\leqslant 10^9(1\leqslant j\leqslant Q)1rj,cj109(1jQ)
对于全部的数据, 1⩽N, Q⩽2⋅1051\leqslant N,\, Q\leqslant 2\cdot 10^51N,Q2105i⩽i⩽N; 1⩽vi⩽10 000; 1⩽xi, yi⩽1018i\leqslant i\leqslant N;\, 1\leqslant v_i\leqslant 10\, 000;\, 1\leqslant x_i,\, y_i\leqslant 10^{18}iiN;1vi10000;1xi,yi10181⩽j⩽Q; 1⩽rj⩽1018; 1⩽cj⩽10181\leqslant j\leqslant Q;\, 1\leqslant r_j\leqslant 10^{18};\, 1\leqslant c_j\leqslant 10^{18}1jQ;1rj1018;1cj1018

请注意在 LibreOJ 上共有 555 个子任务,其中第一个子任务为样例。