米小游陪着她的好朋友莫娜来买手办，她时不时会看一眼队列中有多少人。也就是说，共有 4 种事件：

事件1 => 1 s ：名字为 s 的人加入队列的结尾（保证不在队列中）。

事件2 => 2 s ：名字为s 的人离开队列（保证 s 在队列中，但不一定在队列最前面）。

事件3 => 3 x ：队列最前面的人购买了x 个手办（保证在手办个数大于 0 时，当前至少有x 个手办）。

事件4 => 4：米小游查看队列人数。

(注意 => 箭头后面的代表输入的格式, 1 和2 后面会跟一个字符串, 3 后面跟的是数字, 4 后面什么也没有, 仅有一个4)

还有一个特殊规则：当手办个数小于等于m 时，处于队列最前面的人一定会把剩余的所有手办全部买走。当手办全部被买走后，队列会立即清空，后续的所有事件都将失效。

米小游想知道，她每次查看队列人数时，队列中有多少人。以及最后手办全部卖完或者所有事件结束后，每个参与过排队的人各买了多少个手办？（按名字字典序升序输出）

第一行输入三个整数 n, m (1 <= m <= n <= 10^9)，q(1 <= q <= 10^5) 

其中n表示手办个数、

m表示特殊规则限制、

q为事件个数。

接下来q 行，首先输入一个整数 op(1 <= op <= 4) 表示事件类型：

若事件类型为 1 或 2，则再输入一个长度不超过20 的只由大小写字母组成的字符串s 表示名字；

若事件类型为 3，则再输入一个整数x 表示购买的手办个数；

若事件类型为 4，则不再输入。

对于每一个类型为 4 的事件，输出一行，包含一个整数表示队列中的人数。

最后每一行按字典序升序输出每一个参与过排队的人的名字和购买的手办个数（用一个空格隔开）。

样例输入1:
70 20 8
1 Mona
1 Kaveh
4
2 Mona
1 Mona
2 Kaveh
4
1 Kaveh
样例输入2:
70 20 13
1 Mona
1 Kaveh
4
2 Mona
1 Eden
1 Mona
2 Kaveh
4
1 Kaveh
4
3 50
2 Eden
4

样例输出1:
2
1
Kaveh 0
Mona 0
样例输出2:
2
2
3
Eden 70
Kaveh 0
Mona 0

样例1解释:
初始时队列为空。
第1个事件：Mona加入队列，队列为：["Mona"]。
第2个事件：Kaveh加入队列，队列为：["Mona","Kaveh"]。
第3个事件：查看队列人数，队列为：["Mona","Kaveh"]，共有2人。
第4个事件：Mona离开队列，队列为：["Kaveh"]。
第5个事件：Mona加入队列，队列为：["Kaveh","Mona"]。
第6个事件：Kaveh离开队列，队列为：["Mona"]。
第7个事件：查看队列人数，队列为：["Mona"]，共有1人。
第8个事件：Kaveh加入队列，队列为：["Mona","Kaveh"]。
Kaveh共购买了0个手办。
Mona共购买了0个手办。
样例2解释:
初始时队列为空。
第1个事件：Mona加入队列，队列为：["Mona"]。
第2个事件：Kaveh加入队列，队列为：["Mona","Kaveh"]。
第3个事件：查看队列人数，队列为：["Mona","Kaveh"]，共有2人。
第4个事件：Mona离开队列，队列为：["Kaveh"]。
第5个事件：Eden加入队列，队列为：["Kaveh","Eden"]。
第6个事件：Mona加入队列，队列为：["Kaveh","Eden","Mona"]。
第7个事件：Kaveh离开队列，队列为：["Eden","Mona"]。
第8个事件：查看队列人数，队列为：["Eden","Mona"]，共有2人。
第9个事件：Kaveh加入队列，队列为：["Eden","Mona","Kaveh"]。
第10个事件：查看队列人数，队列为：["Eden","Mona","Kaveh"]，共有3人。
第11个事件：Eden购买了50个手办，队列为：["Eden","Mona","Kaveh"]，但此时手办剩余数量小于等于20，因此处于队列最前方的Eden还会买走剩下的20个手办，总共买走了70个。
第12个事件：由于手办全部被买走，事件失效。
第13个事件：由于手办全部被买走，事件失效。
Eden共购买了70个手办。
Kaveh共购买了0个手办。
Mona共购买了0个手办。