I. Tree Generators
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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.
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.

Examples
Input
3 3 2
()
(()())
(())
a 2
s 3
a 3
6 4
2 5
Output
4
2
Input
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
Output
0
2
3
3
2