题目描述

高桥君和青木君非常喜欢做计算。于是，他们决定通过做计算来玩耍。

首先，两人各自准备了一个正整数。高桥君准备的数为 $X$，青木君准备的数为 $Y$。然后，他们重复以下步骤 $K$ 次，以此来享受计算的乐趣。

• 计算高桥君手中的数与青木君手中的数的按位与（bitwise AND），记为 $Z$。
• 然后，将 $Z$ 分别加到高桥君和青木君手中的数上。

然而，即使是非常喜欢计算的两人，这样的计算也太辛苦了。因此，请你帮他们计算出最终高桥君和青木君手中各自会得到的数。

注意，输入输出均采用二进制表示。特别地，$X,Y$ 分别以长度为 $N,M$ 的仅由 0、1 组成的字符串 $S,T$ 输入，并保证 $S,T$ 的首位字符均为 1。

输入格式

输入以如下格式从标准输入读入。

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

输出格式

第一行输出高桥君最终得到的数，第二行输出青木君最终得到的数。均需以二进制字符串形式输出，且首位字符为 1，仅包含 0、1。

样例 1

输入

2 3 3
11
101

输出

10000
10010

样例 2

输入

5 8 3
10101
10101001

输出

100000
10110100

样例 3

输入

10 10 10
1100110011
1011001101

输出

10000100000010001000
10000100000000100010

说明/提示

约束条件

• $1 \leq K \leq 10^6$
• $1 \leq N, M \leq 10^6$
• $S,T$ 的首位字符均为 1。

样例解释 1

每次操作后 $X,Y$ 的值如下所示：

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

由 ChatGPT 4.1 翻译