У Индианы Джонса есть ключ от двери, ведущей к тайным богатствам инков. Ключ имеет форму правильного треугольника, который, в свою очередь, разбит на n² маленьких правильных треугольников, в каждом из которых написана одна десятичная цифра. Пример ключа приведен ниже на рисунке.

Джонс вставил треугольник в соответствующее треугольное отверстие в двери, и... она не открылась. Возможно, он вставил ключ неправильно, ведь его можно вставить тремя способами. Из-за того, что у Джонса осталась лишь одна попытка для того, чтоб открыть двери (в случае неудачи его убьют уже настигающие его кровожадные инки), он хочет знать как будет выглядеть ключ при его вставке в дверь другими двумя способами. После этого он сделает правильный выбор. Вас, как одного из двух своих помощников, он попросил показать ему только один из двух возможных вариантов. Внешний вид ключа, приведенного выше, при повороте против и по часовой стрелке изображен на рисунке ниже.

Поскольку вы не хотите смерти Индианы и хотите получить свою долю сокровищ, вам придется помочь ему!

В воинской части города Шатров продолжаются занятия по строевой подготовке. Молодой прапорщик Андрей Юрьевич уже приноровился проводить эти занятия, но тут его начальник Павел Андреевич стал давать ему новые, более сложные задания.

Как известно, обычно все солдаты выстраиваются в шеренгу по росту, начиная с самого низкого. Но Павлу Андреевичу это показалось слишком скучным и он потребовал от Андрея Юрьевича выстроить солдат в другом порядке. Случайный порядок ему показался слишком хаотичным, поэтому он потребовал построения, в котором будет ровно k инверсий. Инверсией называется такая пара солдат, что более высокий из них стоит в шеренге раньше более низкого.

К счастью для Андрея Юрьевича, все солдаты разного роста и для каждого он знает, какой он по росту среди всех солдат. Исходя из этого, каждому солдату Андрей Юрьевич присвоил номер: первый номер получил самый низкий, а последний — самый высокий солдат.

Например, в построении (3, 1, 2) есть две инверсии — пары (3, 1) и (3, 2), в которых более высокий солдат стоит раньше более низкого.

Андрей Юрьевич поручил Вам помочь ему в построении солдат в требуемом порядке, и для этого вы должны написать программу, находящую расстановку n солдат в порядке, в котором есть ровно k инверсий.

На планете Руук существует Большая Корпорация Маленьких Фей. Одним из видов деятельности, которым испокон веков занимаются ее сотрудницы, является посадка грядок с волшебными грибами. Каждый день, начиная с самого первого дня существования этой корпорации, феи создают одну новую грядку грибов. После этого с новой грядки два дня можно собирать споры, которыми размножаются эти грибы, а потом грядка будет поставлять уже только сам продукт — грибы.

Таким образом, если обозначить количество грибов, посаженных на грядке, созданной в день номер i, как c_i, то оно будет считаться по формуле c_i = c_i - 1 + c_i - 2. Так, в первый и второй дни было посажено по одному грибу, в третий — два, в четвертый — три, в пятый — пять и так далее.

Волшебные грибы являются самыми ценными сувенирами, которые путешественник может привезти с планеты Руук. Поэтому первым, что делает любой приезжий, становится поиск грядки с волшебными грибами. Однако, в последнее время все чаще стали появляться сообщения о поддельных волшебных грибах. Тщательное расследование показало, что это является следствием действий Маленькой Корпорации Больших Фей, которая сажает грядки с грибами, внешне не отличимыми, но далеко не такими ценными, как волшебные. Причем, создавая очередную грядку, эти феи сажают туда такое количество грибов, какое их соперницы никогда не сажали и не смогут посадить.

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