该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

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

输出一个数，表示答案。

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

9

Hint

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