题目描述

某货运枢纽的停机坪上一共有 $n$ 个泊位，调度中心陆续收到 $m$ 条动态，每条动态是下面两种之一：

• 1 id：编号为 $id$ 的货机驶离泊位起飞。
• 2 x：一架新到的货机（其编号等于已经到达过的货机总架数加 $1$）停靠到 $x$ 号泊位。

请统计全部动态处理完以后，每个泊位上仍停着的货机架数，以及每个泊位自始至今曾经停靠过的货机架数。

输入格式

第一行输入两个正整数 $n,m$，用空格隔开。

接下来 $m$ 行，每行输入两个正整数，用空格隔开，表示一条动态。

输出格式

输出共两行。

第一行输出 $n$ 个正整数，用空格隔开，第 $i$ 个正整数表示最终状态下第 $i$ 个泊位停靠的货机数量。

第二行输出 $n$ 个正整数，用空格隔开，第 $i$ 个正整数表示最终状态下第 $i$ 个泊位曾经停靠过货机的数量。

样例

2 5
2 1
2 2
2 1
2 2
1 4

2 1
2 2

4 5
2 1
2 2
2 3
2 4
2 3

1 1 2 1
1 1 2 1

6 6
2 1
2 4
2 1
1 1
2 1
2 2

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

提示

对于样例 #1，第 $1,3$ 架货机曾经停在 $1$ 号泊位，第 $2,4$ 架货机曾经停在 $2$ 号泊位，第 $4$ 架货机起飞后，$2$ 号泊位只剩一架货机。

对于样例 #2，没有货机起飞，每个泊位曾经停靠过的货机数量依次为 $1,1,2,1$。

对于 $30\%$ 的数据，保证没有 1 动态出现。

对于另外 $20\%$ 的数据，保证 $1\leq m\leq 5$。

对于 $100\%$ 的数据，保证 $1\leq n,m\leq 100000$，保证所有操作均合法。