시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 (추가 시간 없음) 1024 MB111100.000%

문제

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 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$

출력

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

제한

  • $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.

예제 입력 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

노트

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