Последовательность из \(n\) чисел называется перестановкой, если она содержит в себе все числа от \(1\) до \(n\) ровно по одному разу. Например, последовательности [\(3, 1, 4, 2\)], [\(1\)] и [\(2,1\)] являются перестановками, а [\(1,2,1\)], [\(0,1\)] и [\(1,3,4\)] — нет.
У Кристины была перестановка \(p\) из \(n\) элементов. Она записала ее на доску \(n\) раз таким образом, что:
- записывая перестановку в \(i\)-й (\(1 \le i \le n)\) раз она пропускала элемент \(p_i\)
Таким образом, всего она записала на доску
\(n\) последовательностей длины
\(n-1\) каждая.
Например, пусть у Кристины была перестановка \(p\) = \([4,2,1,3]\) длины \(4\). Тогда она сделала следующее:
- Записала на доску последовательность \([2, 1, 3]\), пропустив элемент \(p_1=4\) из исходной перестановки.
- Записала на доску последовательность \([4, 1, 3]\), пропустив элемент \(p_2=2\) из исходной перестановки.
- Записала на доску последовательность \([4, 2, 3]\), пропустив элемент \(p_3=1\) из исходной перестановки.
- Записала на доску последовательность \([4, 2, 1]\), пропустив элемент \(p_4=3\) из исходной перестановки.
Вам известны \(n\) последовательностей, которые были записаны на доску, но Вы не знаете, в каком порядке они были записаны. Восстановите по ним исходную перестановку.
Таким образом, если Вам известны последовательности \([4, 2, 1]\), \([4, 2, 3]\), \([2, 1, 3]\), \([4, 1, 3]\), то исходная перестановка будет равна \(p\) = \([4, 2, 1, 3]\).
Выходные данные
Для каждого набора входных данных выведите в отдельной строке перестановку \(p\) такую, что из нее могли быть получены заданные \(n\) последовательностей.
Гарантируется, что ответ существует и он единственный. Иными словами, для каждого набора входных данных обязательно найдется искомая перестановка.