题目描述

有 $n$ 颗红球排成一行，从左到右编号从 $0$ 到 $(n - 1)$（含两端）。我们将进行 $n$ 次操作，其中第 $i$ 次操作将第 $a_i$ 颗球涂成蓝色。所有操作结束后，所有球都会变成蓝色。

有 $m$ 个编号从 $1$ 到 $m$（含两端）的传感器监控球的颜色。若第 $l_i$ 颗球到第 $r_i$ 颗球（含两端）里恰有一颗红球，则第 $i$ 个传感器将进入激活状态；否则传感器将保持非激活状态。

问每次操作结束后，哪些传感器处于激活状态。

更具体地，设第 $i$ 次操作结束后共有 $k_i$ 个传感器处于激活状态，它们的编号是 $s_{i, 1}, s_{i, 2}, \cdots, s_{i, k_i}$。对于每个 $0 \le i \le n$，输出 $v_i = \sum\limits_{j = 1}^{k_i} s_{i, j}^2$。特别地，定义 $v_0 = \sum\limits_{j = 1}^{k_0} s_{0, j}^2$，其中 $k_0$ 是第一次操作之前处于激活状态的传感器数量，它们的编号为 $s_{0, 1}, s_{0, 2}, \cdots, 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, \cdots, a'_n$（$0 \le a'_i < n$），其中 $a'_i$ 表示 $\textbf{加密后的}$ 第 $i$ 次操作。 $a_i$ 的真实值等于 $(a'_i + v_{i - 1}) \bmod n$，其中 $v_{i - 1}$ 是第 $(i - 1)$ 次操作后的答案，在上述描述中已有定义。这些加密后的操作强制您必须计算好当前操作的答案，才能处理下一个操作。保证解密后 $a_i$ 互不相同。

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

输出格式

每组数据输出一行 $(n + 1)$ 个由单个空格分隔的整数 $v_0, v_1, \cdots, v_n$。$v_i$ 的含义在上述描述中已有定义。

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

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

提示

对于第一组样例数据：

• 在第一次操作之前，只有传感器 $3$ 处于激活状态，所以 $v_0 = 3^2 = 9$。
• 对于第 $1$ 次操作，真实的 $a_1 = (3 + 9) \bmod 5 = 2$。本次操作后，传感器 $2$ 和 $3$ 处于激活状态，所以 $v_1 = 2^2 + 3^2 = 13$。
• 对于第 $2$ 次操作，真实的 $a_2 = (2 + 13) \bmod 5 = 0$。本次操作后，传感器 $2$，$3$ 和 $4$ 处于激活状态，所以 $v_2 = 2^2 + 3^2 + 4^2 = 29$。
• 对于第 $3$ 次操作，真实的 $a_3 = (4 + 29) \bmod 5 = 3$。本次操作后，传感器 $1$ 和 $4$ 处于激活状态，所以 $v_3 = 1^2 + 4^2 = 17$。
• 对于第 $4$ 次操作，真实的 $a_4 = (2 + 17) \bmod 5 = 4$。本次操作后，只有传感器 $4$ 处于激活状态，所以 $v_4 = 4^2 = 16$。
• 对于第 $5$ 次操作，真实的 $a_5 = (0 + 16) \bmod 5 = 1$。本次操作后，没有传感器处于激活状态，所以 $v_5 = 0$。