配点 : $2400$ 点

問題文

高橋君と青木君は計算をするのが大好きです。 そこで、二人は計算をして遊ぶことにしました。

まず二人は正整数を $1$ つずつ用意しました。高橋君の用意した数は $X$、青木君の用意した数は $Y$ です。 そして、以下の手順を $K$ 回繰り返すことで、計算を楽しむことにしました。

• 高橋君の持っている数と青木君の持っている数の bitwise AND を計算し、それを $Z$ とする。
• そして、高橋君と青木君の持っている数それぞれに $Z$ を足す。

しかし、計算の大好きな二人にもこの計算は酷です。 そこで彼らの代わりに、高橋君が最終的に持つことになる数と、青木君が最終的に持つことになる数を求めてあげてください。

ただし、入出力は $2$ 進数表記で行われることに注意してください。 特に、$X,Y$ はそれぞれ長さ $N,M$ の0,1 のみからなる文字列 $S,T$ として入力され、$S,T$ の先頭の文字は 1 であることが保証されています。

制約

• $1 \leq K \leq 10^6$
• $1 \leq N,M \leq 10^6$
• $S,T$ の先頭の文字は 1 である。

入力

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

$N$ $M$ $K$

$S$

$T$

出力

一行目には高橋君の最終的に持つことになる数を、二行目には青木君の最終的に持つことになる数を出力せよ。 ただし、それらを $2$ 進数表記で表し、先頭の文字が 1 であるような 0,1 のみからなる文字列として出力せよ。

2 3 3
11
101

10000
10010

各操作後の $X,Y$ の値は以下のようになります。

• 一回目の操作後は $(X,Y)=(4,6)$ になる。
• 二回目の操作後は $(X,Y)=(8,10)$ になる。
• 三回目の操作後は $(X,Y)=(16,18)$ になる。

5 8 3
10101
10101001

100000
10110100

10 10 10
1100110011
1011001101

10000100000010001000
10000100000000100010