有一个 n 个节点 m 条边的无向图,对于一条边有四个参数 (a,b,l,r) ,表示这条边在 [l,r] 这些时间连接 (a,b) 。
有一个传送技能:如果在某时刻 u 和 v 在一个连通块里,可以从 u 传送到 v 。
小 A 初始在节点 1 ,所以 小 A 想知道他能在[1,n] 中的哪些时间点能直接从 1 传送到节点 i ,请你帮帮他。
由于输出量可能过大,考虑简化输出,假设所有能从 1 到达 i 的时间点为 ti,1…ti,k ,定义ansi=∑j=1kti,j ,你只需要输出一个 ⊕i=1nansi 即可,其中 ⊕ 表示异或和。
第一行输入 n,m 。
接下来 m 行,每行输入 ai,bi,li,ri ,表示第 i 条边的属性。
1≤n,m≤6×105,1≤ai,bi,li,ri≤n.
4 5
1 3 3 4
2 1 3 4
4 3 1 3
2 4 2 2
4 3 3 3
9