#3308. 「联合省选 2020 B」幸运数字

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: EntropyIncreaser

题目描述

为庆祝疫情防治取得重大进展,某商场举行酬宾活动,给顾客一些优惠额度,规则如下:

  1. 每位顾客可以任意选择一个整数作为自己的幸运数字。

  2. 每位顾客的初始优惠额度为 0 元。

  3. 商场有 n 个奖励条件,对应不同的奖励额度 w_i

  4. 每位顾客需要依次比对这 n 个奖励条件,如果该位顾客选择的幸运数字满足第 i 个条件,那么他的优惠额度就会异或上这个条件所对应的奖励额度。

奖励条件共有三种,假设顾客选择的幸运数字为 x

  1. 区间型条件,其有两个参数 L R ,满足条件为 L \le x\le R 。保证 L < R

  2. 相等型条件,其有一个参数 A ,满足条件为 x = A

  3. 不等型条件,其有一个参数 B ,满足条件为 x \neq B

小炎同学获知了所有奖励条件的信息,他希望知道一位顾客能够得到的最大优惠额度以及对应的幸运数字是多少,请你帮他计算。

输入格式

第一行包含一个正整数 n ,代表奖励条件的数量。

接下来 n 行,每行三个或四个整数表示一个奖励条件。每行第一个整数 t_i 代表奖励条件的类型:

  1. t_i = 1 则该条件是区间型条件,接下来三个整数,分别代表 L, R, w_i

  2. t_i = 2 则该条件是相等型条件,接下来两个整数,分别代表 A, w_i

  3. t_i = 3 则该条件是不等型条件,接下来两个整数,分别代表 B, w_i

输出格式

输出一行两个整数,第一个数代表能够得到的最大优惠额度,第二个数代表对应的幸运数字。

如果有多个幸运数字能够得到最大优惠额度,输出绝对值最小的那个。如果还有多个,则输出值最大的。

样例

样例输入

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

样例输出

223 -3

样例解释

幸运数字 -3 满足奖励条件 2, 3, 4 ,奖励额度为 3\oplus 64\oplus 156 = 223 ,其中 \oplus 表示异或运算。

数据范围与提示

20\% 的数据满足: n, |L|, |R|, |A|, |B| \le 1000

40\% 的数据满足: n\le 1000

100\% 的数据满足: 1\le n\le 10^5, |L|, |R|, |A|, |B|\le 10^9, 1\le w_i\le 10^9