Problem Description

To celebrate major progress in epidemic prevention and control, a shopping mall is holding a promotional event and offers customers some discount credits under the following rules.

1. Each customer may choose any integer as their lucky number.
2. Each customer’s initial discount credit is $0$ yuan.
3. The mall has $n$ reward conditions, each with a corresponding reward value $w_i$.
4. Each customer checks these $n$ reward conditions in order. If the lucky number chosen by the customer satisfies the $i$-th condition, then their discount credit will be XORed with the reward value corresponding to that condition.

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

1. Interval condition: it 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: it has one parameter $A$. The condition is satisfied if $x = A$.
3. Inequality condition: it has one parameter $B$. The condition is satisfied if $x \neq B$.

Xiaoyan knows all the reward conditions. He wants to know the maximum discount credit a customer can obtain and the corresponding lucky number. Please help him compute it.

Input Format

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

The next $n$ lines each contain three or four integers describing one reward condition. The first integer of each line is $t_i$, representing the type of the reward condition.

1. If $t_i = 1$, the condition is an interval condition. The next three integers are $L, R, w_i$.
2. If $t_i = 2$, the condition is an equality condition. The next two integers are $A, w_i$.
3. If $t_i = 3$, the condition is an inequality condition. The next two integers are $B, w_i$.

Output Format

Output one line with two integers. The first number is the maximum discount credit that can be obtained, and the second number is the corresponding lucky number.

If multiple lucky numbers can achieve the maximum discount credit, output the one with the smallest absolute value. If there are still multiple, output the largest one.

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

223 -3

Hint

Sample Explanation

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

Constraints and Conventions

$20\%$ of the testdata satisfy: $n, |L|, |R|, |A|, |B| \le 1000$.
$40\%$ of the testdata satisfy: $n \le 1000$.
$100\%$ of the testdata satisfy: $1 \le n \le 10^5, |L|, |R|, |A|, |B| \le 10^9, 1 \le w_i \le 10^9$.

Translated by ChatGPT 5