K. Game and Queries
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Alice and Bob are going to play a game. The rule of the game is as follows:

  • There are some monsters, each of which has a specified HP.
  • Alice and Bob take turns alternately, with Alice going first.
  • In Alice's turn, she chooses one of the monsters and increases its HP by $$$1$$$.
  • In Bob's turn, he chooses one of the monsters and decreases its HP by $$$2$$$. If the monster's HP becomes $$$0$$$ or less, the monster disappears.
  • The game ends when $$$k$$$ monsters disappear.

Alice's objective is to finish the game as late as possible, while Bob's is as soon as possible.

Initially, there are no monsters. You have to process $$$Q$$$ queries of the following types:

  • Type $$$1$$$: You are given two integers $$$X_i$$$ and $$$Y_i$$$. After this query, the number of monsters whose HPs are $$$X_i$$$ becomes $$$Y_i$$$.
  • Type $$$2$$$: Given an integer $$$K_i$$$, calculate how many turns would Bob take if the game started with current monsters and $$$k=K_i$$$, assuming both players play optimally.

Note that the game doesn't happen in reality, and the monsters don't disappear.

Input

Input is given from Standard Input in the following format:

$$$Q$$$

Description of the $$$1$$$-st query

Description of the $$$2$$$-nd query

$$$\vdots$$$

Description of the $$$Q$$$-th query

The description of each query is in one of the following formats:

Type $$$1$$$

$$$1$$$ $$$X_i$$$ $$$Y_i$$$

Type $$$2$$$

$$$2$$$ $$$K_i$$$

Constraints:

  • $$$1 \leq Q \leq 3 \times 10^5$$$
  • $$$1 \leq T_i \leq 2$$$
  • $$$1 \leq X_i \leq 10^6$$$
  • $$$0 \leq Y_i \leq 10^6$$$
  • $$$1 \leq K_i \leq ($$$ the number of current monsters $$$)$$$
  • There is at least one query of the type $$$2$$$
  • All values in input are integers.
Output

For each query of the type $$$2$$$, print the answer in a line.

Examples
Input
6
1 1 4
2 3
1 2 3
2 6
1 2 2
2 6
Output
3
7
8
Input
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
Output
12
12
3
42
7
246
25
301
91
8
32
Note

In the example $$$1$$$, after the $$$5$$$-th query, there are $$$4$$$ monsters whose HPs are $$$1$$$ and $$$2$$$ monsters whose HPs are $$$2$$$.