Integers and Operators

問題文

$N$ 枚の整数の書かれたカードと、 $N$ 枚の演算子の書かれたカードがあります。
$i ~ (1 \le i \le N)$ 番目の整数の書かれたカードには整数 $A_i$ が書かれています。 $j ~ (1 \le j \le N)$ 番目の演算子の書かれたカードには演算子 $\mathrm{op}_j$ が書かれています。 書かれている演算子は + または ^ です。

変数 $x$ があり、はじめ $x = 0$ で初期化されています。あなたはこれから、以下の一連の手続きを $N$ 回繰り返します。

• 整数の書かれたカードと演算子の書かれたカードをそれぞれ $1$ 枚ずつ選び、それぞれ整数 $a$ と演算子 $\mathrm{op}$ が書かれているとする。
  • $\mathrm{op}$ が + のとき、 $x \leftarrow x + a$ に更新する。
  • $\mathrm{op}$ が ^ のとき、 $x \leftarrow x \oplus a$ に更新する。ここで $\oplus$ はビット単位 XOR を表す。
• 上記の整数の書かれたカードと演算子の書かれたカードを食べる。

手続きがすべて完了した後の $x$ としてあり得る最大値と最小値をそれぞれ求めてください。

制約

• $1 \le N \le 8$
• $1 \le A_i \le 10^9$
• $N, A_i$ は整数
• $\mathrm{op}_j$ は + または ^

入力

入力は以下の形式で標準入力から与えられる。

出力

$x$ としてあり得る最大値と最小値を、この順に空白区切りで出力せよ。

サンプル 1

入力

3
1 2 3
+ + ^

出力

6 0

例えば、以下のように手続きを行うことで、 $x = 6$ を達成することができます。

• $3$ の書かれたカードと ^ の書かれたカードを選ぶ。 $x = 3$ に更新される。
• $1$ の書かれたカードと + の書かれたカードを選ぶ。 $x = 4$ に更新される。
• $2$ の書かれたカードと + の書かれたカードを選ぶ。 $x = 6$ に更新される。

このような手続きによって得られる $x$ の最大値と最小値はそれぞれ $6, 0$ です。

サンプル 2

入力

8
9 323 640 833 102 773 889 900
+ ^ + ^ + + ^ ^

出力

4469 9