Alice 和 Bob 正在玩一个游戏。游戏规则如下：

• 有一些怪物，每个怪物都有一个指定的生命值（HP）。
• Alice 和 Bob 轮流行动，Alice 先手。
• 在 Alice 的回合，她选择一个怪物并将其 HP 增加 1。
• 在 Bob 的回合，他选择一个怪物并将其 HP 减少 2。如果怪物的 HP 变为 0 或更低，该怪物就会消失。
• 当有 $k$ 个怪物消失时，游戏结束。

Alice 的目标是尽可能晚地结束游戏，而 Bob 的目标是尽可能早地结束游戏。 最初没有怪物。你需要处理 $Q$ 个查询，查询类型如下：

• 类型 1：给定两个整数 $X_i$ 和 $Y_i$。在此查询后，HP 为 $X_i$ 的怪物数量变为 $Y_i$。
• 类型 2：给定一个整数 $K_i$，假设双方都采取最优策略，计算如果游戏以当前怪物状态开始且 $k = K_i$ 时，Bob 需要多少回合才能结束游戏。

注意，游戏并非实际发生，怪物也不会真的消失。

输入格式

输入通过标准输入给出，格式如下：

$Q$ 第 1 个查询的描述 第 2 个查询的描述 ... 第 $Q$ 个查询的描述

每个查询的描述格式如下：

类型 1 $1 \ X_i \ Y_i$

类型 2 $2 \ K_i$

数据范围

• $1 \le Q \le 3 \times 10^5$
• $1 \le T_i \le 2$
• $1 \le X_i \le 10^6$
• $0 \le Y_i \le 10^6$
• $1 \le K_i \le (\text{当前怪物总数})$
• 至少存在一个类型 2 的查询
• 输入中的所有值均为整数

输出格式

对于每个类型 2 的查询，输出一行答案。

样例

样例输入 1

6
1 1 4
2 3
1 2 3
2 6
1 2 2
2 6

样例输出 1

3
7
8

样例输入 2

20
1 1 12
2 12
1 2 15
2 12
2 3
1 12 10
2 27
1 14 6
2 7
2 43
2 22
1 8 7
1 1 11
2 49
1 5 19
2 38
2 8
1 12 14
1 16 1
2 24

样例输出 2

12
12
3
42
7
246
25
301
91
8
32

说明

在样例 1 中，第 5 个查询之后，有 4 个 HP 为 1 的怪物和 2 个 HP 为 2 的怪物。