问题 D: 传送

内存限制:256 MB 时间限制:3 S
题面:传统 评测方式:文本比较 上传者:
提交:7 通过:4

题目描述

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

有一个传送技能:如果在某时刻 u 和 v 在一个连通块里,可以从 u 传送到 v 。

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

由于输出量可能过大,考虑简化输出,假设所有能从 1 到达 i 的时间点为 ti,1ti,k ,定义ansi=j=1kti,j ,你只需要输出一个 i=1nansi 即可,其中  表示异或和。

输入格式

第一行输入 n,m 。

接下来 m 行,每行输入 ai,bi,li,ri ,表示第 i 条边的属性。

1n,m6×105,1ai,bi,li,rin.

输出格式

输出一个数,表示答案。

输入样例 复制

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