Можете представить, насколько сложно сделать торт? Нет, еще сложнее, чем вы представили.

А вот главный королевский кондитер точно представлял. Он готовил торты с детства, самых разных форм, цветов и вкусов. Когда его спросили, как у него получается делать такие сложные торты, он просто ответил: "Я верю, что Ника, богиня победы, очень любит торты - поэтому из кухни я всегда выхожу победителем".

Но однажды ему заказали особо необычный торт. Этот торт должны были повесить в комнате королевского первенца, поэтому он должен был быть выполнен в виде плоской картины из N·M кубиков попарно различных цветов, каждый кубик имел свой неповторимый цвет.

Кондитер разработал специальный аппарат для выдавливания кубиков нужной формы. Для упрощения конструкции материалы разных цветов вводились в аппарат заранее в неизменном после ввода порядке.

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

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

Это был провал! Не каждый ведь порядок цветов может привести к созданию картины по заданному эскизу. Но отступать некуда - весь королевский двор собрался посмотреть, как кондитер приготовит свое самое великое творение.

Времени до начала не так и много, поэтому он просит вас поскорее определить по заданной картине и порядку цветов в аппарате, выйдет ли он победителем и в этот раз или его спасет только божественное вмешательство?

На всякий случай приведем формальное описание алгоритма получения картины для незнакомых с тонкостями кондитерского искусства:

- Цвета в аппарате заданы в определенном порядке, цвет C_k обрабатывается только после обработки всех цветов C₁, C₂, ..., C_k - 1;

- Выбирается колонка j (1 ≤ j ≤ M), куда будет выдавлен кубик цвета C_k;

- Кубик занимает позицию в строке N, если до этого колонка была пустой, и в строке i, если позиции в данной колонке в строках N, N - 1, ..., i + 1 заняты обработанными ранее кубиками.