Description

Dwx 有 $n$ 个木棍编号为 0 到 $(n-1)$ 。现在 Dyz有 $q$ 堆圆环，其中第 $i$ 堆可以记为两个整数 $a_i$ 与 $b_i$，表示该堆圆环有 $a_i$ 个，编号为 0 到 $(a_i - 1)$ 的圆环，且圆环 $j$ 会串在第 ($(b_i + j) \mod n)$个木棍上。

对于每个 $0 \leq k < n$，求所有圆环串完之后，木棍 $k$ 一共串了几个圆环。

Format

Input

有多组测试数据。第一行输入一个整数 $T$（$1 \leq T \leq 10^4$）表示测试数据组数，对于每组测试数据：

• 第一行输入两个整数 $n$ 和 $q$（$1 \leq n, q \leq 2 \times 10^5$），表示 Dwx 手中木棍的数量以及 Dyz 圆环堆的数量。

• 对于接下来 $q$ 行，第 $i$ 行输入两个整数 $a_i$ 和 $b_i$（$0 \leq a_i \leq 10^9$，$0 \leq b_i < n$），表示第 $i$ 堆圆环。

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

Output

每组数据输出一行 $n$ 个由单个空格分隔的整数 $v_0, v_1, \cdots, v_{n-1}$，其中 $v_k$ 表示所有圆环串完之后，木棍 $k$ 一共串了几个圆环。

Samples

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

5 5 6 5 5 5 4
300

Limitation

Time Limit: 1 second

Memory Limit: 256MiB