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: Find the sum of elements with indices from set S k : . The query format is "? k". 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.
输入描述:
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.
输出描述:
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.
示例1
输入
5 3 5<br />5 -5 5 1 -4<br />2 1 2<br />4 2 1 4 5<br />2 2 5<br />? 2<br />+ 3 4<br />? 1<br />+ 2 1<br />? 2<br />
加载中...