Hearthstone 是流行的电子游戏之一。请仔细阅读以下规则。它们与通常的规则不同。

有 $n$ 种编号为 $1, 2, \dots, n$ 的奥秘牌。关于奥秘有两种类型的事件：

• add：向英雄区域添加一张编号未知的奥秘。英雄区域中不能同时存在两张编号相同的奥秘。
• test x y：测试奥秘 $x$ 是否存在。如果奥秘 $x$ 存在，则 $y = 1$ 且奥秘 $x$ 从英雄区域中移除；否则，$y = 0$。注意，无论 $y$ 为何值，在测试 $x$ 后，奥秘 $x$ 都不存在于英雄区域中。

一个事件序列 $E = [e_1, \dots, e_m]$ 是合法的，当且仅当可以为每个 add 事件分配一个 $1$ 到 $n$ 之间的编号，并按顺序执行事件 $e_1, e_2, \dots, e_m$，使得：

• 开始时英雄区域中没有任何奥秘；
• 在添加奥秘 $x$ 的事件之前，奥秘 $x$ 不存在；
• 在 test x 1 事件之前，奥秘 $x$ 存在；
• 在 test x 0 事件之前，奥秘 $x$ 不存在。

给定 $q$ 个事件 $e_1, e_2, \dots, e_q$，你需要维护一个事件序列 $E$。初始时，$E$ 为空。对于每个 $i = 1, 2, \dots, q$，按顺序尝试将 $e_i$ 追加到 $E$ 的末尾。如果 $E$ 不合法，则移除 $e_i$ 并报告一个 bug。否则，求出在按顺序执行 $E$ 中的事件后，英雄区域中必然存在的奥秘数量，以及必然不存在的奥秘数量。

注意，必然（不）存在的奥秘数量不仅仅是（非）存在奥秘的数量。例如，当 $n = 2$ 时，初始时奥秘 $1$ 缺失且奥秘 $2$ 缺失，因此答案为 $0$ 和 $2$。在执行一次 add 后，奥秘 $1$ 是未知的（可能在也可能不在英雄区域中），奥秘 $2$ 也是未知的，因此答案为 $0$ 和 $0$。在执行 test 2 0 后，奥秘 $2$ 缺失，因此我们知道添加的那张牌一定是奥秘 $1$，所以奥秘 $1$ 存在，答案为 $1$ 和 $1$。详情请参考样例。

输入格式

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

第一行包含两个整数 $n$ 和 $q$ ($1 \le n, q \le 10^5$)，分别表示奥秘的种类数和事件数。

接下来的 $q$ 行，第 $i$ 行表示事件 $e_i$，包含：

• 字符串 add；
• 或者字符串 test，后跟两个整数 $x$ 和 $y$ ($1 \le x \le n, 0 \le y \le 1$)。

保证所有测试数据中 $n$ 的总和与 $q$ 的总和均不超过 $10^5$。

输出格式

对于每组测试数据：

对于每个事件，如果可以追加，输出两个整数：英雄区域中必然存在的奥秘数量和必然不存在的奥秘数量；否则，输出字符串 bug。

样例

样例输入 1

2
1 8
test 1 0
test 1 1
add
test 1 0
test 1 1
add
test 1 1
test 1 0
2 10
add
add
add
test 1 1
test 1 1
add
add
add
test 2 1
test 2 1

样例输出 1

0 1
bug
1 0
bug
0 1
1 0
0 1
0 1
0 0
2 0
bug
1 1
bug
2 0
bug
bug
1 1
bug

样例输入 2

1
4 7
add
add
test 3 0
test 4 0
add
test 1 1
test 3 1

样例输出 2

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