题目描述

某机场有 $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$，保证所有操作均合法。