题目描述

也许你听说过康威生命游戏（Conway's Game of Life）。康威生命游戏适用于方格组成的矩阵。但它可以产生十分复杂的结构。在这道题目中，我们将探讨简化版的生命游戏。

将一个圆环分为 N 段，将这 N 段顺时针依次编为1,⋯,N 号。 每一段内有一个细胞, 要么是生存状态（以 1 表示），要么是死亡状态（以 0 表示）。 我们把每个细胞两边的细胞称作它的邻居。

在时刻0, 给出那些活着的细胞的位置, 今后任何时刻的状态, 都已经被它前面的状态按照下面的游戏规则无情地规定下来了:

出生: 在时刻t处于死亡状态的细胞, 如果他的两个邻居中恰好有1个在时刻t活着, 那么这个细胞将在t+1时刻变成生存状态。

死亡: 在时刻t处于生存状态的细胞, 如果他的两个邻居中恰好有0个（孤立）或2个（过于拥挤）在时刻t活着, 那么这个细胞将在t+1时刻变成死亡状态。

生存: 在时刻t处于生存状态的细胞, 如果他的两个邻居中恰好有1个在时刻t活着, 那么这个细胞在t+1时刻仍然会继续保持生存状态。

给出N和时刻0时每个细胞的生存状态, 求出时刻T时细胞的生存状态

输入格式

输入共两行:

第1行: 2个正整数N,T,以空格分隔。

第2行: N个正整数a1,a2,⋯,aN, 以空格分隔, ai表示细胞i在时刻0的状态。

ai=0表示细胞i处于死亡状态, ai=1表示细胞i处于生存状态。

输出格式

输出1行, N个数, 以空格分隔, 第i个数表示细胞i在时刻T的生存状态。（以 1 表示生存，以 0 表示死亡）

输入样例 #1

7 1
0 0 0 0 0 0 1

输出样例 #1

1 0 0 0 0 1 0

输入样例 #2

1 7
1

输出样例 #2

0

输入样例 #3

2 1
0 0

输出样例 #3

0 0

提示

数据范围：1≤N≤10000 1≤T≤1000

数据范围

输入数据满足题目正文及输入格式中给出的约束。