English Statement

题目背景

你知道吗，__int128 皇帝陛下其实非常热爱玩电脑游戏！

这一天，__int128 皇帝的电脑因为跳蚤国的互联网基础设施核心——CloudFlea 服务突然发生爆炸而无法启动。

__int128 皇帝下令搜集全国还能使用的电脑，但是所有的电脑都死机了，最终只找到了 ccz181078 的一台六个状态的图灵机。

但是由于这台图灵机正在运行，所以得等图灵机停机后才能使用。

你需要帮助 __int128 皇帝加速这台图灵机的运算，越快越好！

题目描述

ccz181078 的图灵机里面预先存储了 $n$ 个操作 $x_i,y_i,a_i,b_i,\;1\le i\le n$，图灵机需要处理 $m$ 次查询。

每次查询给定 $l,r,X$，图灵机需要执行：

初始化 $A=1,B=0$；

从小到大依次遍历 $l\le i\le r$ 的每个整数 $i$，如果 $X\le x_i$ 则将 $X,A,B$ 修改为 $X+y_i,a_iA,a_iB+b_i$；

最后需要输出 $X,(A\bmod 2^{32}),(B\bmod 2^{32})$．

输入格式

第一行两个整数 $n,m$。

接下来 $n$ 行，每行四个整数 $x_i,y_i,a_i,b_i$。

接下来 $m$ 行，每行三个整数 $l',r',X'$ 表示一次查询。

由于图灵机需要执行完上一次查询才能执行下一次查询，所以本题强制在线，你需要将 $l'$、$r'$、$X'$ 分别进行先截断至低 32 位（强制转换为 32 位无符号整数）再异或 $A'$ 再异或 $B'$ 的操作得到真正的 $l'$、$r'$、$X'$。其中 $A', B'$ 为上一次查询得到的 $(A\bmod 2^{32}),(B\bmod 2^{32})$，若是第一次查询则 $A'=B'=0$。注意解密前的 $\mathbf{l', r', X'}$ 可能不在 32 位有符号整数范围内。

输出格式

共 $m$ 行，每行三个整数 $X,A,B$，依次表示每次查询的答案。

样例1

input

10 10
80 1 8 9
47 2 8 5
30 1 0 0
51 0 2 10
11 -3 1 7
87 -3 0 4
11 -1 0 0
11 2 10 8
11 0 7 6
49 2 5 0
8 10 26
3 15 28
16 29 29
57 52 94
0 8 38
6 14 21
21 30 52
21 29 26
1 13 39
5 12 76

output

28 5 0
24 0 20
4 0 62
96 1 0
39 0 4
19 0 20
34 0 20
15 0 4
32 0 4
70 0 4

样例解释

如果没有强制在线的加密，样例输入如下：

10 10
80 1 8 9
47 2 8 5
30 1 0 0
51 0 2 10
11 -3 1 7
87 -3 0 4
11 -1 0 0
11 2 10 8
11 0 7 6
49 2 5 0
8 10 26
6 10 25
4 9 9
7 10 96
1 9 39
2 10 17
1 10 32
1 9 14
5 9 35
1 8 72

样例2

input

20 20
83 -2 6 1
62 -3 0 5
79 -2 5 9
3 4 6 3
4 1 0 9
19 1 9 0
71 -3 8 2
87 -4 5 5
2 -1 2 3
23 3 7 4
44 -3 7 7
16 1 0 7
2 2 8 10
66 -1 10 7
25 -2 9 8
0 4 6 1
24 3 4 7
55 -1 5 9
8 -1 10 8
9 0 3 10
8 15 56
10 27 65
14492 14473 14589
7 16 26
982964 982973 983021
0 14 26
702 693 645
446 433 488
13 20 22
701 675 679
689 672 745
7 15 83
9 20 1
21641566 21641542 21641562
421957 421969 421982
2162314 2162309 2162385
3 14 81
1 14 94
7 18 24
2162308 2162331 2162327

output

51 50 57
62 12000 5757
96 1 0
20 705600 277491
94 1 0
11 0 701
47 200 375
83 5 5
21 1800 1464
22 1800 1464
89 1 0
78 5 5
5 0 21641554
7 0 421954
20 3528000 1387464
89 1 0
76 5 5
94 1 0
17 3528000 1387464
29 50 44

样例解释

如果没有强制在线的加密，样例输入如下：

20 20
83 -2 6 1
62 -3 0 5
79 -2 5 9
3 4 6 3
4 1 0 9
19 1 9 0
71 -3 8 2
87 -4 5 5
2 -1 2 3
23 3 7 4
44 -3 7 7
16 1 0 7
2 2 8 10
66 -1 10 7
25 -2 9 8
0 4 6 1
24 3 4 7
55 -1 5 9
8 -1 10 8
9 0 3 10
8 15 56
1 16 74
1 20 96
6 17 27
7 14 94
1 15 27
3 8 56
1 14 87
13 20 22
13 19 23
1 16 89
6 14 82
9 20 1
12 20 8
7 19 28
2 13 89
2 15 80
1 14 94
6 19 25
12 19 31

数据范围

本题采用子任务测试，你只有通过了一个子任务中的所有测试点才可以获得该子任务对应的分数。

对于所有数据：

$1\le n,m\le 2\times 10^5$。

$0\le x_i,a_i,b_i,X\le 10^9$。

$|y_i|\le 10^9$。

$1\le l\le r\le n$。

$l', r', X' \in [-2^{63}, 2^{63}-1]$。

对于任意一个整数区间 $[l,r] \subseteq [1,n]$，$\left | \sum_{i=l}^r y_i \right | \le 10^9$。

时间限制：$5\texttt{s}$

空间限制：$4\texttt{GiB}$