小Artem发明了时光机!他可以及时去任何地方,但他所有的想法当然都与计算机科学有关。他想将这个时间机器应用到一个众所周知的数据结构:多重集。
Artem 想要创建一个基本的整数多重集。他希望这些结构支持三种类型的操作:
1. 将整数添加到多重集。请注意,集合和多重集之间的区别在于多重集可以存储一个整数的多个实例。
2. 从多重集中删除整数。仅删除该整数的一个实例。 Artem 不想处理任何异常,因此他假设每次调用删除操作时,该整数都会出现在多重集中。
3. 计算多重集中存储的给定整数的实例数。
但是时间机器呢? Artem 并不简单地将运算一一应用于多重集,他现在旅行到不同的时刻并在那里应用他的运算。考虑以下示例。
- 第一个 Artem 在第一个时刻将整数 5 添加到多重集。
- 然后 Artem 将整数 3 添加到时刻 5 的多重集。
- 然后 Artem 询问第 6 时刻多重集中有多少个 5。答案是 1。
- 然后 Artem 返回过去,询问在时刻 4 的集合中有多少个整数 3。由于 3 是在时刻 5 才添加的,所以在时刻 4 的整数 3 的数量等于 0。
- 然后 Artem 再次回到过去,并在第 3 时刻从多重集中删除 5。
- 最后 Artyom 在第 7 时刻询问集合中有多少个整数 5。结果是 0,因为我们在 3 时刻删除了 5。
请注意,Artem 非常不喜欢异常,因此他确保在每次更改后,所有删除操作都仅应用于多重集中存在的元素。第三类查询的答案是在 Artem 进行相应查询时计算的,并且不会受到他将来所做的更改的任何影响。
帮助 Artem 实现时间旅行者多重集。
输入
输入的第一行包含一个整数 n (1 ≤ n ≤ 100 000) — Artem 的查询数。
然后接下来的 n 行是查询描述。它们每个都包含三个整数 ai、ti 和 xi (1 ≤ ai ≤ 3, 1 ≤ ti, xi ≤ 109)——分别是查询类型、Artem 执行此查询所需的时间以及查询本身的值。保证所有时刻都是不同的,并且在应用每个操作之后,第一类型和第二类型的所有操作都是一致的。
输出
对于每个询问操作,输出在给定时刻查询的整数实例的数量。
示例
输入 #1
6 1 1 5 3 5 5 1 2 5 3 6 5 2 3 5 3 7 5
输出 #1
1 2 1
输入 #2
3 1 1 1 2 2 1 3 3 1
输出 #2
0