外部サイトへ移動します

リンク先の URL を確認してから開いてください。

別タブで開く

D - ANDORXOR

作成者 sevenc_nanashi

テスター unbakedbread

配点 250 点

実行時間制限
2 秒
メモリ制限
512 MiB

問題文

ヴィータさんはマヤさんから手紙を受け取りました。

手紙には長さNNの数列AAと、AND、OR、XORのいずれかをN−1N-1個連結した文字列SSが書かれています。
SSをAND、OR、XORの演算子に分解し、それぞれをs1,s2,…,sN−1s_1, s_2, \ldots, s_{N-1}としたとき、A1s1A2s2A3…sN−1ANA_1 s_1 A_2 s_2 A_3 \ldots s_{N-1} A_Nの計算結果を求めてください。

ここで、各演算子は以下のように定義されます。

  • A AND BA \text{ AND } Bは、AAとBBを2進数で表したときに、両方のビットが1であるようなビットだけを1にした数を返します。例えば、5 AND 3=1012 AND 0112=0012=15 \text{ AND } 3 = 101_2 \text{ AND } 011_2 = 001_2 = 1です。
  • A OR BA \text{ OR } Bは、AAとBBを2進数で表したときに、どちらかあるいは両方のビットが1であるようなビットを1にした数を返します。例えば、5 OR 3=1012 OR 0112=1112=75 \text{ OR } 3 = 101_2 \text{ OR } 011_2 = 111_2 = 7です。
  • A XOR BA \text{ XOR } Bは、AAとBBを2進数で表したときに、どちらか一方のみのビットが1であるようなビットを1にした数を返します。例えば、5 XOR 3=1012 XOR 0112=1102=65 \text{ XOR } 3 = 101_2 \text{ XOR } 011_2 = 110_2 = 6です。

ただし、結合の強さはAND > OR > XORであり、同じ演算子は左結合で計算するとします。

制約

  • NN、AiA_iは整数
  • 2≤N≤1052 \leq N \leq 10^5
  • 0≤Ai≤230−10 \leq A_i \leq 2^{30} - 1
  • SSはN−1N-1個のAND、OR、XORのいずれかを連結した文字列である。

入力

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

NN A1A2A3…ANA_1 \quad A_2 \quad A_3 \quad \ldots \quad A_N SS

出力

計算結果を1行で出力してください。

サンプル 1

入力

4
1 2 4 8
ANDORXOR

出力

12

式は((1 AND 2) OR 4) XOR 8((1 \text{ AND } 2) \text{ OR } 4) \text{ XOR } 8となり、計算結果は1212です。

サンプル 2

入力

4
7 3 5 6
XORORAND

出力

0

式は7 XOR (3 OR (5 AND 6))7 \text{ XOR } (3 \text{ OR } (5 \text{ AND } 6))となり、計算結果は00です。

サンプル 3

入力

2
42 15
XOR

出力

37

式は42 XOR 1542 \text{ XOR } 15となり、計算結果は3737です。

サンプル 4

入力

11
3 12 5 10 6 17 9 20 7 25 2
ORXORXORORORXORORXORXOROR

出力

20

ORを先に計算すると、式は15 XOR 5 XOR 31 XOR 29 XOR 7 XOR 2715 \text{ XOR } 5 \text{ XOR } 31 \text{ XOR } 29 \text{ XOR } 7 \text{ XOR } 27となり、計算結果は2020です。

参加受付は終了しました。