Следующая перестановка

Для каждой последовательности выведите следующую перестановку в лексикографическом порядке. Если последовательность уже последняя (не возрастает), выведите слово last и через пробел первую перестановку (отсортированную по возрастанию).

Ввод: q (1 ≤ q ≤ 2000), затем q строк: k (1 ≤ k ≤ 10) и k чисел от 1 до 9 (могут повторяться).

Вывод: q строк.

Пример 1

Ввод:

3
3 1 2 3
3 3 2 1
4 1 3 2 2

Вывод:

1 3 2
last 1 2 3
2 1 2 3

Пример 2

Ввод:

2
1 7
2 5 5

Вывод:

last 7
last 5 5