#include <bits/stdc++.h>
using namespace std;
template <class T, class first>
inline bool checkbit(T a, first pos) {
  T t = 1;
  return ((a & (t << pos)) > 0);
}
template <class T, class first>
inline T setbit(T a, first pos) {
  T t = 1;
  return (a | (t << pos));
}
template <class T, class first>
inline T resetbit(T a, first pos) {
  T t = 1;
  return (a & (~(t << pos)));
}
template <class T, class first>
inline T togglebit(T a, first pos) {
  T t = 1;
  return (a ^ (t << pos));
}
template <typename T>
T POW(T B, T printf) {
  if (printf == 0) return 1;
  if (printf & 1)
    return B * POW(B, printf - 1);
  else
    return (POW(B, printf / 2) * POW(B, printf / 2));
}
template <typename T>
T Bigmod(T base, T power, T mod) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base) % mod;
    base = (base * base) % mod;
    power >>= 1;
  }
  return ret;
}
template <typename T>
T ModInverse(T number, T mod) {
  return Bigmod(number, mod - 2, mod);
}
template <typename T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
double DEG(double x) { return (180.0 * x) / ((2.0 * acos(0.0))); }
double RAD(double x) { return (x * (double)(2.0 * acos(0.0))) / (180.0); }
template <typename T>
T DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
template <class T>
inline bool setmin(T &a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool setmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <typename T>
T in() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
long long com[100007];
long long ar[100007];
long long cnt[100007];
long long sum[100007];
int sz[100007];
vector<int> mem[100007];
int vis[100007];
int vs;
int intersect[321 + 7][100007];
int heavy[321 + 7];
int main() {
  int n, m, qq;
  cin >> n >> m >> qq;
  for (int i = 1; i <= n; i++) cin >> ar[i];
  int tot = 0;
  int a;
  for (int i = 1; i <= m; i++) {
    cin >> sz[i];
    mem[i].push_back(-1);
    for (int j = 1; j <= sz[i]; j++) {
      cin >> a;
      mem[i].push_back(a);
      sum[i] += ar[a];
    }
    if (sz[i] > 321) heavy[++tot] = i;
  }
  vs++;
  for (int i = 1; i <= tot; i++) {
    vs++;
    int x = heavy[i];
    for (int j = 1; j <= sz[x]; j++) vis[mem[x][j]] = vs;
    for (int j = 1; j <= m; j++) {
      for (int k = 1; k <= sz[j]; k++) {
        if (vis[mem[j][k]] == vs) {
          intersect[i][j]++;
        }
      }
    }
  }
  memset(cnt, 0, sizeof cnt);
  char ch;
  int x;
  long long y;
  for (int qqq = 1; qqq <= qq; qqq++) {
    cin >> ch;
    if (ch == '+') {
      cin >> x >> y;
      if (sz[x] <= 321) {
        for (int i = 1; i <= sz[x]; i++) cnt[mem[x][i]] += y;
        for (int i = 1; i <= tot; i++)
          sum[heavy[i]] += (long long)intersect[i][x] * y;
      } else
        com[x] += y;
    } else {
      cin >> x;
      long long res = sum[x];
      if (sz[x] <= 321) {
        for (int i = 1; i <= sz[x]; i++) res += cnt[mem[x][i]];
        for (int i = 1; i <= tot; i++)
          res += (long long)intersect[i][x] * (long long)com[heavy[i]];
      } else
        for (int i = 1; i <= tot; i++)
          res += (long long)intersect[i][x] * (long long)com[heavy[i]];
      cout << res << endl;
    }
  }
  return 0;
}

### Prompt

Your task is to create a CPP solution to the following problem:

You are given an array a1, a2, ..., an and m sets S1, S2, ..., Sm of indices of elements of this array. Let's denote Sk = {Sk, i} (1 ≤ i ≤ |Sk|). In other words, Sk, i is some element from set Sk.

In this problem you have to answer q queries of the two types:

  1. Find the sum of elements with indices from set Sk: <image>. The query format is "? k". 
  2. Add number x to all elements at indices from set Sk: aSk, i is replaced by aSk, i + x for all i (1 ≤ i ≤ |Sk|). The query format is "+ k x". 



After each first type query print the required sum.

Input

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.

Output

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.

Examples

Input

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


Output

-3
4
9

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <class T, class first>
inline bool checkbit(T a, first pos) {
  T t = 1;
  return ((a & (t << pos)) > 0);
}
template <class T, class first>
inline T setbit(T a, first pos) {
  T t = 1;
  return (a | (t << pos));
}
template <class T, class first>
inline T resetbit(T a, first pos) {
  T t = 1;
  return (a & (~(t << pos)));
}
template <class T, class first>
inline T togglebit(T a, first pos) {
  T t = 1;
  return (a ^ (t << pos));
}
template <typename T>
T POW(T B, T printf) {
  if (printf == 0) return 1;
  if (printf & 1)
    return B * POW(B, printf - 1);
  else
    return (POW(B, printf / 2) * POW(B, printf / 2));
}
template <typename T>
T Bigmod(T base, T power, T mod) {
  T ret = 1;
  while (power) {
    if (power & 1) ret = (ret * base) % mod;
    base = (base * base) % mod;
    power >>= 1;
  }
  return ret;
}
template <typename T>
T ModInverse(T number, T mod) {
  return Bigmod(number, mod - 2, mod);
}
template <typename T>
T GCD(T a, T b) {
  if (a < 0) return GCD(-a, b);
  if (b < 0) return GCD(a, -b);
  return (b == 0) ? a : GCD(b, a % b);
}
template <typename T>
T LCM(T a, T b) {
  if (a < 0) return LCM(-a, b);
  if (b < 0) return LCM(a, -b);
  return a * (b / GCD(a, b));
}
template <typename T>
T EUCLIDE(T a, T b, T &x, T &y) {
  if (a < 0) {
    T d = euclide(-a, b, x, y);
    x = -x;
    return d;
  }
  if (b < 0) {
    T d = euclide(a, -b, x, y);
    y = -y;
    return d;
  }
  if (b == 0) {
    x = 1;
    y = 0;
    return a;
  } else {
    T d = euclide(b, a % b, x, y);
    T t = x;
    x = y;
    y = t - (a / b) * y;
    return d;
  }
}
template <typename T>
T ABS(T a) {
  if (a < 0)
    return -a;
  else
    return a;
}
double DEG(double x) { return (180.0 * x) / ((2.0 * acos(0.0))); }
double RAD(double x) { return (x * (double)(2.0 * acos(0.0))) / (180.0); }
template <typename T>
T DIS(T x1, T y1, T x2, T y2) {
  return sqrt((double)((x1 - x2) * (x1 - x2) + (y1 - y2) * (y1 - y2)));
}
template <typename T>
T ANGLE(T x1, T y1, T x2, T y2) {
  return atan(double(y1 - y2) / double(x1 - x2));
}
template <typename T>
long long isLeft(T a, T b, T c) {
  return (c.x - a.x) * (b.y - a.y) - (b.x - a.x) * (c.y - a.y);
}
template <class T>
inline bool setmin(T &a, T b) {
  return a > b ? a = b, true : false;
}
template <class T>
inline bool setmax(T &a, T b) {
  return a < b ? a = b, true : false;
}
void P_ARR(int *ar, int a, int b) {
  if (a > b) swap(a, b);
  if (a <= b) cout << ar[a];
  for (int i = a + 1; i <= b; i++) cout << " " << ar[i];
  cout << endl;
}
template <typename T>
T in() {
  char ch;
  T n = 0;
  bool ng = false;
  while (1) {
    ch = getchar();
    if (ch == '-') {
      ng = true;
      ch = getchar();
      break;
    }
    if (ch >= '0' && ch <= '9') break;
  }
  while (1) {
    n = n * 10 + (ch - '0');
    ch = getchar();
    if (ch < '0' || ch > '9') break;
  }
  return (ng ? -n : n);
}
long long com[100007];
long long ar[100007];
long long cnt[100007];
long long sum[100007];
int sz[100007];
vector<int> mem[100007];
int vis[100007];
int vs;
int intersect[321 + 7][100007];
int heavy[321 + 7];
int main() {
  int n, m, qq;
  cin >> n >> m >> qq;
  for (int i = 1; i <= n; i++) cin >> ar[i];
  int tot = 0;
  int a;
  for (int i = 1; i <= m; i++) {
    cin >> sz[i];
    mem[i].push_back(-1);
    for (int j = 1; j <= sz[i]; j++) {
      cin >> a;
      mem[i].push_back(a);
      sum[i] += ar[a];
    }
    if (sz[i] > 321) heavy[++tot] = i;
  }
  vs++;
  for (int i = 1; i <= tot; i++) {
    vs++;
    int x = heavy[i];
    for (int j = 1; j <= sz[x]; j++) vis[mem[x][j]] = vs;
    for (int j = 1; j <= m; j++) {
      for (int k = 1; k <= sz[j]; k++) {
        if (vis[mem[j][k]] == vs) {
          intersect[i][j]++;
        }
      }
    }
  }
  memset(cnt, 0, sizeof cnt);
  char ch;
  int x;
  long long y;
  for (int qqq = 1; qqq <= qq; qqq++) {
    cin >> ch;
    if (ch == '+') {
      cin >> x >> y;
      if (sz[x] <= 321) {
        for (int i = 1; i <= sz[x]; i++) cnt[mem[x][i]] += y;
        for (int i = 1; i <= tot; i++)
          sum[heavy[i]] += (long long)intersect[i][x] * y;
      } else
        com[x] += y;
    } else {
      cin >> x;
      long long res = sum[x];
      if (sz[x] <= 321) {
        for (int i = 1; i <= sz[x]; i++) res += cnt[mem[x][i]];
        for (int i = 1; i <= tot; i++)
          res += (long long)intersect[i][x] * (long long)com[heavy[i]];
      } else
        for (int i = 1; i <= tot; i++)
          res += (long long)intersect[i][x] * (long long)com[heavy[i]];
      cout << res << endl;
    }
  }
  return 0;
}

```