Tree

Limits: 2 sec., 512 MiB

This statement was translated automatically from Ukrainian.

Having successfully passed the External Independent Evaluation in geography, Zenyk decided to spend a pleasant evening and solve the following interesting problem.

You are given a connected graph with \(n\) vertices connected by \(n-1\) edges. The vertices of the graph are numbered with integers from 1 to \(n\) inclusive.

Initially, the number zero is written in each vertex. In addition, you are given a set of \(m\) simple paths in this graph, where each path is given as a sequence of vertices. The given paths are numbered with integers from 1 to \(m\) inclusive.

You need to process \(k\) queries of the following two types.

• + \(p_i\) \(a_i\) — add \(a_i\) to the numbers written on all vertices on the \(p_i\)-th path.

• ? \(p_i\) — find the sum of the numbers written on all vertices of the \(p_i\)-th path.

Help Zenyk solve this problem.

Input

The first line contains three integers \(n\), \(m\), \(k\) — the number of vertices, the number of paths, and the number of queries, respectively.

The next \(n-1\) lines describe the edges of the tree \(u_i\), \(v_i\).

The next \(m\) lines describe the paths, one per line. The first number \(c_i\) denotes the number of vertices on the path, and the next \(c_i\) numbers describe the vertices of the path in traversal order.

The last \(k\) lines describe the queries according to the format described in the statement.

Output

For each query of the second type, output an integer — the answer to it.

Constraints

\(1 \le n, m, k \le 2 \cdot 10^5\),

\(1 \le u_i, v_i, c_i \le n\),

\(0 \le a_i \le 10^9\),

The total size of all given paths does not exceed \(2 \cdot 10^5\).

Samples

Input (stdin) сopy	Output (stdout) сopy
7 4 7 1 2 1 3 3 4 3 5 3 6 4 7 3 1 3 5 3 6 3 4 4 7 4 3 5 2 3 1 ? 4 + 3 7 + 4 4 ? 4 ? 1 + 2 1 ? 3	0 15 22 34