Задача: Рассадка зверей
Сегодня Колобок созвал всех волков и лис к себе в гости на чаепитие. Чаепитие пройдет за круглым столом, за которым всего n мест. Колобок хочет рассадить зверей по-особенному — так, чтобы волки не сидели только с волками, а лисы только с лисами. Поэтому для каждого места он записал одно целое число — сколько лис должно сидеть на расстоянии не более d от этого места, включая это место.
Два места находятся на расстоянии не более d, если между ними встречаются не более d−1 места при движении по или против часовой стрелки от одного к другому. Таким образом, для заданного места всего существует 2d + 1 место, находящееся на расстоянии не более d от него.
Теперь он хочет придумать какую-нибудь рассадку зверей, удовлетворяющую этим ограничениям.
Входные данные
В первой строке находятся два натуральных числа n, d (3 ≤ n ≤ 105 , 3 ≤ 2d+1 ≤ n) — количество мест за круглым столом и расстояние d. В следующей строке находятся n неотрицательных целых чисел ai (0 ≤ ai ≤ 2d+1) — количество лис на расстоянии не более d от этого места, включая это место. Информация о местах перечислена в порядке их следования по кругу.
Выходные данные
Если решения не существует, выведите «NO», иначе в первой строке выведите «YES», а в следу- ющей n чисел: 1 в том случае, если на этом месте сидит лиса, и 0, если на этом месте сидит волк. Если ответов несколько, разрешается вывести любой.
| Ввод |
Вывод |
5
1 2 2 1 2 2 |
YES
1 0 1 0 1 |
9
2 3 4 4 3 3 2 2 2 2 |
YES
1 0 1 1 1 0 0 0 1 |
6
1 3 3 3 3 3 1 |
NO |
Ваш ответ: