Райан хочет преподнести Рейхане подарок, чтобы завоевать её сердце. Однако Рейхане привередлива и примет только k-гармоничное множество перестановок.
Определим k-гармоничное множество перестановок как набор \(k\) попарно различных перестановок \(p_1, p_2, \ldots, p_k\) такого размера \(n\), что для каждой пары индексов \(i\) и \(j\) (где \(1 \leq i, j \leq n\)) выполняется следующее условие:
\(\) p_1[i] + p_2[i] + \ldots + p_k[i] = p_1[j] + p_2[j] + \ldots + p_k[j] \(\)
Ваша задача состоит в том, чтобы помочь Райану, либо предоставив допустимое k-гармоничное множество перестановок для заданных значений \(n\) и \(k\), либо определив, что такого набора не существует.
Мы называем последовательность длины \(n\) перестановкой, если она содержит каждое целое число от \(1\) до \(n\) ровно один раз.
Выходные данные
Для каждого набора входных данных, если k-гармоничное множество перестановок существует, выведите YES в первой строке. Затем выведите \(k\) строк, которые содержат различные перестановки целых чисел от \(1\) до \(n\).
Если такого набора не существует, в единственной строке выведите NO.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
Если существует несколько ответов, вы можете вывести любой из них.
Примечание
В 1 наборе входных данных мы имеем \(p_1 = [1, 2, 3]\), \(p_2 = [2, 3, 1]\), и \(p_3 = [3, 1, 2]\). Можно заметить, что \(p_1[1] + p_2[1] + p_3[1] = p_1[2] + p_2[2] + p_3[2] = p_1[3] + p_2[3] + p_3[3] = 6\).
Во 2 наборе входных данных у нас есть \(p_1 = [1, 2, 3, 4]\) и \(p_2 = [4, 3, 2, 1]\). Можно заметить, что \(p_1[1] + p_2[1] = p_1[2] + p_2[2] = p_1[3] + p_2[3] = p_1[4] + p_2[4] = 5\).
В 3 наборе входных данных, поскольку в \(p_1\) есть пять различных элементов, очевидно, что ответ — «No».
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4
3 3
4 2
5 1
3 2
|
YES
1 2 3
2 3 1
3 1 2
YES
1 2 3 4
4 3 2 1
NO
YES
1 2 3
3 2 1
|