405114: GYM101798 I Tree Generators

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:

• Select node x. It is guaranteed that node x exists in the tree before this operation.
• Activate generator number i (1 ≤ i ≤ n) at the selected node. Note that the selected node will remain the same after the process (as the given generators are balanced).

Finally, you have to answer q queries on the generated tree, each query has the following format:

• Find the length of the shortest path between node u and v.

The first line of input contains three integers n, k and q (1 ≤ n, k, q ≤ 10⁵), 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 × 10⁵.

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.

For each query in the given order, print the length of the shortest path between the given nodes.

3 3 2
()
(()())
(())
a 2
s 3
a 3
6 4
2 5

4
2

3 9 5
(()())
()()
(())
s 1
s 1
s 1
a 1
a 2
s 4
a 3
a 3
a 1
3 3
1 3
11 3
8 2
4 8

0
2
3
3
2