Problem: Write a program which manipulates a weighted rooted tree $T$ with the following operations:

* $add(v,w)$: add $w$ to all edges from the root to node $u$

* $getSum(u)$: report the sum of weights of all edges from the root to node $u$



The given tree $T$ consists of $n$ nodes and every node has a unique ID from $0$ to $n-1$ respectively where ID of the root is $0$. Note that all weights are initialized to zero.

Constraints

* All the inputs are given in integers
* $ 2 \leq n \leq 100000 $
* $ c_j < c_{j+1} $   $( 1 \leq j \leq k-1 )$
* $ 2 \leq q \leq 200000 $
* $ 1 \leq u,v \leq n-1 $
* $ 1 \leq w \leq 10000 $

Input

The input is given in the following format.

$n$
$node_0$
$node_1$
$node_2$
$:$
$node_{n-1}$
$q$
$query_1$
$query_2$
$:$
$query_{q}$


The first line of the input includes an integer $n$, the number of nodes in the tree.

In the next $n$ lines,the information of node $i$ is given in the following format:


ki c1 c2 ... ck


$k_i$ is the number of children of node $i$, and $c_1$ $c_2$ ... $c_{k_i}$ are node IDs of 1st, ... $k$th child of node $i$.

In the next line, the number of queries $q$ is given. In the next $q$ lines, $i$th query is given in the following format:


0 v w


or


1 u


The first integer represents the type of queries.'0' denotes $add(v, w)$ and '1' denotes $getSum(u)$.

Output

For each $getSum$ query, print the sum in a line.

Examples

Input

6
2 1 2
2 3 5
0
0
0
1 4
7
1 1
0 3 10
1 2
0 4 20
1 3
0 5 40
1 4


Output

0
0
40
150


Input

4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3


Output

3000
5000
6000

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int maxn = 100005;
const int maxlogn = 18;

struct Chain {
  // parent
  int parent;
  // top and bottom node
  int top, bottom;
  // segment tree ID
  int segId;
};

struct Node {
  int l, r, nl, nr;
  ll sum, lazy;

  Node(int l, int r, int nl, int nr)
    : l(l), r(r), nl(nl), nr(nr), sum(0), lazy(0) {}
  Node() {}

  void update(int ql, int qr, int v);
  ll query(int ql, int qr);
};

// Global variables declared here
int cid = 1;        // chain allocation ID
int pid = 1;        // preorder position
int nid = 1;        // seg allocation ID
Chain chain[maxn];
Node seg[maxn * 2];
int n, q;
vector<int> childs[maxn];
int jt[maxlogn][maxn];
int depth[maxn];
int belong[maxn];   // chain id that seg belongs to
int pos[maxn];      // position in segment tree
int size[maxn];     // size of subtree
int pc[maxn];       // preferred child (child with largest number of segs)
int po[maxn];       // preorder array
int poi[maxn];      // inverse preorder array
ll ttl0 = 0;        // total augment to 0 (to be subtracted)
// End of global variables

void Node::update(int ql, int qr, int v) {
  if (ql == l && qr == r) {
    lazy += v;
    return;
  }

  int m = l + r >> 1;
  if (qr <= m)
    seg[nl].update(ql, qr, v);
  else if (ql > m)
    seg[nr].update(ql, qr, v);
  else
    seg[nl].update(ql, m, v), seg[nr].update(m + 1, qr, v);

  sum = seg[nl].sum + seg[nr].sum +
    seg[nl].lazy * (m - l + 1) +
    seg[nr].lazy * (r - m);
}

ll Node::query(int ql, int qr) {
  int m = l + r >> 1;
  ll lz = lazy * (qr - ql + 1);

  if (ql == l && qr == r) {
    return lz + sum;
  }

  if (qr <= m)
    return lz + seg[nl].query(ql, qr);
  else if (ql > m)
    return lz + seg[nr].query(ql, qr);
  else
    return lz + seg[nl].query(ql, m) + seg[nr].query(m + 1, qr);
}

int build(int l, int r) {
  int id = nid++;
  int m = l + r >> 1;

  if (l == r) {
    seg[id] = Node(l, r, 0, 0);
  } else {
    seg[id] = Node(l, r, build(l, m), build(m + 1, r));
  }

  return id;
}

void dfs(int n, int p = -1) {
  depth[n] = p == -1 ? 0 : depth[p] + 1;
  size[n] = 1;
  pc[n] = -1;

  for (int h : childs[n]) {
    dfs(h, n);
    size[n] += size[h];
    if (pc[n] == -1 || size[h] > size[pc[n]])
      pc[n] = h;
  }

  //printf("Pc of %d is %d\n", n, pc[n]);
}

int makeChain(int v, int p = -1) {
  chain[cid].parent = p;
  chain[cid].top = chain[cid].bottom = v;
  return cid++;
}

void hld(int v, int c) {
  //printf("Node %d belongs to chain %d\n", v, c);

  poi[v] = pid, po[pid] = v;
  belong[v] = c;
  chain[c].bottom = v;
  pid++;

  if (pc[v] != -1) {
    hld(pc[v], c);
  }

  for (int h : childs[v]) {
    if (h != pc[v]) {
      hld(h, makeChain(h, c));
    }
  }
}

void init() {
  dfs(0);

  jt[0][0] = -1;

  for (int i = 0; i < maxlogn - 1; i++) {
    for (int j = 0; j < n; j++) {
      if (jt[i][j] != -1) {
        jt[i + 1][j] = jt[i][jt[i][j]];
      }
    }
  }

  // HLD
  hld(0, makeChain(0));

  for (int i = 1; i < cid; i++) {
    int t = chain[i].top, b = chain[i].bottom;
    int tt = poi[t], bb = poi[b];
    //printf("Chain %d is from %d to %d: seg is from %d to %d\n",
        //i, t, b, tt, bb);
    chain[i].segId = build(tt, bb);
  }
}

// Walk up n from v
int up(int v, int n) {
  for (int i = maxlogn - 1; i >= 0; i--) {
    if (n & (1 << i)) {
      v = jt[i][v];
    }
  }

  return v;
}

int lca(int a, int b) {
  if (depth[a] > depth[b])
    swap(a, b);

  b = up(b, depth[b] - depth[a]);

  if (a == b)
    return a;

  for (int i = maxlogn - 1; i >= 0; i--) {
    if (jt[i][a] != jt[i][b]) {
      a = jt[i][a], b = jt[i][b];
    }
  }

  return jt[0][a];
}

void add(int v, int w) {
  int c = belong[v];
  do {
    //printf("At %d, chain %d\n", v, c);
    int ss = chain[c].segId;
    seg[ss].update(poi[chain[c].top], poi[v], w);
    v = jt[0][chain[c].top];
    c = chain[c].parent;
  } while (c != -1);
}

ll query(int v) {
  int c = belong[v];
  ll ans = 0;
  do {
    //printf("At %d, chain %d\n", v, c);
    int ss = chain[c].segId;
    ans += seg[ss].query(poi[chain[c].top], poi[v]);
    v = jt[0][chain[c].top];
    c = chain[c].parent;
  } while (c != -1);
  return ans - ttl0;
}

int main() {
  cin >> n;
  for (int i = 0; i < n; i++) {
    int k; cin >> k;
    for (int j = 0; j < k; j++) {
      int c; cin >> c;
      childs[i].push_back(c);
      jt[0][c] = i;
    }
  }

  init();

  cin >> q;
  for (int i = 0; i < q; i++) {
    int o; cin >> o;
    for (int i = 1; i < n; i++) {
      //printf("%d [%lld] ", i, seg[chain[belong[i]].segId].query(poi[i], poi[i]));
    }
    //puts("");
    if (o == 0) {
      int v, w; cin >> v >> w;
      add(v, w);
      ttl0 += w;
    } else {
      int u; cin >> u;
      cout << query(u) << endl;
    }
  }
}