分数: 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