题目描述

某航空训练基地设置了 $n$ 个机位，编号依次为 $1$ 到 $n$。

系统按照时间顺序记录了 $m$ 条飞机调度信息，每条信息属于以下两种类型之一：

• 1 id：编号为 $id$ 的飞机离开当前停靠的机位并起飞；
• 2 x：一架新飞机降落，并停靠在编号为 $x$ 的机位。

飞机按照降落的先后顺序编号。第一架降落的飞机编号为 $1$，第二架编号为 $2$，以此类推。也就是说，每当出现一次 2 操作，新飞机的编号等于此前已经降落过的飞机总数加 $1$。

处理完全部调度信息后，请你分别统计：

1. 当前每个机位上停靠的飞机数量；
2. 从开始记录到现在，每个机位累计停靠过的飞机数量。

输入格式

第一行输入两个正整数 $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

样例 1 解释

第 $1,3$ 架飞机曾经停在 $1$ 机位，第 $2,4$ 架飞机曾经停在 $2$ 机位，第 $4$ 架飞机起飞后，$2$ 机位只有一架飞机。

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

1 1 2 1
1 1 2 1

样例 2 解释

没有飞机起飞，每个机位曾经停靠过的飞机数量依次为 $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 

提示

• 对于 $30$ 的数据，保证没有 1 信息出现。
• 对于另外 $20$ 的数据，保证 $1\leq m\leq 5$。
• 对于 $100$ 的数据，保证 $1\leq n,m\leq 100000$，保证所有操作均合法。