B. Зловещий Лабиринт
ограничение по времени на тест
1.5 секунд
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод
Axium Crisis - ak+q

В лабиринте есть $$$n$$$ клеток, и клетка $$$i$$$ ($$$1 \leq i \leq n$$$) находится на расстоянии $$$n - i$$$ километров от выхода. В частности, клетка $$$n$$$ является выходом. Также следует отметить, что каждая клетка соединена с выходом, но никак не доступна ни из какой-либо другой клетки.

В каждой клетке изначально находится ровно один человек, застрявший в ней. Вы хотите помочь всем приблизиться к выходу, установив телепорт в каждой ячейке $$$i$$$ ($$$1 \leq i \leq n$$$), который перемещает человека из этой ячейки в другую ячейку $$$a_i$$$.

Владелица лабиринта поймала вас на месте преступления. Удивлённая, она позволила вам продолжить, но при некоторых условиях:

  • Каждый должен использовать телепорт ровно $$$k$$$ раз.
  • Ни один телепорт не может вести в ту же ячейку, в которой он находится. Формально, $$$i \neq a_i$$$ для всех $$$1 \leq i \leq n$$$.

Вам необходимо найти конфигурацию телепортов, которая минимизирует сумму итоговых расстояний всех людей до выхода после использования каждым человеком ровно $$$k$$$ телепортов, соблюдая ограничения владелицы лабиринта.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая и единственная строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$2 \leq n \leq 2 \cdot 10^5$$$, $$$1 \leq k \leq 10^9$$$) — количество клеток в лабиринте и значение $$$k$$$.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2 \cdot 10^5$$$.

Выходные данные

Для каждого набора входных данных выведите $$$n$$$ целых чисел — клетки назначения телепортов $$$a_1, a_2, \ldots, a_n$$$ по порядку, удовлетворяющие заданным условиям ($$$1 \leq a_i \leq n$$$, $$$a_i \neq i$$$).

Пример
Входные данные
2
2 1
3 2
Выходные данные
2 1
2 3 2
Примечание

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

  • Перед телепортацией: $$$[1, 2]$$$.
  • Первая телепортация: $$$[2, 1]$$$.

Сумма расстояний равна $$$(2-2) + (2-1) = 1$$$, что является минимально возможным ответом.

Во втором наборе входных данных положение каждого человека следующее.

  • Перед телепортацией: $$$[1, 2, 3]$$$.
  • Первая телепортация: $$$[2, 3, 2]$$$.
  • Вторая телепортация: $$$[3, 2, 3]$$$.

Сумма расстояний равна $$$(3-3) + (3-2) + (3-3) = 1$$$, что является минимально возможным ответом.