You are given an array $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ and $*m*$ sets $*S*_{1}, *S*_{2}, ..., *S*_{*m*}$ of indices of elements of this array. Let's denote $*S*_{*k*} = {*S*_{*k*, *i*}} (1 ≤ *i* ≤ |*S*_{*k*}|)$. In other words, $*S*_{*k*, *i*}$ is some element from set $*S*_{*k*}$.

In this problem you have to answer $*q*$ queries of the two types:

1. Find the sum of elements with indices from set $*S*_{*k*}$: . The query format is "? k".
2. Add number $*x*$ to all elements at indices from set $*S*_{*k*}$: $*a*_{*S*_{*k*, *i*}}$ is replaced by $*a*_{*S*_{*k*, *i*}} + *x*$ for all $*i*$ $(1 ≤ *i* ≤ |*S*_{*k*}|)$. The query format is "+ k x".

After each first type query print the required sum.

Input

The first line contains integers $*n*, *m*, *q*$ $(1 ≤ *n*, *m*, *q* ≤ 10^{5})$. The second line contains $*n*$ integers $*a*_{1}, *a*_{2}, ..., *a*_{*n*}$ $(|*a*_{*i*}| ≤ 10^{8})$ — elements of array $*a*$.

Each of the following $*m*$ lines describes one set of indices. The $*k*$-th line first contains a positive integer, representing the number of elements in set ($|*S*_{*k*}|$), then follow $|*S*_{*k*}|$ distinct integers $*S*_{*k*, 1}, *S*_{*k*, 2}, ..., *S*_{*k*, |*S*_{*k*}|}$ $(1 ≤ *S*_{*k*, *i*} ≤ *n*)$ — elements of set $*S*_{*k*}$.

The next $*q*$ lines contain queries. Each query looks like either "? k" or "+ k x" and sits on a single line. For all queries the following limits are held: $1 ≤ *k* ≤ *m*$, $|*x*| ≤ 10^{8}$. The queries are given in order they need to be answered.

It is guaranteed that the sum of sizes of all sets $*S*_{*k*}$ doesn't exceed $10^{5}$.

Output

After each first type query print the required sum on a single line.

Please, do not write the %lld specifier to read or write 64-bit integers in С++. It is preferred to use the cin, cout streams or the %I64d specifier.