There is an array $A$ of length $2 \times 10^9 + 1$. The indices of $A$ are integers in the range $[-10^9, 10^9]$. Initially, all elements of $A$ are $0$ (i.e., $A[-10^9] = A[-10^9+1] = \ldots = A[10^9] = 0$).

The array receives $q$ queries, which are of the following two types:

• 1 x y: For all $-10^9 \le i \le 10^9$, set $A[i] = A[i] + |i - x| + y$.
• 2: Output the position $m$ of the first occurrence of the minimum value of $A$, and $A[m]$. (First occurrence means the smallest index.)

Input

The first line contains an integer $q$ ($1 \le q \le 2 \times 10^5$).

The next $q$ lines each contain a query in one of the above forms ($-10^9 \le a, b \le 10^9$).

The first query is always of the form 1 x y.

Output

For every query of type 2, output the position $m$ of the first occurrence of the minimum value of $A$ and $A[m]$, separated by a space.

Examples

Input 1

4
1 4 2
2
1 1 -8
2

Output 1

4 2
1 -3

Input 2

4
1 -1000000000 1000000000
1 -1000000000 1000000000
1 -1000000000 1000000000
2

Output 2

-1000000000 3000000000