题目描述

翁老师有 $n$ 个宝箱，每个宝箱有一个属性 $op_i\in \{\&,|,$^$\}$ ，一个魔法值 $a_i$，并且里面装着 $b_i$ 枚金币。其中 $\in$ 为属于的意思，指的是 $op_i$ 的值为 & | ^ 这三个符号之一，& | ^ 为位运算的按位与，按位或，异或符号。

假设你当前拥有 $x$ 枚金币，打开了一个 $\{op_i,a_i,b_i\}$ 的宝箱，那么你的金币数会变为 $(x\ op_i\ a_i)+b_i$ 枚。

你初始有 $0$ 枚金币，可以按照任意顺序打开宝箱，所有宝箱要 全部打开 且每个宝箱 只能打开一次。请问最终你最多能拥有多少枚金币？

输入描述

第一行输入一个整数 $n$，表示宝箱的个数。

接下来 $n$ 行，每一行输入一个字符 $op_i$ 和两个整数 $a_i,b_i$，表示每个宝箱的类型、魔法值以及金币枚数。

输出描述

输出共一行一个整数，表示答案。

3
& 3 4
| 3 0
^ 1 9

15

5
& 3 4
| 3 0
^ 1 9
& 3 9
^ 8 7

37

10
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000
| 1000000000 1000000000

11733215232

样例 1 解释

按照 $1\to 2\to 3$ 的顺序可以获得 $15$ 的金币。

• 第一次：sum = (sum & 3) + 4 = 4
• 第二次：sum = (sum | 3) + 0 = 7
• 第三次：sum = (sum ^ 1) + 9 = 15

提示

对于 $50\%$ 的数据，保证 $1\le n\le 5$.

对于 $100\%$ 的数据，保证 $1\le n\le 10$，$p_i\in \{\&,|,$^$\}$，$0\le a_i,b_i\le 10^9$.