D. Игра со стеками
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть $$$n$$$ стеков $$$r_1,r_2,\ldots,r_n$$$. Каждый стек содержит некоторое количество целых положительных чисел в диапазоне от $$$1$$$ до $$$n$$$.

Определим следующие функции:

function init(pos):
    stacks := массив, содержащий n стеков r[1], r[2], ..., r[n].
    return get(stacks, pos)

function get(stacks, pos):
    if stacks[pos] пуст:
        return pos
    else:
        new_pos := верхний элемент stacks[pos]
        удалить верхний элемент stacks[pos]
        return get(stacks, new_pos)

Вы хотите узнать значения, возвращаемые $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$.

Заметим, что во время этих вызовов стеки $$$r_1,r_2,\ldots,r_n$$$ не изменяются, поэтому вызовы $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$ являются независимыми.

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

Первая строка ввода содержит одно целое число $$$n$$$ ($$$1\le n\le 10^5$$$) — длина массива $$$r$$$.

Каждая из последующих $$$n$$$ строк содержит несколько целых чисел. Первое целое число $$$k_i$$$ ($$$0\le k_i\le 10^5$$$) представляет собой количество элементов в $$$i$$$-м стеке, а следующие $$$k_i$$$ положительных целых чисел $$$c_{i,1},c_{i,2},\ldots,c_{i,k_i}$$$ ($$$1\le c_{i,j}\le n$$$) представляют элементы в $$$i$$$-м стеке. $$$c_{i,1}$$$ - нижний элемент.

В каждом тесте $$$\sum k_i\le 10^6$$$.

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

Необходимо вывести $$$n$$$ значений, $$$i$$$-м из которых является значение, возвращаемое $$$\texttt{init(i)}$$$.

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

В первом примере:

  • При вызове $$$\texttt{init(1)}$$$ присваивается $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3,1,2],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3,1],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[3],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 3}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[3]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[],[],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ пуст, возвращается $$$1$$$.
  • При вызове $$$\texttt{init(2)}$$$ присваивается $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2,2],[3,1],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2,2],[3],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 3}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[],[1,2,1]]$$$, а затем вызывается $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[3]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ пуст, возвращается $$$2$$$.
  • При вызове $$$\texttt{init(3)}$$$ присваивается $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, а затем вызывается $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[3]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2,2],[3,1,2],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3,1,2],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3,1],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 1}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1,2],[3],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 1)}$$$.
    • $$$\texttt{stacks[1]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[1]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[3],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ не пуст, присваивается $$$\texttt{new_pos := 3}$$$ и удаляется верхний элемент $$$\texttt{stacks[2]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[],[1,2]]$$$, а затем вызывается $$$\texttt{get(stacks, 3)}$$$.
    • $$$\texttt{stacks[3]}$$$ не пуст, присваивается $$$\texttt{new_pos := 2}$$$ и удаляется верхний элемент $$$\texttt{stacks[3]}$$$, в результате чего $$$\texttt{stacks}$$$ станет $$$[[1],[],[1]]$$$, а затем вызывается $$$\texttt{get(stacks, 2)}$$$.
    • $$$\texttt{stacks[2]}$$$ пуст, возвращается $$$2$$$.