CF1889D Game of Stacks

你有 $n$ 个栈 $r_1,r_2,\cdots,r_n$。每个栈中有一些 $1$ 到 $n$ 的正整数。 定义如下函数： ``` function init(pos): stacks := an array that contains n stacks r[1], r[2], ..., r[n] return get(stacks, pos) function get(stacks, pos): if stacks[pos] is empty: return pos else: new_pos := the top element of stacks[pos] pop the top element of stacks[pos] return get(stacks, new_pos) ``` 你想要知道 $\texttt{init(1)},\texttt{init(2)},\cdots,\texttt{init(n)}$ 的返回值。 注意在调用过程中，栈 $r_1,r_2,\cdots,r_n$ 没有变化，所以对 $\texttt{init(1)},\texttt{init(2)},\cdots,\texttt{init(n)}$ 的调用是独立的。

第一行一个整数 $n(1\le n\le 10^5)$，为序列 $r$ 的长度。 接下来 $n$ 行，第 $i$ 行第一个整数为 $k_i(0\le k_i\le 10^5)$，为第 $i$ 个栈里的数字个数。接下来 $k_i$ 个整数 $c_{i,1},c_{i,2},\cdots,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)}$ 的返回值。

**样例解释** 在样例 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$。