灰之魔女栽魔法树
时间限制:C/C++/Rust/Pascal 1秒,其他语言2秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

戴着这枚彰显魔女身份的胸针,披着一头灰色秀发,其美貌与才能散发的光芒,连太阳见了都会不由眯起眼睛的美女,究竟是谁呢?

这是发生在一位旅行者-灰之魔女伊蕾雅旅行途中的故事。驻留在旅馆的伊蕾雅,某日突发奇想想要在旅馆门口裁树。一开始,门口只有刚迈进土里的树苗(高度为 0),每棵树从左往右编号依次为1-n。每天过后,每棵树会自然生长 1 单位高度。但伊蕾雅觉得这太慢了,于是她决定加速该过程。

具体来说,伊蕾雅的栽树过程持续m天,在每一天早上,她有三种操作:

op=1 她选择某棵树 x 对其施展魔法,该效果持续 k 天(包括当天)。拥有魔法效果的树每天晚上会额外生长 1 单位高度。若施展时该树已经存在魔法效果,则忽略原来的魔法效果。

op=2 她选择取消某棵树 x 的魔法效果。

op=3 她想知道该天某棵树 x 的高度。

输入描述:

第一行输入两个整数 nmk 。1\le n \le 2*10^51\le m\le 2*10^51 \le k\le 10

接下来 m 行,第 i 行输出格式为 op xop \in \{1,2,3\},代表第 i 天的操作。

输出描述:

对于每个 op=3,输出一行一个整数 h,代表该树的高度。 
示例1

输入

复制
7 9 3
3 1
3 1
1 5
1 5
1 1
3 1
2 1
3 1
3 5

输出

复制
0
1
6
9
12