该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

置顶聊天列表

题目描述

有 $n$ 个聊天，编号为 $1 \sim n$。

初始时：

• 所有聊天都未置顶；
• 聊天列表从前到后的显示顺序为 $1, 2, 3, \dots, n$；
• 每个聊天的未读消息数均为 $0$。

聊天列表始终满足以下显示规则：

1. 所有置顶聊天排在前面（构成置顶区）；
2. 所有未置顶聊天排在后面（构成未置顶区）；
3. 置顶区内部、未置顶区内部，各自维护一个相对顺序。

现在有 $q$ 次操作，每次操作为以下四种之一：

• 1 x：聊天 $x$ 收到一条新消息；
• 2 x：用户打开聊天 $x$；
• 3 x：将聊天 $x$ 设为置顶；
• 4 x：取消聊天 $x$ 的置顶。

对于每种操作，列表的具体变化规则如下：

操作 1 x（收到消息）：

• 聊天 $x$ 的未读消息数加 $1$；
• 若 $x$ 当前是置顶聊天，则将它移动到置顶区最前面；
• 若 $x$ 当前是未置顶聊天，则将它移动到未置顶区最前面。

操作 2 x（打开聊天）：

• 聊天 $x$ 的未读消息数清零（变为 $0$）；
• 若 $x$ 当前是置顶聊天，则将它移动到置顶区最前面；
• 若 $x$ 当前是未置顶聊天，则将它移动到未置顶区最前面。

操作 3 x（设为置顶）：

• 若 $x$ 当前已经是置顶聊天，则本次操作不产生任何影响；
• 否则，将 $x$ 从未置顶区移出，并插入到置顶区最前面。

操作 4 x（取消置顶）：

• 若 $x$ 当前不是置顶聊天，则本次操作不产生任何影响；
• 否则，将 $x$ 从置顶区移出，并插入到未置顶区最前面。

请你在所有操作结束后，输出最终聊天列表从前到后的聊天编号，以及对应每个聊天的未读消息数。

输入格式

第一行输入两个整数 $n, q$，分别表示聊天总数和操作次数。

接下来 $q$ 行，每行输入两个整数 op 和 $x$，表示一次操作。

数据范围

• $1 \le n, q \le 2\times 10^5$
• $op \in {1, 2, 3, 4}$
• $1 \le x \le n$

输出格式

输出共两行：

• 第一行输出 $n$ 个用空格隔开的整数，表示最终聊天列表从前到后的聊天编号；
• 第二行输出 $n$ 个用空格隔开的整数，表示与第一行顺序一一对应的未读消息数。

输入输出样例 #1

输入 #1

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

输出 #1

3 1 5 2 4
0 1 1 1 0

说明/提示

初始列表为（使用 | 分隔置顶区和未置顶区，初始置顶区为空）： | 1 2 3 4 5

下面依次模拟每次操作：

• 第 1 次操作 1 3：聊天 $3$ 收到新消息，未读数变为 $1$。它未置顶，移动到未置顶区最前面。列表为：| 3 1 2 4 5
• 第 2 次操作 1 2：聊天 $2$ 收到新消息，未读数变为 $1$。它未置顶，移动到未置顶区最前面。列表为：| 2 3 1 4 5
• 第 3 次操作 3 3：将聊天 $3$ 设为置顶。移到置顶区最前面。列表为：3 | 2 1 4 5
• 第 4 次操作 1 5：聊天 $5$ 收到新消息，未读数变为 $1$。它未置顶，移动到未置顶区最前面。列表为：3 | 5 2 1 4
• 第 5 次操作 2 3：打开聊天 $3$，未读数清零。它已置顶，移动到置顶区最前面（位置不变）。列表仍为：3 | 5 2 1 4
• 第 6 次操作 3 5：将聊天 $5$ 设为置顶。移到置顶区最前面。列表为：5 3 | 2 1 4
• 第 7 次操作 4 5：取消聊天 $5$ 的置顶。移到未置顶区最前面。列表为：3 | 5 2 1 4
• 第 8 次操作 1 1：聊天 $1$ 收到新消息，未读数变为 $1$。它未置顶，移动到未置顶区最前面。列表为：3 | 1 5 2 4

最终聊天编号顺序为：3 1 5 2 4 对应未读消息数为：0 1 1 1 0