1

Problem Statement

長さnのビット列がある．

左からi番目のビットが1のとき，スコアをa_i点得られる．
左からi番目のビットを中心に距離w以内にある1の個数(=|\{j \in \{1,...,n\}∩\{i-w,...,i+w\} | 左からj番目のビットが1\}|)が奇数のとき，スコアをb_i点得られる．

スコアを最も多く得られるようなビット列を求めよ．

Input

入力は以下の形式に従う．与えられる数は全て整数である．

n w
a_1 ... a_n
b_1 ... b_n

Constraints

• 1≦n≦1,000
• 1≦w≦1,000
• 0≦a_i≦10^5
• 0≦b_i≦10^5

Output

最も多くスコアを得られるビット列を1行に出力せよ．
そのような解が複数ある場合はどれを出力してもよい．

Sample Input 1

4 1
3 1 2 7
13 8 25 9

Output for the Sample Input 1

1001

3+7+13+8+25+9=65点が得られる．

Sample Input 2

2 1
1 1
3 3

Output for the Sample Input 2

10

01と出力してもよい．

---