题目描述

有一个长度为 $n$ 的数组 $a$，下标从 $0$ 到 $n-1$。初始时，所有元素均为 $0$。

接下来进行 $m$ 次操作。一次操作给出四个整数 $l,r,p,q$。 对于每个满足 $l \le i \le r$ 的整数 $i$： $\red{j = i \oplus p}$ 若 $0\le j < n$，则执行 $a_j \leftarrow a_j \oplus q$；否则忽略这个 $i$。

求所有操作结束后的数组。

输入格式

第一行输入两个整数 $n,m$。 接下来 $m$ 行，每行输入四个整数 $l,r,p,q$，表示一次操作。

输出格式

输出一行 $n$ 个非负整数，依次表示 $a_0,a_1,\dots,a_{n-1}$。

样例输入 #1

4 2
0 2 0 3
1 3 0 5

样例输出 #1

3 6 6 5

样例输入 #2

4 2
0 2 0 3
1 3 1 5

样例输出 #2

6 3 6 5

样例输入 #3

4 2
0 2 1 3
1 3 1 5

样例输出 #3

6 3 5 6

数据范围

对于全部数据：

• $1 \le n,m \le 2^{18}$
• $0 \le l \le r < 2^{18}$
• $0 \le p < 2^{18}$
• $0 \le q \le 2^{32}-1$

数组中每个元素在操作过程中均处于32位无符号整数范围 $[0,2^{32}-1]$ 内。 共20个测试点，每个测试点5分。