题目描述

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

游戏的规则是，总共有 $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。

2 9 2
0 1

0 1

6 499 5
1 0 0 1 1 0

0 1 1 1 1 0

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

1 1 1 1 1 1 1 1 1 1

提示

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

第一个样例的说明：

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

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

题面翻译由 ChatGPT-4o 提供，123asdf123 修缮。