Description:
You have $$$n$$$ stacks $$$r_1,r_2,\ldots,r_n$$$. Each stack contains some positive integers ranging from $$$1$$$ to $$$n$$$.
Define the following functions:
You want to know the values returned by $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$.
Note that, during these calls, the stacks $$$r_1,r_2,\ldots,r_n$$$ don't change, so the calls $$$\texttt{init(1)}, \texttt{init(2)}, \ldots, \texttt{init(n)}$$$ are independent.
Input Format:
The first line of the input contains one integer $$$n$$$ ($$$1\le n\le 10^5$$$) — the length of the array $$$r$$$.
Each of the following $$$n$$$ lines contains several integers. The first integer $$$k_i$$$ ($$$0\le k_i\le 10^5$$$) represents the number of elements in the $$$i$$$-th stack, and the following $$$k_i$$$ positive integers $$$c_{i,1},c_{i,2},\ldots,c_{i,k_i}$$$ ($$$1\le c_{i,j}\le n$$$) represent the elements in the $$$i$$$-th stack. $$$c_{i,1}$$$ is the bottom element.
In each test, $$$\sum k_i\le 10^6$$$.
Output Format:
You need to output $$$n$$$ values, the $$$i$$$-th of which is the value returned by $$$\texttt{init(i)}$$$.
Note:
In the first example:
- When you call $$$\texttt{init(1)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1,2],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$. $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is empty, return $$$1$$$.
- When you call $$$\texttt{init(2)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3,1],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[],[1,2,1]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$. $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is empty, return $$$2$$$.
- When you call $$$\texttt{init(3)}$$$, set $$$\texttt{stacks := [[1,2,2],[3,1,2],[1,2,1]]}$$$, and then call $$$\texttt{get(stacks, 3)}$$$. $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2,2],[3,1,2],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1,2],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3,1],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 1}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1,2],[3],[1,2]]$$$, and then call $$$\texttt{get(stacks, 1)}$$$. $$$\texttt{stacks[1]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[1]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[3],[1,2]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is not empty, set $$$\texttt{new_pos := 3}$$$, and pop the top element of $$$\texttt{stacks[2]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1,2]]$$$, and then call $$$\texttt{get(stacks, 3)}$$$. $$$\texttt{stacks[3]}$$$ is not empty, set $$$\texttt{new_pos := 2}$$$, and pop the top element of $$$\texttt{stacks[3]}$$$, which makes $$$\texttt{stacks}$$$ become $$$[[1],[],[1]]$$$, and then call $$$\texttt{get(stacks, 2)}$$$. $$$\texttt{stacks[2]}$$$ is empty, return $$$2$$$.