主题

主题

 
   

C. Subset Sums

You are given an array a1, a2, ..., an and m sets S1, S2, ..., Sm of indices of elements of this array. Let's denoteSk = {Sk, i} (1 ≤ i ≤ |Sk|). In other words, Sk, i is some element from set Sk.

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

  1. Find the sum of elements with indices from set Sk: . The query format is "? k".

  2. Add number x to all elements at indices from set Sk: aSk, i is replaced by aSk, i + x for all i (1 ≤ i ≤ |Sk|). 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 ≤ 105). The second line contains n integers a1, a2, ..., an (|ai| ≤ 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 (|Sk|), then follow |Sk| distinct integers Sk, 1, Sk, 2, ..., Sk, |Sk| (1 ≤ Sk, i ≤ n) — elements of set Sk.

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 Sk doesn't exceed 105.

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

Examples

input

5 3 5

5 -5 5 1 -4 

2 1 2

4 2 1 4 5

2 2 5

? 2

+ 3 4

? 1

+ 2 1

? 2

output

-3

4

9


题目大意:

给出一个长度为n的序列。给出m个集合,每个集合里面的元素是序列的下标。集合元素总大小不超过1e5。

现在需要支持两个操作:

  1. 给一个集合里面所有的下标在序列中对应的数字+w

  2. 查询一个集合里面所有的下标在序列中对应的数字之和


个人解法:

看到总大小的,便想到了大小分块。

大体思路不过是,对于元素个数小于或者等于sqrt(1e5)的,修改查询直接维护。对于元素个数大于sqrt(1e5)的,这样的集合不会超过sqrt(1e5)个,所以可以考虑如何计算贡献。

搬结论好了:

  1. 首先我们不管原来的数组。只记录影响。初始答案,直接扫描就可以了。

  2. 集合的修改都要做的:扫描每一个大集合,让大集合的答案标记+=w*交集

  3. 小集合的修改:现在小集合的元素的位置直接修改。

  4. 小集合的查询:扫描每一个元素的位置,加上这个和,扫描每一个大集合,自己加上交集*大集合的加法标记。

  5. 大集合的修改:自己加法标记+w。(注意自己的答案标记在都要做的部分以及加了)

  6. 大集合的查询,输出自己的答案标记。

可能我的做法不是那么优。不过是可行的……


代码如下:

http://codeforces.com/contest/348/submission/25936194

 
 
评论