题目描述

有一个 $n$ 个节点 $m$ 条边的无向图，对于一条边有四个参数 $(a,b,l,r)$，表示这条边在 $[l,r]$ 这些时间连接 $(a,b)$。

有一个传送技能：如果在弄个时刻 $u$ 和 $v$ 在一个连通块里，可以从 $u$ 传送到 $v$。

小 A 初始在节点 $1$，所以小 A 想知道他能在 $[1,n]$ 中的哪些时间点能直接从 $1$ 传送到节点 $i$，请你帮帮他。

由于输出量可能过大，考虑简化输出，假设所有能从 $1$ 到达 $i$ 的时间点为 $t_{i,1}...t_{i,k}$，定义 $ans_i=\sum_{j=1}^k t_{i,j}$ ，你只需要输出一个 $\bigoplus_{i=1}^n ans_i$ 即可，其中 $\bigoplus$ 表示异或和。

输入格式

第一行输入 $n,m$（$1\le n,m \le 6 \times 10^5$）。

接下来 $m$ 行，每行输入 $a_i,b_i,l_i,r_i$ （$1\le a_i,b_i,l_i,r_i \le n$），表示第 $i$ 条边的属性。

输出格式

输出一个数字，表示答案。

输入样例

4 5
1 3 3 4
2 1 3 4
4 3 1 3
2 4 2 2
4 3 3 3

输出样例

9

提示

答案分别是$10,7,7,3$。