To celebrate the significant progress in epidemic prevention and control, a shopping mall is holding a promotional event, offering customers some discount amounts based on the following rules:

1. Each customer can choose any integer as their lucky number.
2. Each customer's initial discount amount is $0$.
3. The mall has $n$ reward conditions, each corresponding to a reward value $w_i$.
4. Each customer must check their lucky number against these $n$ reward conditions in order. If the customer's chosen lucky number satisfies the $i$-th condition, their discount amount is XORed with the reward value corresponding to that condition.

There are three types of reward conditions. Suppose the customer's chosen lucky number is $x$:

1. Interval condition: has two parameters $L$ and $R$. The condition is satisfied if $L \le x \le R$. It is guaranteed that $L < R$.
2. Equality condition: has one parameter $A$. The condition is satisfied if $x = A$.
3. Inequality condition: has one parameter $B$. The condition is satisfied if $x \neq B$.

Xiao Yan has obtained information about all the reward conditions. He wants to know the maximum discount amount a customer can receive and the corresponding lucky number. Please help him calculate this.

Input

The first line contains a positive integer $n$, representing the number of reward conditions.

The next $n$ lines each contain three or four integers representing a reward condition. The first integer $t_i$ in each line represents the type of the reward condition:

1. If $t_i = 1$, it is an interval condition, followed by three integers representing $L, R, w_i$.
2. If $t_i = 2$, it is an equality condition, followed by two integers representing $A, w_i$.
3. If $t_i = 3$, it is an inequality condition, followed by two integers representing $B, w_i$.

Output

Output two integers on a single line. The first number represents the maximum discount amount that can be obtained, and the second number represents the corresponding lucky number.

If there are multiple lucky numbers that yield the maximum discount amount, output the one with the smallest absolute value. If there is still a tie, output the largest value.

Examples

Input 1

4
1 -100 -80 37
2 -3 3
3 4 64
1 -10 1024 156

Output 1

223 -3

Note 1

The lucky number $-3$ satisfies reward conditions $2, 3,$ and $4$. The reward amount is $3 \oplus 64 \oplus 156 = 223$, where $\oplus$ denotes the XOR operation.

Subtasks

$20\%$ of the data satisfies: $n, |L|, |R|, |A|, |B| \le 1000$.

$40\%$ of the data satisfies: $n \le 1000$.

$100\%$ of the data satisfies: $1 \le n \le 10^5, |L|, |R|, |A|, |B| \le 10^9, 1 \le w_i \le 10^9$.