题目描述

高桥和青木喜欢计算，所以他们现在要玩数字游戏了。

首先，他们各自想出了一个正整数。高桥想到了 $X$，青木想到了 $Y$。然后，他们将通过重复进行以下操作 $K$ 次来享受乐趣：

• 计算高桥当前保存的数字与青木当前保存的数字的按位 AND 运算。令 $Z$ 为结果。
• 然后，将 $Z$ 分别加到高桥和青木当前保留的数字上。

然而，即使对于这两位数学狂人来说，这也是太多的工作了。你能找到最终由高桥保存的数字和青木保存的数字吗？

注意输入和输出都是使用二进制表示。特别地，$X$ 和 $Y$ 以字符串 $S$ 和 $T$ 的形式给出，长度分别为 $N$ 和 $M$，字符串只包含 0 和 1，并且保证初始字符是 1。

约束条件

• $1 ≤ K ≤ 10^6$
• $1 ≤ N,M ≤ 10^6$
• 字符串 $S$ 和 $T$ 的初始字符是 1。

输入格式

从标准输入读入数据，格式如下：

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

输出格式

第一行中打印最终由高桥保存的数字；第二行中打印最终由青木保存的数字。这些数字应以字符串形式表示，并且以 0 和 1 开头。

示例输入 1

2 3 3
11
101

示例输出 1

10000
10010

每次操作后，$X$ 和 $Y$ 的值如下：

• 第一次操作后：$(X,Y)=(4,6)$。
• 第二次操作后：$(X,Y)=(8,10)$。
• 第三次操作后：$(X,Y)=(16,18)$。

示例输入 2

5 8 3
10101
10101001

示例输出 2

100000
10110100

示例输入 3

10 10 10
1100110011
1011001101

示例输出 3

10000100000010001000
10000100000000100010