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

给你一个数组 $a_1, a_2, \dots, a_n$ 和 $m$ 个下标集合 $S_1, S_2, \dots, S_m$，这些集合中的元素均为该数组的下标。记 $S_k = \{S_{k,i}\}$（其中 $1 \le i \le |S_k|$）。换言之，$S_{k,i}$ 是集合 $S_k$ 中的某个元素。

本题要求你处理 $q$ 个查询，查询分为以下两类：

1. 求下标属于集合 $S_k$ 的所有数组元素之和：。查询格式为 ? k。
2. 将数值 $x$ 加到下标属于集合 $S_k$ 的所有数组元素上：对所有 $i$（$1 \le i \le |S_k|$），将 $a_{S_{k,i}}$ 替换为 $a_{S_{k,i}} + x$。查询格式为 + k x。

对每个第一类查询，请输出所求的和。

The first line contains integers n, m, q (1 ≤ n, m, q ≤ 105). The second line contains n integers _a_1, _a_2, ..., a__n (|a__i| ≤ 108) — 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| ≤ 108. 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 105.

第一行包含三个整数 $n$、$m$、$q$（$1 \leq n, m, q \leq 10^5$）。第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$（$|a_i| \leq 10^8$）——数组 $a$ 的元素。

接下来的 $m$ 行中，每行描述一个下标集合。第 $k$ 行首先包含一个正整数，表示该集合的元素个数（即 $|S_k|$），随后是 $|S_k|$ 个互不相同的整数 $S_{k,1}, S_{k,2}, \dots, S_{k,|S_k|}$（$1 \leq S_{k,i} \leq n$）——集合 $S_k$ 的元素。

接下来的 $q$ 行包含查询。每个查询形如 ? k 或 + k x，独占一行。对所有查询均满足：$1 \leq k \leq m$，$|x| \leq 10^8$。查询按给定顺序依次执行并回答。

保证所有集合 $S_k$ 的大小之和不超过 $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.

每次执行第一类查询后，在单独一行输出所需的和。

请注意，在 C++ 中读写 64 位整数时，请勿使用 %lld 说明符。推荐使用 cin、cout 流，或 %I64d 说明符。