传送

Problem Description

有一个 $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} \dots t_{i,k}$ ，定义 $ans_i = \sum_{j=1}^{k} t_{i, j}$ ，你只需要输出一个 $\oplus_{i=1}^{n} ans_i$ 即可，其中 $\oplus$ 表示异或和。

Input

第一行输入 $n,m$ 。 接下来 $m$ 行，每行输入 $a_i, b_i, l_i, r_i$ ，表示第 $i$ 条边的属性。 $ 1 \leq n,m\leq 6 \times 10^5, 1 \leq a_i, b_i, l_i, r_i \leq n. $

Output

输出一个数，表示答案。

Sample Input

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

Sample Output

9

Hint

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

Source

2024“钉耙编程”中国大学生算法设计超级联赛（1）