Subset Sums

View as PDF

Submit solution


Points: 1.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Input: stdin
Output: stdout

Problem type
Allowed languages
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 ~\displaystyle \sum^{|S_k|}_{i = 1}{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, \cdots, 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}, \cdots, 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

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

-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~.


Comments

Please read the guidelines before commenting.



  • 4
    HoangMC2009  commented on Nov. 26, 2024, 4:13 p.m.

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


  • -15
    Loc2008  commented on Dec. 27, 2023, 8:24 a.m.

    This comment is hidden due to too much negative feedback. Show it anyway.