Description

A sequence $a$ is initially empty. Let $n$ denote its current length. The following two operations are supported:

• Append a value to the end of the sequence.
• Given an index $x$, find$$\max_{1 \leq i \leq n,\ i \neq x}\left\lfloor\frac{a_i}{|x-i|}\right\rfloor. $$

If there is no valid index $i$ (that is, if $n=1$), the answer is $0$.

Input Format

The first line contains one integer $m$, the number of operations.

Each of the next $m$ lines contains two integers $op$ and $x$, describing an operation:

• If $op=1$, append the value $x$ to the end of the sequence.
• If $op=2$, query the current sequence using $x$ as an index. It is guaranteed that $1\leq x\leq n$.

Output Format

For each operation with $op=2$, output the answer on a separate line.

Sample

Input #1

3
1 1
1 2
2 1

Output #1

2

Constraints

For all test cases:

• $1\leq m\leq 10^5$;
• $0\leq a_i\leq 10^5$;
• for an operation with $op=1$, $0\leq x\leq 10^5$;
• for an operation with $op=2$, $1\leq x\leq n$.

The appended values and query indices are generated at random within their respective valid ranges.