小明和安琪是好朋友，最近，他们的谈话被一家侦探公司监控，所以他们想将他们的谈话内容进行加密处理。于是，他们发明了一种新的加密方式，每条信息都被编译成二进制数B(明文)，其长度为N，每次向右移动0,1,...,K-1位。然后对每一列进行异或操作，并且把最终所得的结果记录下来。

例如：B=1001010,K=4

1001010
 1001010
  1001010
^  1001010
-----------
1110100110

我们将该结果称为S(密文)。例如上述例子的结果为：
1110100110
最后，将编码的信息S和K发送给安琪。
小明已经实现了这种编码的加密过程，但他要求安琪去写一个程序去实现这种编码的解密过程，你能帮助安琪实现解密过程吗？

输入描述：

第一行输入两个整数N和K
第二行输入一个二进制字符串S，长度是N+K-1

输出描述：

输出明文B

示例：

输入1

7 4
1110100110

输出1

1001010

思路

行数\位数 0 1 2 3 4 5 6 7 8 9
原文 x             0 0 0
»1 0 ↘             0 0
»2 0 0 ↘             0
»3 0 0 0 ↘            
密文 1 1 1 0 1 0 0 1 1 0

由题意知，右移后高位补0，考虑x，x往下一直异或0就得到了密文的最高位1，即x^0^0^0 == 1。可知x==1，将x处填1,并且沿x的对角线向右下角延长的位置上全部填入x的值：

行数\位数 0 1 2 3 4 5 6 7 8 9
原文 1 y           0 0 0
»1 0 1 ↘           0 0
»2 0 0 1 ↘           0
»3 0 0 0 1 ↘          
密文 1 1 1 0 1 0 0 1 1 0

同理有y^1^0^0 == 1 => y == 0，并向右下角延长：

行数\位数 0 1 2 3 4 5 6 7 8 9
原文 1 0 z         0 0 0
»1 0 1 0 ↘         0 0
»2 0 0 1 0 ↘         0
»3 0 0 0 1 0 ↘        
密文 1 1 1 0 1 0 0 1 1 0

同理z == 0

……

行数\位数 0 1 2 3 4 5 6 7 8 9
原文 1 0 0 1 0 1 0 0 0 0
»1 0 1 0 0 1 0 1 0 0 0
»2 0 0 1 0 0 1 0 1 0 0
»3 0 0 0 1 0 0 1 0 1 0
密文 1 1 1 0 1 0 0 1 1 0

当原文一行填满时，前N位即为所求。

这样做需要创建一个N*K的矩阵，空间复杂度非常高：

行数\位数 0 1 2 3 4 5 6 7 8 9
原文 1 0 0 🐇 🐱 🐕 0 0 0 0
»1 0 1 0 0 1 0 🐕 0 0 0
»2 0 0 1 0 0 1 🐱 1 0 0
»3 0 0 0 1 0 0 🐇 0 1 0
密文 1 1 1 0 1 0 0 1 1 0

其实不需要保存二维矩阵，根据对称性有：
🐇 == 🐇、🐱 == 🐱、🐕 == 🐕
也就是说某一位与正下方a行的同一位做异或其实就是该位与比自己高a位的左边某一位做异或。所以其实只用一个N+K-1位的数组即可。

解答

class Solution:
    def key(self,n,k,num):
        key = num
        ans = [0 for i in range(n+k-1)]
        for i in range(n+k-1):
            ans[i] = key[i]
            left = max(0,i-(k-1))
            for j in range(left,i):
                ans[i] ^= ans[j]
        return ans[:n]

import sys
if __name__ == "__main__":
    solution = Solution()

    n,k = list(map(int,sys.stdin.readline().strip().split()))
    num = list(map(int,sys.stdin.readline().strip()))

    res = solution.key(n,k,num)
    for bit in res:
        print(bit,end='')