Subset Sums

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Input: stdin

Output: stdout

Dạng bài

Ngôn ngữ cho phép

C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Bạn được cho một dãy số $A_{1}$ , $A_{2}$ , ..., $A_{n}$ và $m$ tập hợp $S_{1}$ , $S_{2}$ , ..., $S_{m}$ các chỉ số của mảng này. Gọi $S_{k} = {S_{k, i}}, 1 \leq i \leq | S_{k} |$ . Nói cách khác, $S_{k, i}$ là một phần tử bất kỳ từ tập hợp $S_{k}$ .

Trong bài này bạn sẽ phải trả lời $q$ truy vấn có 2 dạng sau:

$? k$ : Tính tổng $\sum_{i = 1}^{| S_{k} |} A_{S_{k, i}}$ , hay tổng các phần tử có vị trí thuộc tập $S_{k}$ của dãy $A$ .
$+ k x$ : Cộng $x$ vào các phần tử của dãy $A$ có chỉ số trong tập $S_{k}$ . Phần tử $A_{S_{k, i}}$ được thay bằng $A_{S_{k, i}} + x$ với mọi $i \in [1, | S_{k} |]$ .

Với mỗi truy vấn loại đầu tiên hãy in tổng đã tính.

Input

Dòng đầu tiên gồm 3 số $n, m, q$ ( $1 \leq n, m, q \leq 10^{5}$ ). Dòng thứ hai gồm $n$ phần tử $A_{1}, A_{2}, \dots, A_{n}$ ( $| A_{i} | \leq 10^{8}$ ), các phần tử của dãy $A$ .

$m$ dòng tiếp theo, dòng thứ $k$ gồm một số nguyên dương ở đầu cho biết số lượng phần tử của tập $S_{k}$ , theo sau bởi $| S_{k} |$ số nguyên dương phân biệt $S_{k, 1}, S_{k, 2}, \dots, S_{k, | S_{k} |}$ ( $1 \leq S_{k, i} \leq n$ ).

$q$ dòng tiếp theo, mỗi dòng có dạng $? k$ hoặc $+ k x$ . Với mọi truy vấn có $1 \leq k \leq m$ , $| x | \leq 10^{8}$ . Các truy vấn được cho theo thứ tự chúng cần được trả lời.

Đề đảm bảo tổng của kích thước mọi tập $S_{k}$ không quá $10^{5}$ .

Output

Sau mỗi truy vấn dạng đầu tiên hãy in tổng đã tính trên một dòng.

Sample Input 1

Copy

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

Sample Output 1

Copy

-3
4
9

Notes

Ở truy vấn đầu tiên, tập $S_{k}$ là $S_{2}$ có 4 phần tử ${2, 1, 4, 5}$ . Tổng của 4 phần tử có vị trí trong tập $S_{2}$ là $A_{2} + A_{1} + A_{4} + A_{5} = - 5 + 5 + 1 + (- 4) = - 3$ .

Bình luận

Hãy đọc nội quy trước khi bình luận.

4

HoangMC2009 đã bình luận 4:13:17 ch, 26/11/2024

https://codeforces.com/problemset/problem/348/C

-15

Loc2008 đã bình luận 8:24:24 sa, 27/12/2023

xin downvote

Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.