E. Дэд олонлогийн нийлбэрүүд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Танд $a_1 , a_2 , ..., a_n$ дараалал ба уг олонлогийн индексүүдээс тогтох $m$ ширхэг $S_1, S_2,... , S_m$ дэд олонлогууд өгөгдөнө. $S_k$ = {$S_{k,i}$} ($1 ≤ i ≤ |S_k|$) гэж үзье. Өөрөөр хэлбэл $S_{k,i}$ гэдэг нь $S_k$ дэд олонлогийн гишүүн нь гэсэн үг.

Таны даалгавар бол өгөгдсөн $q$ ширхэг дараах $2$ төрлийн хүсэлтэд хариулах юм.

  1. Үндсэн дараалалд $S_k$ дэд олонлогийн гишүүдээр дугаарлагдсан элементүүдийн нийлбэр болох -г олно. Хүсэлтийн хэлбэр нь "$? \ k$" байна.
  2. $x$ тоогоор үндсэн дараалалд $S_k$ дэд олонлогийн гишүүдээр дугаарлагдсан элементүүдийн утгыг нэмэгдүүлнэ. Өөрөөр хэлбэл $a_{S_{k,i}}$-ийн утгыг $a_{S_{k,i}} + x$ ($1 ≤ i ≤ |S_k|$) болгож өөрчлөнө гэсэн үг. Хүсэлтийн хэлбэр нь "$+ \ k\ x$".

Эхний төрлийн хүсэлт бүрт харгалзах хариуг нэг мөрөнд хэвлэнэ.

Оролт

Эхний мөрөнд $n$, $m$, $q$ ($1 ≤ n, m, q ≤10^5$) бүхэл тоонууд өгөгдөнө. Хоёрдугаар мөр $a_1, a_2, ..., a_n$ ($a_i ≤ |10^8|$) гэсэн $a$ дарааллыг агуулна.

Дараах $m$ мөрөнд нэг нэг $S$ дэд олонлогууд илэрхийлэгдэнэ. $k$-дэх мөрний эхний гишүүн нь $S_k$ олонлогийн гишүүдийн тоо ($|S_k|$) бөгөөд дараагийн $k$ тоо $S$ олонлогийн элементүүд болох $S_{k,1}, S_{k,2}, ... , S_{k,|S_k|}$ ($1 ≤ S_{k,i} ≤ n$) тоог агуулна.

Дараагийн $q$ мөрөнд хүсэлтүүд өгөгдөнө. Бүх хүсэлтүүд "$? \ k$" юм уу "$+ \ k \ x$" хэлбэртэй байх ба $1 ≤ k ≤ m$, $|x| ≤ 10^8$. Хүсэлтүүдэд орж ирсэн дарааллаар нь хариулах ёстой.

Гаралт

Эхний төрлийн хүсэлт бүрийн дараа харгалзах хариуг нэг нэг мөрөнд хэвлэнэ.

C++ хэл дээр 64-битийн тоо хэрэглэх үед %lld-г хэрэглэхгүй байхыг зөвлөж байна. %I64d, эсвэл cin, cout стриймийг ашиглана уу.

Орчуулсан: Говьхүү

Жишээ тэстүүд

Оролт
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
Сэтгэгдлүүдийг ачааллаж байна...