#P5561. 2021蓝桥杯b——G异或变换(待加强)

2021蓝桥杯b——G异或变换(待加强)

Background

小蓝有一个 01 串 s=s1s2s3sns = s_1 s_2 s_3 · · · s_n 。 以后每个时刻,小蓝要对这个 01 串进行一次变换。每次变换的规则相同。 对于 01 串 s=s1s2s3sns = s_1 s_2 s_3 · · · s_n ,变换后的 01 串 s=s1s2s3sns′ = s′_1 s′_2 s′_3· · · s′_n 为:

s1=s1s′1 = s_1

si=si1sis′i = s_{i-1} ⊕ s_i

其中 aba ⊕ b 表示两个二进制的异或,当 a 和 b 相同时结果为 0,当 a 和 b不同时结果为 1。 请问,经过 t 次变换后的 01 串是什么?

Format

Input

输入的第一行包含两个整数 n, t,分别表示 01 串的长度和变换的次数。

第二行包含一个长度为 nn的 01 串。

Output

输出一行包含一个 01 串,为变换后的串。

Samples

5 3
10110
11010

Limitation

1s, 1024KiB for each test case.