E. 海明码

内存限制:512 MiB 时间限制:1500 ms 标准输入输出
题目类型:传统 评测方式:文本比较

题目描述

小 A 想给小 B 传输一串长度为 的二进制数 ,但由于外界环境的干扰,传输的二进制数的某一位可能发生改变,为了应对这个问题,小 A 学习了海明码。

海明码(Hamming code)是一种线性误差更正码,由理查德·海明(Richard Hamming)在1950年发明。它能够检测和纠正单一比特的错误。海明码通过在数据位之间插入额外的校验位来实现这种错误检测和更正的功能。

,则小 A 会在这 位二进制码的后面补上

其中 的值为所有二进制第 位为 的数 异或和。例如 ,则 ,而 为所有 的异或和,即

这样将小A 将 传输给小 B ,那么小B 得到的是 ,小 B 就可以通过 的值来判断他收到的 相比,是否有某一位发生了改变,如果发生了那改变的是哪一位?

现在小 B 希望得到 到底是什么,请你帮帮他!

小 A 贴心的为小 B 提供了一个判断过程:

  • ,则说明
  • ,按接下来的步骤处理:
    • 设一个未知数
    • 对于每一个 ,我们设 的值为所有二进制第 位为 的数 异或和.
      • ,我们就令 二进制的第 位是
      • ,我们就令 二进制的第 位是
    • 最后若
    • 否则对于所有

输入格式

行包含一个正整数 ,表示二进制数的位数。

行为 位的 字符串,表示小 B 收到的

输出格式

输出一行长度为 串,表示

样例

样例一

输入

7
11100010101

输出

1110101

样例解释

因为 ,且

所以 ,所以

数据范围与提示

对于所有数据 ,保证数据合法。

测试点 数据范围 特殊性质
保证 且为整数
无限制

保证

大样例见附加文件