No.387 ハンコ

レベル : / 実行時間制限 : 1ケース 5.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 35
作問者 : yosupotyosupot / テスター : antaanta
1 ProblemId : 1199 / 出題時の順位表

問題文

MKM君は長さ $N$ のマス目型のハンコを持っています。それぞれのマス目には、絵の具がついています。$i$ 個目のマス目の絵の具の色は、$a_i$ です。

MKM君は長さ $2 \times N-1$ のマス目型の紙を持っています。それぞれのマス目は、最初は何も絵の具はついていません。

MKM君は紙に何回かハンコを押します。この情報は長さ $N$ の数列 $b_i$ として与えられます。$b_i$ は $0$ か $1$ で、$1$ だったらハンコの左端が、紙の左から $i$ 個目のマス目と重なるようにハンコを押したということを表します。なお、同じ位置に $2$ 回ハンコを押すことは無いです。

MKM君は、それぞれのマスについて、何色の絵の具が混ざるか数えたいです。ですがこれは難しかったので、とりあえず答えが偶数か奇数かだけ求めることにしました。

なお、ハンコを押したあとは毎回紙を乾かすので、紙についた絵の具がハンコに移ることは考えなくてよいです。

入力

$N$
$a_1$ $a_2$ $\dots$ $a_N$
$b_1$ $b_2$ $\dots$ $b_N$

入力は全て整数。

$1 \le N \le 100,000$
$1 \le a_i \le 100,000$
$b_i$ は $0$ か $1$

出力

出力は $2 \times N-1$ 行からなる。
$i$ 行目には、$i$ 個目のマスの答えが偶数なら"EVEN"、奇数なら"ODD"と出力すること。

サンプル

サンプル1
入力
3
1 2 3
1 0 1
出力
ODD
ODD
EVEN
ODD
ODD

$b_1$ と $b_3$ が $1$ なのですが、仮に前者を先に押すこととすると、1回目のハンコは下図のようになります。



そして2回目のハンコは下図のようになります。



結果、下図のようになります。



よって、1, 2, 3, 4, 5個目のマス目の絵の具は{1}, {2}, {1, 3}, {2}, {3}なので、3個目だけ偶数です。

サンプル2
入力
3
1 2 1
1 0 1
出力
ODD
ODD
ODD
ODD
ODD

1, 2, 3, 4, 5個目のマス目の絵の具は{1}, {2}, {1}, {2}, {1}なので、全部奇数です。

提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。