Description

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

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

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

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

最后需要的是所有攻击完成之后,所有柱子的损伤度的异或和和最大值。

Format

Input

第一行包含2个整数 $N$ $(1 \leq N \leq 10^6)$, $M$ $(1 \leq M \leq 2 * 10^5)$.

接下来 $M$ 行, 每行4个整数 $l, r, s, e$.

$(1 \leq l < r \leq n)$.

$(0 \leq s \leq 10^4)$.

$(0 \leq e \leq 10^4)$.

Output

输出变化之后, 数组异或和和最大值

Samples

5 2
1 5 2 10
2 4 1 1

3 10

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

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

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

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

Limitation

1s, 1024KiB for each test case.