| Codeforces Round 202 (Div. 1) |
|---|
| Закончено |
Дан массив a1, a2, ..., an и m множеств S1, S2, ..., Sm индексов элементов этого массива. Введем обозначение, Sk = {Sk, i} (1 ≤ i ≤ |Sk|), другими словами Sk, i — это некоторый элемент множества Sk.
В задаче нужно ответить на q запросов. Каждый запрос имеет один из следующих типов:
- Найти сумму элементов с индексами из множества Sk:
. Формат запроса — «? k». - Добавить число x ко всем элементам с индексами из множества Sk: aSk, i заменяется на aSk, i + x для всех i (1 ≤ i ≤ |Sk|). Формат запроса — «+ k x».
После каждого запроса первого типа, выведите искомую сумму.
В первой строке записаны целые числа n, m, q (1 ≤ n, m, q ≤ 105). В следующей строке записаны n целых чисел a1, a2, ..., an (|ai| ≤ 108) — элементы массива a.
Каждая из следующих m строк описывает одно множество индексов. В k-ой строке сначала записано целое положительное число, обозначающее количество элементов в множестве (|Sk|), а затем даны |Sk| различных целых чисел Sk, 1, Sk, 2, ..., Sk, |Sk| (1 ≤ Sk, i ≤ n) — элементы множества Sk.
В следующих q строках заданы запросы. Каждый запрос имеет вид «? k» или «+ k x» и находится на отдельной строчке. Для всех запросов выполняются ограничения: 1 ≤ k ≤ m, |x| ≤ 108. Запросы заданы в том порядке, в котором их нужно выполнять.
Гарантируется, что сумма размеров всех множеств Sk не превосходит 105.
После каждого запроса первого типа, выведите искомую сумму в отдельной строке.
Пожалуйста, не используйте спецификатор %lld для чтения или записи 64-битных чисел на С++. Рекомендуется использовать потоки cin, cout или спецификатор %I64d.
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
-3
4
9
