题目描述

众所周知，山羊和绵羊为了它们放牧的田地已经争斗多年。在经历了许多激烈的战斗后，山羊首领和绵羊首领决定会面，尝试为他们的问题找到一个和平的解决方案。经过多小时的讨论，他们同意为每块田地玩一个游戏，胜者将获得在该田地放牧的权利。

游戏的规则是，总共有 N 只动物（可能是山羊或绵羊）围成一个圈（山羊和绵羊的具体顺序由它们的首领协商决定）。在动物 i（1 ≤ i ≤ N-1）之后，游戏由动物 i+1 继续，而在动物 N 之后，游戏由动物 1 继续。开始游戏的动物可以从区间 [1, K] 中说出任意一个正整数，但这个数字不能大于 M。如果开始游戏的动物说了数字 j，那么下一个动物可以在区间 [j+1, j+K] 中说一个数字，但这个数字也不能大于 M。换句话说，每只动物可以说出比前一只动物所说的数字大至少 1、最多 K 的数字，但新数字不能大于 M。如果一只动物必须说出数字 M，它所在的队伍（山羊或绵羊）就会输掉。

如果山羊和绵羊都以最佳策略进行游戏，对于每个 i（1 ≤ i ≤ N），确定如果游戏由第 $i$ 只动物开始，谁将赢得这块田地。

输入格式

输入的第一行包含 N、M 和 K（1 ≤ N, M, K ≤ 5000），这些是任务中的数字。接下来的行包含 N 个数字，如果第 $i$ 只动物是绵羊，则为 0，如果是山羊，则为 1。

输出格式

输出 N 个以空格分隔的数字。对于每只动物 i（1 ≤ i ≤ N），如果绵羊将赢得田地，则输出 0；如果山羊将赢得田地，则输出 1，前提是游戏由第 $i$ 只动物开始。

输入输出样例 #1

输入 #1

2 9 2
0 1

输出 #1

0 1

输入输出样例 #2

输入 #2

6 499 5
1 0 0 1 1 0

输出 #2

0 1 1 1 1 0

输入输出样例 #3

输入 #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

说明/提示

在总分值为 60% 的测试用例中，将满足 1 ≤ N, M, K ≤ 500。

第一个测试用例的说明：

当绵羊先开始时，它可以这样进行游戏：

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

题面翻译由 ChatGPT-4o 提供。