A9264 | Subset Sums

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_{Sk,i}$ is replaced by $a_{Sk,i}+x$ for all $i$ $(1<=i<=|S_{k}|)$ . The query format is "+ k x".

After each first type query print the required sum.

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,|Sk}|$ $(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}$ .

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.