CF707D.Persistent Bookcase

Recently in school Alina has learned what are the persistent data structures: they are data structures that always preserves the previous version of itself and access to it when it is modified.

After reaching home Alina decided to invent her own persistent data structure. Inventing didn't take long: there is a bookcase right behind her bed. Alina thinks that the bookcase is a good choice for a persistent data structure. Initially the bookcase is empty, thus there is no book at any position at any shelf.

The bookcase consists of n shelves, and each shelf has exactly m positions for books at it. Alina enumerates shelves by integers from 1 to n and positions at shelves — from 1 to m. Initially the bookcase is empty, thus there is no book at any position at any shelf in it.

Alina wrote down q operations, which will be consecutively applied to the bookcase. Each of the operations has one of four types:

• 1 i j — Place a book at position j at shelf i if there is no book at it.
• 2 i j — Remove the book from position j at shelf i if there is a book at it.
• 3 i — Invert book placing at shelf i. This means that from every position at shelf i which has a book at it, the book should be removed, and at every position at shelf i which has not book at it, a book should be placed.
• 4 k — Return the books in the bookcase in a state they were after applying k-th operation. In particular, k = 0 means that the bookcase should be in initial state, thus every book in the bookcase should be removed from its position.

After applying each of operation Alina is interested in the number of books in the bookcase. Alina got 'A' in the school and had no problem finding this values. Will you do so?

最近，阿莉娜在学校学习了什么是持久化数据结构：这类数据结构在被修改时，总是保留其先前的版本，并允许对这些旧版本进行访问。

回到家后，阿莉娜决定发明一种属于自己的持久化数据结构。发明过程并没有花费太长时间：她的床后正好有一排书架。阿莉娜认为，这排书架是实现持久化数据结构的一个绝佳选择。初始时书架为空，即任意一层书架上的任意位置均无书籍。

该书架共包含 $n$ 层，每层恰好有 $m$ 个放书的位置。阿莉娜用 $1$ 到 $n$ 的整数为各层编号，用 $1$ 到 $m$ 的整数为每层上的各位置编号。初始时书架为空，因此书架中任意一层的任意位置上均无书籍。

阿莉娜写下了 $q$ 个操作，将按顺序依次应用于该书架。每个操作属于以下四种类型之一：

• 1 i j — 若第 $i$ 层第 $j$ 个位置上尚无书籍，则在此处放置一本书；
• 2 i j — 若第 $i$ 层第 $j$ 个位置上有书籍，则将其移除；
• 3 i — 对第 $i$ 层执行“翻转”操作：即所有已有书的位置上的书被移除，所有空位置上则放置一本书；
• 4 k — 将书架恢复至执行完第 $k$ 个操作后的状态。特别地，当 $k = 0$ 时，表示应恢复至初始状态，即书架中所有书籍均须被移除。

每次操作执行完毕后，阿莉娜都希望知道此时书架中书籍的总数。阿莉娜在学校得了“A”，轻松解决了这个问题。你也能做到吗？

The first line of the input contains three integers n, m and q (1 ≤ n, m ≤ 103, 1 ≤ q ≤ 105) — the bookcase dimensions and the number of operations respectively.

The next q lines describes operations in chronological order — i-th of them describes i-th operation in one of the four formats described in the statement.

It is guaranteed that shelf indices and position indices are correct, and in each of fourth-type operation the number k corresponds to some operation before it or equals to 0.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 \leq n, m \leq 10^3$，$1 \leq q \leq 10^5$），分别表示书架的尺寸以及操作的数量。

接下来的 $q$ 行按时间顺序描述各操作——其中第 $i$ 行描述第 $i$ 个操作，格式为题目陈述中所述的四种格式之一。

保证书架索引和位置索引均合法；且在每种第四类操作中，数字 $k$ 要么对应之前某个操作的编号，要么等于 $0$。

For each operation, print the number of books in the bookcase after applying it in a separate line. The answers should be printed in chronological order.

对于每个操作，请在单独一行中输出执行该操作后书架上的书籍数量。答案应按时间顺序输出。

This image illustrates the second sample case.

该图展示了第二个样例。