一个分布式系统拥有 $n$ 个工作节点，编号从 $0$ 到 $(n - 1)$。该系统将处理 $q$ 个任务，其中第 $i$ 个任务由两个整数 $a_i$ 和 $b_i$ 表示，意味着该任务包含 $a_i$ 个子任务，编号从 $0$ 到 $(a_i - 1)$，且第 $j$ 个子任务将被分配给工作节点 $(b_i + j) \pmod n$。

对于每个 $0 \le k < n$，计算所有任务处理完成后，分配给工作节点 $k$ 的子任务总数。

输入格式

输入包含多组测试数据。第一行包含一个整数 $T$ ($1 \le T \le 10^4$)，表示测试数据组数。对于每组测试数据：

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 2 \times 10^5$)，分别表示工作节点的数量和任务的数量。

接下来的 $q$ 行中，第 $i$ 行包含两个整数 $a_i$ 和 $b_i$ ($1 \le a_i \le 10^9, 0 \le b_i < n$)，表示第 $i$ 个任务。

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

输出格式

对于每组测试数据，输出一行，包含 $n$ 个整数 $v_0, v_1, \dots, v_{n-1}$，并用空格分隔，其中 $v_k$ 表示所有任务处理完成后分配给工作节点 $k$ 的子任务总数。

样例

输入 1

2
7 3
10 0
4 2
21 1
1 2
200 0
100 0

输出 1

5 5 6 5 5 5 4
300