ENG  RUSTimus Online Judge
Online Judge
Задачи
Авторы
Соревнования
О системе
Часто задаваемые вопросы
Новости сайта
Форум
Ссылки
Архив задач
Отправить на проверку
Состояние проверки
Руководство
Регистрация
Исправить данные
Рейтинг авторов
Текущее соревнование
Расписание
Прошедшие соревнования
Правила

1310. Диагностика ACM

Ограничение времени: 0.5 секунды
Ограничение памяти: 64 МБ
Вы никогда не слышали об ACM? Вполне возможно. Ведь ACM — это новая разработка лаборатории вычислительных машин. И ACM (Abstract Computation Machine) — это не что иное, как новый прибор для проведения весьма сложных вычислений. Одна загвоздка: как всегда, в самом начале опытный образец не желает работать. Требуется диагностика, чтобы выяснить, что же именно неисправно.
Что же известно про конструкцию прибора? Он содержит L независимых регистров, каждый из которых способен хранить целое число в диапазоне от 1 до M. Не все регистры используются для вычислений — некоторое их число отвечает за контроль ошибок. Каким образом? Очень просто: значения в этих регистрах аппаратно выбираются так, чтобы сумма значений всех регистров прибора всегда делилась на некое изначально заданное число K. Проверено, что механизм поддержания делимости работает исправно, следовательно, сумма значений всех регистров действительно все время делится на число K.
Содержимое регистров ACM полностью определяет состояние устройства. Так что для точной диагностики достаточно лишь узнать содержимое всех регистров. Но вот незадача: разработчики, готовившие процедуру диагностики устройства, решили оптимизировать представление диагностической информации. И для этого вместо простого списка содержимого регистров решили выдавать единственное число — код состояния.
Код состояния должен полностью описывать состояние машины. Поэтому разработчики решили вычислять его следующим образом. Состояние машины — это произвольный вектор длины L (содержимое регистров), удовлетворяющий названным выше условиям. Так вот, в качестве кода состояния был выбран индекс вектора текущего состояния машины в отсортированном лексикографически по возрастанию списке всех возможных ее состояний (первое состояние в списке имеет индекс 0).
Конечно же, такой код состояния действительно однозначно описывает состояние прибора, но теперь перед разработчиками встала проблема. Требуется по коду состояния восстановить содержимое всех регистров прибора. Вот для этого и требуется ваша помощь. Недаром теперь аббревиатура ACM — не пустой звук для вас.

Исходные данные

В первой строке входа находятся три числа L, M и K (1 ≤ L ≤ 100; 2 ≤ M ≤ 50; 1 ≤ K ≤ 50). Во второй строке находится целое число N — код состояния, возвращенный прибором.

Результат

На выход следует выдать состояние регистров машины, соответствующее коду N. То есть L целых чисел, разделенных пробелами.

Пример

исходные данныерезультат
3 10 4
213
9 6 1
Автор задачи: Идея — Александр Клепинин, подготовка — Александр Клепинин, Павел Егоров
Источник задачи: VIII Командный студенческий чемпионат Урала по программированию. Екатеринбург, 11-16 марта 2004 г.