{"raw_statement":[{"iden":"statement","content":"A long time ago...\n\nIn a galaxy far far away...\n\nWhere nobody cared about how chocolates should be shared...\n\n#cf_span(class=[tex-font-style-sc], body=[There was Og.])\n\nOne day, Og was very bored. He has not done anything interesting after discovering fire a few months back. And so he decided to write a program in [C+]+. (It is the predecessor of the languages C, C++, C++++, C++C+CC+++C, and so on.)\n\n[C+]+ is very similar to C++, but it has a Python-like syntax and has infinite memory. In particular, _int_s are arbitrary precision. Arrays are zero-indexed.\n\nHere is Og's program.\n\nNodes are numbered 1 to $n$. Ug, Og's brother, edited the program while Og was not looking. He inserted lines in Og's code. In particular, an _else_ clause is inserted, so the code now looks like:\n\nOg was expecting his code to halt quickly. However, after Ug's shenanigans, it continued printing numbers. Og waited patiently. After $10^(10^(10^(100)))$ years, Og is still waiting. It has printed at least $10^(100)$ numbers at this point. Og got bored again. To pass the time, he decided to look at the $i_1$th element, $i_2$th element, ..., $i_k$th element of the list. What are the $k$ numbers that Og will see?\n\nThe first line of input contains two space-separated integers $n$ and $k$. The nodes are indexed from $1$ to $n$. The tree is rooted at node $1$. \n\nThe $i$th of the next $n$ lines describes the children of node $i$. Specifically, it contains $c_i + 1$ space-separated integers $c_i, x_1, x_2, \\\\dots, x_{c_i}$, where $c_i$ is the number of children of node $i$, and $(x_1, x_2, \\\\dots, x_{c_i})$ are the children of node $i$. \n\nThe $j$th of the next $k$ lines contains $i_k$, as described in the problem statement. \n\nOutput $k$ lines. The $j$th line must contain an integer denoting the $i_j$th element of the list. \n\n$1 <= n <= 50$\n\n$1 <= k <= 143$\n\n$0 <= c_i < n$\n\n$1 <= x_i <= n$\n\nIt is guaranteed that the input describes a tree rooted at node $1$. \n\n*Subtask 1* (27 points): $1 <= i_j <= 10^5$\n\n*Subtask 2* (25 points): $1 <= i_j <= 10^9$\n\n*Subtask 3* (18 points): $1 <= i_j <= 10^(15)$\n\n*Subtask 4* (25 points): $1 <= i_j <= 10^(18)$\n\n*Subtask 5* (5 points): $1 <= i_j <= 10^(100)$\n\n"},{"iden":"input","content":"The first line of input contains two space-separated integers $n$ and $k$. The nodes are indexed from $1$ to $n$. The tree is rooted at node $1$. The $i$th of the next $n$ lines describes the children of node $i$. Specifically, it contains $c_i + 1$ space-separated integers $c_i, x_1, x_2, \\\\dots, x_{c_i}$, where $c_i$ is the number of children of node $i$, and $(x_1, x_2, \\\\dots, x_{c_i})$ are the children of node $i$. The $j$th of the next $k$ lines contains $i_k$, as described in the problem statement. "},{"iden":"output","content":"Output $k$ lines. The $j$th line must contain an integer denoting the $i_j$th element of the list. "},{"iden":"scoring","content":"$1 <= n <= 50$$1 <= k <= 143$$0 <= c_i < n$$1 <= x_i <= n$It is guaranteed that the input describes a tree rooted at node $1$. *Subtask 1* (27 points): $1 <= i_j <= 10^5$*Subtask 2* (25 points): $1 <= i_j <= 10^9$*Subtask 3* (18 points): $1 <= i_j <= 10^(15)$*Subtask 4* (25 points): $1 <= i_j <= 10^(18)$*Subtask 5* (5 points): $1 <= i_j <= 10^(100)$"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of nodes in a rooted tree, with nodes labeled $ 1 $ to $ n $, rooted at node $ 1 $.  \nFor each node $ i \\in \\{1, \\dots, n\\} $, let $ c_i \\in \\mathbb{Z}_{\\geq 0} $ denote its number of children, and let $ \\text{children}(i) = (x_{i,1}, x_{i,2}, \\dots, x_{i,c_i}) $ be the ordered list of its children.  \n\nLet $ L = (v_1, v_2, v_3, \\dots) $ be the infinite sequence generated by a depth-first traversal of the tree, where at each node, the algorithm:  \n- Prints the node label,  \n- Then recursively visits its children in the given order.  \n\nLet $ k \\in \\mathbb{Z}^+ $ be the number of queries.  \nLet $ I = (i_1, i_2, \\dots, i_k) $ be a sequence of indices, where each $ i_j \\in \\mathbb{Z}^+ $, and $ 1 \\leq i_j \\leq 10^{100} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 50 $  \n2. $ 1 \\leq k \\leq 143 $  \n3. $ 0 \\leq c_i < n $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. For all $ i \\in \\{1, \\dots, n\\} $, $ x_{i,\\ell} \\in \\{1, \\dots, n\\} $ for all $ \\ell \\in \\{1, \\dots, c_i\\} $  \n5. The input describes a tree rooted at node $ 1 $  \n\n**Objective**  \nFor each query index $ i_j \\in I $, compute $ L[i_j] $, the $ i_j $-th element of the infinite sequence $ L $ generated by the DFS traversal described.","simple_statement":"Og wrote a program that traverses a tree rooted at node 1 in a specific order and prints node values. Ug modified the code, causing it to print infinitely. Given queries for the i-th printed number, find what number is printed at each position.","has_page_source":false}