생명의 고리

콘웨이의 라이프 게임은 격자 위 세포에 적용하는 규칙이 몇 개뿐인데도 매우 복잡한 모양을 만들어 낸다. 이 문제에서는 그 게임을 1차원 원형 띠로 단순화한 판을 다룬다.

세포 $N$개가 원형으로 이어진 띠가 있다. 세포에는 1번부터 $N$번까지 순서대로 번호를 붙인다. 1번과 2번이 인접하고, 2번과 3번이 인접하며, 같은 방식으로 $N-1$번과 $N$번도 인접하다. 띠가 원형이므로 1번과 $N$번도 인접하다.

각 세포는 살아 있거나 죽어 있다. 살아 있는 세포는 문자 '1'로, 죽어 있는 세포는 문자 '0'으로 나타낸다. 세대가 넘어가면 모든 세포의 상태가 동시에 바뀐다. 어떤 세포의 이웃 두 개 중 현재 세대에 살아 있는 것이 정확히 하나면 그 세포는 다음 세대에 살아 있다. 그렇지 않으면 그 세포는 다음 세대에 죽어 있다.

띠의 처음 상태가 주어질 때, $T$세대가 지난 뒤의 상태를 구한다.

첫째 줄에 정수 $N$과 $T$가 공백으로 구분되어 주어진다 ($3 \le N \le 100000$, $1 \le T \le 10^{15}$).

둘째 줄에 처음 상태를 나타내는 길이 $N$의 문자열이 주어진다. 문자열의 각 문자는 '0' 또는 '1'이고, $i$번째 문자가 $i$번 세포의 처음 상태다. '1'은 살아 있는 세포, '0'은 죽어 있는 세포를 뜻한다.

$T$세대가 지난 뒤 세포 $N$개의 상태를 입력과 같은 형식과 순서로 한 줄에 출력한다. 즉 길이 $N$의 문자열을 출력하고, $i$번째 문자는 $i$번 세포가 살아 있으면 '1', 죽어 있으면 '0'이다.