最近在学校 Alina 学习了什么是持久数据结构:它们是始终保留自身先前版本并在修改时访问它的数据结构。
回到家后,Alina 决定发明她自己的持久数据结构。发明并没有花很长时间:她的床后面就有一个书柜。 Alina 认为书柜是持久数据结构的不错选择。最初书柜是空的,因此任何架子的任何位置都没有书。
书柜由 n 个架子组成,每个架子上正好有 m 个位置可以放书。 Alina 通过从 1 到 n 的整数以及从 1 到 m 的货架位置来枚举货架。最初书柜是空的,因此书柜中任何架子的任何位置都没有书。
Alina 写下 q 操作,这些操作将连续应用于书柜。每个操作都有以下四种类型之一:
- 1 i j — 如果书架 i 上没有书,则将书放在位置 j 处。
- 2 i j — 如果书架 i 上有书,则将书从位置 j 移走。
- 3 i — 反转书籍放置在书架 i 上。这意味着,应该从书架 i 上每个有书的位置移除书,并且应该在书架 i 上没有书的每个位置放置一本书。
- 4 k — 将书柜中的书籍返回到应用第 k 次操作后的状态。特别地,k = 0意味着书柜应处于初始状态,因此书柜中的每一本书都应从其位置移走。
应用每个操作后,Alina 对书柜中的书籍数量感兴趣。阿丽娜在学校获得了“A”,并且毫无问题地找到了这个价值观。你会这样做吗?
输入
输入的第一行包含三个整数 n、m 和 q (1 ≤ n, m ≤ 103, 1 ≤ q ≤ 105)——分别是书柜尺寸和操作次数。
接下来的 q 行按时间顺序描述操作 - 其中第 i 行以语句中描述的四种格式之一描述第 i 个操作。
保证货架索引和位置索引是正确的,并且在每种第四类操作中,数字k对应于其之前的某个操作或等于0。
输出
对于每个操作,在单独的行中应用后打印书柜中的书籍数量。答案应按时间顺序打印。
示例
输入 #1
2 3 3 1 1 1 3 2 4 0
输出 #1
1 4 0
输入 #2
4 2 6 3 2 2 2 2 3 3 3 2 2 2 2 3 2
输出 #2
2 1 3 3 2 4
输入 #3
2 2 2 3 2 2 2 1
输出 #3
2 1
注意
此图展示了第二个示例案例。