У Поликарпа есть компьютер с n процессорами. Также в его компьютере есть n ячеек памяти. Будем считать, что процессоры пронумерованы целыми числами от 1 до n и что ячейки памяти последовательно пронумерованы целыми числами от 1 до n.
Поликарпу нужно разработать модель параллельной программы, которая для каждой ячейки памяти с номером i записывает в эту ячейку значение n - i. Другими словами, для каждой ячейки требуется найти расстояние до ячейки n.
Обозначим, записанное в i-той ячейке значение как ai. Изначально, ai = 1 (1 ≤ i < n) и an = 0. Будем считать, что в ячейку памяти номер i может записывать значения только лишь процессор i. Читать значение ячейки может любой процессор (несколько разных процессоров могут читать значение из ячейки одновременно).
Исполнение параллельной программы происходит в несколько шагов. На каждом шаге происходит выполнение параллельной версии операции инкремента. Выполнение параллельной операции инкремента происходит следующим образом:
- Каждый процессор независимо от других выбирает некоторую ячейку памяти. Пусть процессор i выбрал ячейку с номером ci (1 ≤ ci ≤ n).
- Все процессоры одновременно выполняют операцию, ai = ai + aci.
Помогите Поликарпу разработать модель параллельной программы, которая выполняется ровно в k шагов. Вычислите, какие операции нужно выполнить, чтобы после ровно k шагов для всех i значение ai было равно n - i.
Выходные данные
Выведите ровно n·k целых чисел в k строках. В первой строке выведите номера c1, c2, ..., cn (1 ≤ ci ≤ n) для первой операции инкремента. Во второй — выведите номера для второй операции инкремента. В k-ой — выведите номера для k-ой операции инкремента.
В результате выведенных операций для любого i значение ai должно быть равно n - i.