Числа \(1, \, 2, \, \dots, \, n \cdot k\) окрашены в \(n\) цветов. Эти цвета обозначены \(1, \, 2, \, \dots, \, n\). Для каждого \(1 \le i \le n\) существует ровно \(k\) чисел, окрашенных в цвет \(i\).
Пусть \([a, \, b]\) обозначает отрезок целых чисел от \(a\) до \(b\) включительно, то есть множество \(\{a, \, a + 1, \, \dots, \, b\}\). Вы должны выбрать \(n\) отрезков \([a_1, \, b_1], \, [a_2, \, b_2], \, \dots, [a_n, \, b_n]\) таких, что:
- для каждого \(1 \le i \le n\) имеет место \(1 \le a_i < b_i \le n \cdot k\);
- для каждого \(1 \le i \le n\), числа \(a_i\) и \(b_i\) окрашены цветом \(i\);
- каждое число \(1 \le x \le n \cdot k\) принадлежит не более чем \(\left\lceil \frac{n}{k - 1} \right\rceil\) отрезкам.
Можно показать, что такое семейство отрезков всегда существует при заданных ограничениях.
Выходные данные
Выведите \(n\) строк. В \(i\)-й строке должны содержаться два целых числа \(a_i\) и \(b_i\).
Если существует несколько допустимых вариантов выбрать отрезки, выведите любой.
Примечание
В первой выборке каждое число может содержаться не более чем в \(\left\lceil \frac{4}{3 - 1} \right\rceil = 2\) отрезках. Вывод описывается следующим рисунком:
Во втором примере единственным отрезком, который можно выбрать, является \([1, \, 2]\), и каждое число действительно содержится не более чем в \(\left\lceil \frac{1}{2 - 1} \right\rceil = 1\) отрезках.
В третьем примере, каждое число может содержаться не более чем в \(\left\lceil \frac{3}{3 - 1} \right\rceil = 2\) отрезках. Вывод описывается следующим рисунком:
