← 返回题目列表

AtCoder · agc025_f

F. 加法与除法

中文机器翻译题面 查看原题

分数: 2400 点

问题陈述

高桥和青木喜欢计算,所以他们现在会玩数字。

首先,他们各自想出了一个正整数。高桥想出了 X,青木想出了 Y。 然后,他们就会通过重复下面的操作来享受乐趣 K 次:

  • 计算高桥当前保存的数字和青木当前保存的数字的按位与。让 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.


样本输入 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