You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目背景

（三）旧都

离开狭窄的洞穴，眼前豁然开朗。

天空飘着不寻常的雪花。

一反之前的幽闭，现在面对的，是繁华的街市，可以听见酒碗碰撞的声音。

这是由被人们厌恶的鬼族和其他妖怪们组成的小社会，一片其乐融融的景象。

诶，不远处突然出现了一些密密麻麻的小点，好像大颗粒扬尘一样。

离得近了点，终于看清楚了。

长着角的鬼们聚在一起，围观着另一只鬼的表演。

那”扬尘”，其实都是弹幕。

勇仪的招数之一，三步之内，所到之处弹幕云集，几乎没有生存可能。

为了强化这一技能，勇仪将对着一排柱子进行攻击。

旧地狱的柱子虽然无比坚固，但保险起见还是先要了解一下这样一套攻击对柱子有多少损伤，顺带也能检验练习的效果。

勇仪决定和其它鬼们商量商量...

“我知道妖怪之山的河童一族有一种叫做计算机的神奇道具，说不定可以借来用用”，萃香说道。

于是旧地狱的鬼族就决定请河城荷取来帮忙了。

“要记录【所有柱子的损伤程度】吗”，荷取问道。

经过进一步的询问，荷取发现他们仅仅需要【所有攻击都完成后】柱子的损伤程度。

任务了解地差不多了，荷取将其中的重要部分提取了出来，记录在了她的工作笔记本上：

(记录的内容见题目描述)

那么实验就这样开始了。

在惊天动地的碰撞声中，勇仪每完成一轮攻击，荷取都忠实地记录下对每根柱子产生的伤害。而此时勇仪就在旁边等待着记录完成，然后再进行下一轮的攻击。

地面上，天色渐晚。

“不想在这里留到深夜啊，不然就回不了家了”，荷取这样想着，手中依然在重复地向计算机中输入新产生的信息。

“真的必须一次一次地记录下每轮攻击对每个柱子产生的伤害吗？有没有更高效的方法？”这一念头在荷取的心中闪过...

（后续剧情在题解中，接下来请看T3）

题目描述

$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$ 的伤害。

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

输入格式

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

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

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

输出格式

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

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

（异或运算符在 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

提示

样例解释：

样例 $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。