您有 $$$n$$$ 堆栈 $$$r_1,r_2,\ldots,r_n$$$。每个堆栈包含一些从 $$$1$$$ 到 $$$n$$$ 的正整数。
定义以下函数:
您想知道 $$$\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)}$$$ 返回的值。
示例
输入 #1
3 3 1 2 2 3 3 1 2 3 1 2 1
输出 #1
1 2 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
输出 #2
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(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 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(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[],[1,2,1]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 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(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1,2],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3,1],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 1}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1,2],[3],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 1)}$$$。 $$$\texttt{stacks[1]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[1]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[3],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$不为空,设置$$$\texttt{new_pos := 3}$$$,并弹出$$$\texttt{stacks[2]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1,2]]$$$,然后调用$$$\texttt{get(堆栈, 3)}$$$。 $$$\texttt{stacks[3]}$$$不为空,设置$$$\texttt{new_pos := 2}$$$,并弹出$$$\texttt{stacks[3]}$$$的顶部元素,使得$$$\texttt{stacks}$$$变成$$$[[1],[],[1]]$$$,然后调用$$$\texttt{get(堆栈, 2)}$$$。 $$$\texttt{stacks[2]}$$$为空,返回$$$2$$$。