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.
Initially, there is a tree with one node (1), and this node is selected.
Selecting a new node will deselect any other node.
Newly created nodes take the first unused positive integer as an ID (2, 3, ...).
You are given n generators and will generate a tree using k operations of the following format:
Finally, you have to answer q queries on the generated tree, each query has the following format:
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:
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.
For each query in the given order, print the length of the shortest path between the given nodes.
## Input
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.
## Output
For each query in the given order, print the length of the shortest path between the given nodes.
[samples]
**Definitions**
Let $ n, k, q \in \mathbb{Z}^+ $ with $ 1 \leq n, k, q \leq 10^5 $.
Let $ 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 $.
Let $ T $ be a tree initially consisting of a single root node with ID 1.
Let $ \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 $:
- `'('`: create a new child of the currently selected node, assign it the smallest unused positive integer ID, and select it.
- `')'`: select the parent of the currently selected node.
**Constraints**
1. All strings in $ G $ are balanced.
2. All node IDs in queries are valid (exist in final tree).
3. The tree remains connected after all operations.
**Objective**
After 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 $.