Description

$N$ 个柱子排成一排，一开始每个柱子损伤度为 $0$。

接下来勇仪会进行 $M$ 次攻击，每次攻击可以用 $4$ 个参数 $l,r,s,e$ 来描述：

表示这次攻击作用范围为第 $l$ 个到第 $r$ 个之间所有的柱子(包含 $l,r$)，对第一个柱子的伤害为 $s$，对最后一个柱子的伤害为 $e$。

攻击产生的伤害值是一个等差数列。若 $l=1,r=5,s=2,e=10$，则对第 $1 \sim 5$ 个柱子分别产生 $2,4,6,8,10$ 的伤害。

鬼族们需要的是所有攻击完成之后每个柱子的损伤度。

Input Format

第一行 $2$ 个整数 $N,M$，用空格隔开，下同。

接下来 $M$ 行，每行 $4$ 个整数 $l,r,s,e$，含义见题目描述。

数据保证对每个柱子产生的每次伤害值都是整数。

Output Format

由于输出数据可能过大无法全部输出，为了确保你真的能维护所有柱子的损伤度，只要输出它们的异或和与最大值即可。

（异或和就是所有数字按位异或起来的值。）

（异或运算符在 c++ 里为 ^。）

5 2
1 5 2 10
2 4 1 1

3 10

6 2
1 5 2 10
2 4 1 1

3 10

Hint

样例解释：

样例 $1$：

第一次攻击产生的伤害：$2,4,6,8,10$。

第二次攻击产生的伤害：$0,1,1,1,0$。

所有攻击结束后每个柱子的损伤程度：$2,5,7,9,10$。

输出异或和与最大值，就是 $3,10$。

样例 $2$：

没有打到第六根柱子，答案不变

数据范围：

本题满分为 $100$ 分，下面是 $4$ 个子任务。$(x/y)$ 表示(得分/测试点数量)。

妖精级 $(18/3)$：$1 \le n,m \le 1000$。这种工作即使像妖精一样玩玩闹闹也能完成吧？

河童级 $(10/1)$：$s=e$，这可以代替我工作吗？

天狗级 $(20/4)$：$1 \le n,m \le 10^5$。小打小闹不再可行了呢。

鬼神级 $(52/2)$：没有特殊限制。要真正开始思考了。

以上四部分数据不相交。

对于全部的数据：$1\le n\le 10^7$，$1\le m\le 3\times 10^5$，$1\le l < r \le n$.

所有输入输出数据以及柱子受损伤程度始终在 $[0,9 \times 10^{18}]$ 范围内。

提示：

由于种种原因，时间限制可能会比较紧，c++ 选手请不要使用 cin 读入数据。

by orangebird。