{"raw_statement":[{"iden":"statement","content":"A Tree Generator is a balanced string of parentheses, like (()()). Generators are executed character by character from left to right, where '(' means add a new child to the selected node, and select the new node. While ')' means select the parent of the currently selected node.\n\nInitially, there is a tree with one node (1), and this node is selected.\n\nSelecting a new node will deselect any other node.\n\nNewly created nodes take the first unused positive integer as an ID (2, 3, ...).\n\nYou are given n generators and will generate a tree using k operations of the following format:\n\nFinally, you have to answer q queries on the generated tree, each query has the following format:\n\nThe first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 105), the number of generators, the number of operations, and the number of queries, respectively.\n\nEach of the following n lines contains a non-empty string of parentheses. It is guaranteed that the given string is balanced.\n\nTotal number of characters over all generators will not exceed 2 × 105.\n\nEach of the following k lines is in one of the following formats:\n\nEach of the following q lines contains two integers u and v, representing a query. It is guaranteed that u and v exist in the generated tree.\n\nFor each query in the given order, print the length of the shortest path between the given nodes.\n\n"},{"iden":"input","content":"The first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 105), the number of generators, the number of operations, and the number of queries, respectively.Each of the following n lines contains a non-empty string of parentheses. It is guaranteed that the given string is balanced.Total number of characters over all generators will not exceed 2 × 105.Each of the following k lines is in one of the following formats:  s x, select node x.  a i, activate generator i (1 ≤ i ≤ n). Each of the following q lines contains two integers u and v, representing a query. It is guaranteed that u and v exist in the generated tree."},{"iden":"output","content":"For each query in the given order, print the length of the shortest path between the given nodes."},{"iden":"examples","content":"Input3 3 2()(()())(())a 2s 3a 36 42 5Output42Input3 9 5(()())()()(())s 1s 1s 1a 1a 2s 4a 3a 3a 13 31 311 38 24 8Output02332"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k, q \\in \\mathbb{Z}^+ $ with $ 1 \\leq n, k, q \\leq 10^5 $.  \nLet $ G = \\{g_1, g_2, \\dots, g_n\\} $ be a set of $ n $ balanced parentheses strings, with total length $ \\sum_{i=1}^n |g_i| \\leq 2 \\times 10^5 $.  \nLet $ T $ be a tree initially consisting of a single root node with ID 1.  \nLet $ \\text{ops} = \\{o_1, o_2, \\dots, o_k\\} $ be a sequence of $ k $ operations, each selecting a generator $ g_i $ and executing it character-by-character to modify $ T $:  \n- `'('`: create a new child of the currently selected node, assign it the smallest unused positive integer ID, and select it.  \n- `')'`: select the parent of the currently selected node.  \n\n**Constraints**  \n1. All strings in $ G $ are balanced.  \n2. All node IDs in queries are valid (exist in final tree).  \n3. The tree remains connected after all operations.  \n\n**Objective**  \nAfter applying all $ k $ operations to build the final tree $ T $, for each of the $ q $ queries $ (u, v) $, compute the **shortest path length** (number of edges) between nodes $ u $ and $ v $ in $ T $.","simple_statement":"You are given n balanced parentheses strings (generators).  \nStart with a single node (ID 1).  \nProcess k operations: each operation picks one generator and runs it step by step to modify the tree.  \n'(' means: add a new child to current node, then select the new child.  \n')' means: move to the parent of current node.  \nNew nodes get IDs 2, 3, 4, ... in order of creation.  \n\nAfter k operations, you have a tree.  \nAnswer q queries: for each query (u, v), output the distance (number of edges) between nodes u and v.","has_page_source":false}