Internet of Everything

题目描述

遥遥领先！遥遥领先！遥遥领先！

Orange有一个序列 $a_i$，最开始，所有的数均为 0。Orange将进行如下2种操作 $q$ 次，请你求出最后的 $a_i$ 序列。

• 1 p 令 $a_p \leftarrow a_p+1$，即让 $a_p$ 自增1。
• 2 x 令所有序列中所有值等于 $x$ 的数均自增1，即 $a_i \leftarrow a_i + [a_i = x]$。

输入格式

输入包含多组测试数据，第一行为一个整数 $T$，表示测试数据组数。 对于每组测试数据： 输入第一行包含2个整数 $n,q$，表示序列长度和操作总数。 接下来 $q$ 行，每行两个整数，表示一次操作。

数据范围

$\sum n, q \le 3\times 10^5$ $0 \le x \le n$ $1 \le p \le n$

题目保证，对于每个2 x操作，$x$ 一定是序列中存在的数。

输出格式

对于每组测试数据，输出一个整数序列，占一行，表示答案。

样例 #1

样例输入 #1

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

样例输出 #1

1 3 1
2 0
1
2 2 2 3

提示

样例解释1

第一次操作后序列 a={1,1,1}。

第二次操作后序列 a={1,2,1}。

第三次操作后序列 a={1,3,1}。