Когда котята-джедаи заканчивают свое обучение и готовы стать котами-джедаями, они проходят через еще одно интеллектуальное испытание. Его правила очень просты. Каждому будущему коту-джедаю дается шахматная доска N × M и один белый конь. Задача проста – с помощью коня, перемещая его по обычным правилам, котята-джедаи должны посетить каждую клетку доски ровно один раз, а после этого вернуться на стартовую клетку (это единственная клетка, которая посещается дважды). Котята-джедаи могут справиться с этой задачей, а вы?

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

Первая строка содержит целые числа N и M – размеры шахматной доски (6 ≤ N, M ≤ 1000). Шахматная доска – это M клеток в ширину и N клеток в высоту.

Если решения нет, выведите «No solution» без кавычек. Иначе выведите N строк с M целыми числами. Каждое целое число должно лежать в пределах от 1 до 8 и обозначать, в каком направлении будет выполняться следующий ход коня из клетки (i, j). Вот массив из 8 направлений.

Координаты левой верхней клетки – (1, 1).