ООО «Симптотика» собирается наладить выпуск обучающих игр для детей младшего дошкольного возраста. Одной из придуманных игр был набор кубиков, из которых можно было собирать различные фигуры. Кубики упаковывались в коробку размером N  ×  N  ×  1 кубиков.

Однако, многочисленные маркетинговые исследования показали, что детям неинтересно просто собирать различные фигурки. Гораздо интереснее складывать некоторый набор кубиков на дно коробки в столбики, а после этого переворачивать коробку на 90 градусов по часовой стрелке и смотреть, как именно меняется их расположение. Будем для простоты считать, что коробка поворачивается мгновенно, после чего все кубики падают на дно. На следующем рисунке продемонстрировано, как выглядит расположение кубиков в коробке до и после поворота на 90 градусов.

Разумеется, многим детям становится интересно, как будет выглядеть расположение кубиков после K поворотов в том же направлении. Требуется написать программу, которая вычисляет итоговое положение кубиков в коробке после K поворотов.

В Тридевятом царстве царь был любителем разных заморских традиций. Как прознает, что в другом царстве есть какой-то обычай, сразу думает, как бы его к тридевятым реалиям приспособить.

Вот неделю назад вернулось посольство из Тридесятого царства. И главный посол доложил царю: дескать, придумал Тридесятый царь следующую вещь. Чтобы как-то зарегулировать гуляния народные, повелел он указать определенные дни, и в эти дни устраивать широкие гуляния, а в остальные дни массовые сборища запретить. И с тех пор жизнь в Тридесятом царстве стала прекрасной: гулять так гулять, работать так работать, и все строго по цареву указу.

Понравилась мысль такая царю Тридевятого царства. Подумал он ввести и у себя такие порядки. Собрал царь советников своих, и говорит: подготовьте мне список дней, в которые гулять можно. Только не на год, а на \(N\) дней вперед — посмотрим, дескать, что получится; понравится — сделаем круглогодичным.

И вот вчера принесли советники царю список. Но вот незадача: каждый советник свой список приготовил, да еще и обоснование предложил, какой праздник в какой из этих дней надо отмечать. И у всех советников праздники важные, но у всех — разные! Царь думал-думал и решил: а возьмем их все — объединим предложения советников! Если какой-то день есть в списке хотя бы одного советника, то объявим этот день праздничным, и пускай народ гуляет! Глядишь, и не будет недовольных.

Только одна проблема осталась: некоторые дни оказались в списках сразу у нескольких советников. Но царь и тут нашел выход: перенесем некоторые праздники на более поздние дни, так, чтобы в каждый день получался только один праздник, и переносы были бы как можно короче.

Пусть, например, четыре советника сразу предложили сделать некоторый день (пускай день 5) праздничным. Тогда перенесем три из этих четырех праздников на дни 6, 7 и 8 — так, что праздничными будут дни с 5 по 8 включительно. А если оказывается, что, например, день 7 тоже предложен в качестве праздничного кем-нибудь из советников, то перенесем этот праздник еще дальше — на день 9.

Напишите программу, которая, зная предложения советников, определит, какие дни будут праздничными, а какие нет. Не забывайте, что праздники можно переносить только на более поздние дни; на более ранние переносить нельзя.