众所周知，山羊和绵羊多年来一直在为它们放牧的草地进行争斗。在经历了多次激烈的战斗后，山羊领袖和绵羊领袖决定会面，试图为他们的问题找到一个和平的解决方案。经过数小时之久的讨论，他们同意为每块草地进行一场游戏，获胜者将获得在该草地放牧的权利。

游戏规则如下：总共 $N$ 只动物（可以是山羊或绵羊）排成一个圆圈（山羊和绵羊的具体排列顺序由它们的领袖协商决定）。在动物 $i$（$1 \le i \le N-1$）之后，游戏由动物 $i+1$ 继续；在动物 $N$ 之后，游戏由动物 $1$ 继续。开始游戏的动物可以说区间 $[1, K]$ 中的任意正整数，但该数字不能大于 $M$。如果开始游戏的动物说了数字 $j$，那么下一只动物可以说区间 $[j+1, j+K]$ 中的一个数字，但该数字不能大于 $M$。换句话说，每只动物可以说一个比前一只动物说的数字至少大 $1$ 且至多大 $K$ 的数字，但新数字不能大于 $M$。如果某只动物必须说数字 $M$，则它所在的队伍（山羊或绵羊）输掉游戏。

如果山羊和绵羊都采取最优策略，对于每个 $i$（$1 \le i \le N$），确定如果游戏由第 $i$ 只动物开始，谁将赢得这块草地。

输入格式

第一行输入包含三个整数 $N, M, K$（$1 \le N, M, K \le 5000$），表示题目中的参数。

第二行包含 $N$ 个整数，如果第 $i$ 只动物是绵羊则为 $0$，如果是山羊则为 $1$。

输出格式

输出 $N$ 个空格分隔的整数。对于每个动物 $i$（$1 \le i \le N$），如果由第 $i$ 只动物开始游戏时绵羊获胜，则输出 $0$；如果山羊获胜，则输出 $1$。

子任务

在占总分 $60\%$ 的测试数据中，满足 $1 \le N, M, K \le 500$。

样例

输入格式 1

2 9 2
0 1

输出格式 1

0 1

输入格式 2

6 499 5
1 0 0 1 1 0

输出格式 2

0 1 1 1 1 0

输入格式 3

10 100 10
0 0 0 1 1 1 1 0 1 1

输出格式 3

1 1 1 1 1 1 1 1 1 1

说明

对于第一个样例的解释：

当绵羊先手时，它可以这样玩：

绵羊首先说数字 2，之后山羊可以说 3 或 4。在这两种情况下，绵羊都可以说 5，之后山羊可以说 6 或 7。在这两种情况下，绵羊都可以说 8，之后山羊别无选择只能说 9，从而输掉游戏和草地。