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

通知折叠

题目描述

某聊天软件有一个通知面板，最多只能显示 $k$ 个话题。

每个话题都有一个未读消息数。系统会依次处理 $q$ 个操作，操作共有两种：

• + x：表示话题 $x$ 收到一条新消息。
• - x：表示用户清空话题 $x$ 的所有未读消息。

通知面板中的话题有先后顺序，最上方的话题记为第一个，最下方的话题记为最后一个。

对于每个话题，需要区分两种状态下的未读消息数：

1. 在通知面板中显示的未读消息数
2. 不在通知面板中时，在后台保留的未读消息数

当话题被挤出通知面板时，它当前显示的未读消息数会转移到后台；当它再次收到新消息并重新进入通知面板时，会带着后台保留的未读消息数一起回来。

系统按照以下规则处理操作。

1. 操作 + x

表示话题 $x$ 收到一条新消息。

• 如果话题 $x$ 当前已经在通知面板中：
  • 它的未读消息数加 $1$；
  • 然后将它移动到通知面板最上方。
• 如果话题 $x$ 当前不在通知面板中：
  • 它会被插入到通知面板最上方；
  • 它进入面板后的未读消息数为：该话题当前在后台保留的未读消息数 + 1；
  • 然后该话题在后台保留的未读消息数清零。
• 如果插入后通知面板中的话题数超过 $k$：
  • 删除通知面板最下方的话题；
  • 被删除话题当前的未读消息数会转移到后台保留区中。

2. 操作 - x

表示用户清空话题 $x$ 的所有未读消息。

• 如果话题 $x$ 当前在通知面板中，则将它从通知面板中删除；
• 无论话题 $x$ 当前是否在通知面板中，都需要将它在后台保留的未读消息数清零。

初始时，通知面板为空，所有话题的未读消息数均为 $0$。

请你在所有操作结束后，输出通知面板中从上到下的话题编号及其未读消息数。

输入格式

第一行输入两个整数 $q, k$，表示操作数和通知面板最多显示的话题数。

接下来 $q$ 行，每行描述一个操作，格式为以下两种之一：

• + x
• - x

其中 $x$ 表示话题编号。

数据范围

对于所有数据，满足：

• $1 \le k \le q \le 2 \times 10^5$
• $1 \le x \le 10^9$

输出格式

第一行输出一个整数 $m$，表示最终通知面板中的话题数量。

接下来 $m$ 行，按照通知面板从上到下的顺序，每行输出两个整数：

id cnt

分别表示话题编号和该话题当前显示的未读消息数。

输入输出样例 #1

输入 #1

9 3
+ 1
+ 2
+ 3
+ 4
+ 2
- 2
+ 1
+ 5
+ 2

输出 #1

3
2 1
5 1
1 2

输入输出样例 #2

输入 #2

6 2
+ 7
+ 8
+ 9
- 7
+ 7
+ 8

输出 #2

2
8 2
7 1

说明/提示

样例 1 说明

操作过程如下：

• +1、+2、+3 后，通知面板从上到下为：3(1), 2(1), 1(1)
• +4 后，4 插入到最上方，面板超出容量，1(1) 被挤出并转入后台
• +2 后，2 的未读消息数变为 2，并移动到最上方
• -2 后，2 被清空并从面板中删除
• +1 时，1 在后台保留了 1 条未读，因此重新进入面板时未读消息数为 2