1

Time Limit : 1 sec, Memory Limit : 65536 KB

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と出力してもよい.


Source: Ritsumeikan University Competitive Programming Camp 2013, Day2 , Problem set from Osaka University teams, Shiga, Japan, 2013-03-12
Problem Setter:  komiya