题目描述

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

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

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

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

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

输入格式

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

$N$ $M$ $K$ $S$ $T$

输出格式

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

题目大意

给定长度为 $n$ 的二进制数 $x$ 和长度为 $m$ 的 $y$ 对他们进行 $k$ 次以下操作

• 令$z=x \ \& \ y$，并将 $x$ 和 $y$ 加上 $z$

求出 $k$ 次操作后的 $x$ 和 $y$

2 3 3
11
101

10000
10010

5 8 3
10101
10101001

100000
10110100

10 10 10
1100110011
1011001101

10000100000010001000
10000100000000100010

提示

制約

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

Sample Explanation 1

各操作後の $X,Y$ の値は以下のようになります。 - 一回目の操作後は $(X,Y)=(4,6)$ になる。 - 二回目の操作後は $(X,Y)=(8,10)$ になる。 - 三回目の操作後は $(X,Y)=(16,18)$ になる。