有一座城堡，里面有一个圆形的中央大厅。大厅的墙上挂着 $N$ 盏灯，编号为 $1$ 到 $N$。每盏灯的状态可以是亮或灭。在每一秒，如果第 $i+1$ 盏灯是亮的，那么第 $i$ 盏灯就会改变其状态；特别地，如果第 $1$ 盏灯是亮的，那么第 $N$ 盏灯就会改变其状态。
你的任务是，给定某一时刻所有灯的初始状态，求出 $M$ 秒后它们的状态。
输入格式
第一行包含两个整数 $N$ ($0 < N \le 10^6$) 和 $M$ ($0 \le M \le 10^9$)。
接下来的 $N$ 行，按第 $1$ 盏到第 $N$ 盏灯的顺序，每行包含一个灯的初始状态。其中 $0$ 表示灯是灭的，$1$ 表示灯是亮的。
输出格式
输出共 $N$ 行，按第 $1$ 盏到第 $N$ 盏灯的顺序，每行输出一个数字（$0$ 或 $1$），表示 $M$ 秒后该灯的状态。
样例
输入样例 1
3 1 0 0 1
输出样例 1
0 1 1