有 $n$ 个红球排成一行，从左到右编号为 $0$ 到 $n-1$。我们将进行 $n$ 次操作，第 $i$ 次操作会将编号为 $a_i$ 的球染成蓝色。所有操作完成后，所有的球都将变为蓝色。

有 $m$ 个传感器，编号为 $1$ 到 $m$，用于监测球的颜色。如果第 $i$ 个传感器监测范围内的所有球（编号从 $l_i$ 到 $r_i$，包含两端）中恰好有一个红球，则该传感器变为激活状态；否则传感器保持未激活状态。

请确定每次操作后哪些传感器处于激活状态。

更准确地说，设第 $i$ 次操作后有 $k_i$ 个激活的传感器，它们的编号为 $s_{i,1}, s_{i,2}, \dots, s_{i,k_i}$。对于每个 $0 \le i \le n$，输出 $v_i = \sum_{j=1}^{k_i} s_{i,j}^2$。特别地，定义 $v_0 = \sum_{j=1}^{k_0} s_{0,j}^2$，其中 $k_0$ 是第一次操作前激活传感器的数量，且激活传感器的编号为 $s_{0,1}, s_{0,2}, \dots, s_{0,k_0}$。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$，表示测试数据的组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $m$ ($1 \le n, m \le 5 \times 10^5$)，分别表示球的数量和传感器的数量。

接下来的 $m$ 行，第 $i$ 行包含两个整数 $l_i$ 和 $r_i$ ($0 \le l_i \le r_i < n$)，表示第 $i$ 个传感器的检测范围。

下一行包含 $n$ 个整数 $a'_1, a'_2, \dots, a'_n$ ($0 \le a'_i < n$)，表示编码后的第 $i$ 次操作。$a_i$ 的真实值等于 $(a'_i + v_{i-1}) \pmod n$，其中 $v_{i-1}$ 是第 $(i-1)$ 次操作后的答案（定义见上文）。通过这些编码后的操作，你必须在处理下一次操作前计算出当前操作的答案。保证解码后的每个 $a_i$ 互不相同。

保证所有测试数据的 $n$ 之和与 $m$ 之和均不超过 $5 \times 10^5$。

输出格式

对于每组测试数据，输出一行，包含 $(n+1)$ 个整数 $v_0, v_1, \dots, v_n$，用空格分隔。$v_i$ 的含义如上文所述。

样例

输入 1

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

输出 1

9 13 29 17 16 0
1 1 0
0 1 0

说明

对于第一组样例测试数据：

• 在第一次操作前，只有传感器 3 是激活的，因此 $v_0 = 3^2 = 9$。
• 对于第 1 次操作，真实值 $a_1 = (3 + 9) \pmod 5 = 2$。操作后，传感器 2 和 3 激活，因此 $v_1 = 2^2 + 3^2 = 13$。
• 对于第 2 次操作，真实值 $a_2 = (2 + 13) \pmod 5 = 0$。操作后，传感器 2、3 和 4 激活，因此 $v_2 = 2^2 + 3^2 + 4^2 = 29$。
• 对于第 3 次操作，真实值 $a_3 = (4 + 29) \pmod 5 = 3$。操作后，传感器 1 和 4 激活，因此 $v_3 = 1^2 + 4^2 = 17$。
• 对于第 4 次操作，真实值 $a_4 = (2 + 17) \pmod 5 = 4$。操作后，只有传感器 4 激活，因此 $v_4 = 4^2 = 16$。
• 对于第 5 次操作，真实值 $a_5 = (0 + 16) \pmod 5 = 1$。操作后，没有传感器激活，因此 $v_5 = 0$。