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;

#define int long long

// LinkCutTree
// 各Heavy-edge連結成分を表すBSTをin-orderで捜査すると、元のパスになる
template<typename Monoid = int, typename OperatorMonoid = Monoid>
struct LinkCutTree {
  using F = function<Monoid(Monoid, Monoid)>;
  using G = function<Monoid(Monoid, OperatorMonoid, int)>;
  using H = function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;

  struct Node {
    Node *l, *r, *p;
    int idx;
    Monoid key, sum;
    OperatorMonoid lazy;

    bool rev;
    int sz;

    Node(int idx, const Monoid& key, const OperatorMonoid &om):l(nullptr), r(nullptr), p(nullptr), idx(idx), key(key), sum(key), lazy(om), rev(false), sz(1) {}

    bool is_root() {
      return !p || (p->l != this && p->r != this);
    }
  };

  const F f;
  const G g;
  const H h;
  const Monoid M1;
  const OperatorMonoid OM0;

  LinkCutTree():LinkCutTree([](Monoid a, Monoid b) {return a+b;}, Monoid()) {}
  LinkCutTree(const F &f, const Monoid &M1):LinkCutTree(f, G(), H(), M1, OperatorMonoid()) {}
  LinkCutTree(const F &f, const G &g, const H &h, const Monoid &M1, const OperatorMonoid &OM0):f(f), g(g), h(h), M1(M1), OM0(OM0) {}

  Node *make_node(int idx, const Monoid &v = Monoid()) {
    return new Node(idx, v, OM0);
  }

  void propagate(Node *t, const OperatorMonoid &x) {
    t->lazy = h(t->lazy, x);
    t->key = g(t->key, x, 1);
    t->sum = g(t->sum, x, t->sz);
  }

  void toggle(Node *t) {
    assert(t);
    swap(t->l, t->r);
    /*ここに反転処理*/
    t->rev ^= true;
  }

  void push(Node *t) {
    if(t->lazy != OM0) {
      if(t->l) propagate(t->l, t->lazy);
      if(t->r) propagate(t->r, t->lazy);
      t->lazy = OM0;
    }
    if(t->rev) {
      if(t->l) toggle(t->l);
      if(t->r) toggle(t->r);
      t->rev = false;
    }
  }

  void update(Node *t) {
    t->sz = 1;
    t->sum = t->key;
    if(t->l) t->sz += t->l->sz, t->sum = f(t->l->sum, t->sum);
    if(t->r) t->sz += t->r->sz, t->sum = f(t->sum, t->r->sum);
  }

  void rotr(Node *t) {
    auto *x = t->p, *y = x->p;
    if((x->l = t->r)) t->r->p = x;
    t->r = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void rotl(Node *t) {
    auto *x = t->p, *y = x->p;
    if((x->r = t->l)) t->l->p = x;
    t->l = x, x->p = t;
    update(x), update(t);
    if((t->p = y)) {
      if(y->l == x) y->l = t;
      if(y->r == x) y->r = t;
      update(y);
    }
  }

  void splay(Node *t) {
    push(t);
    while(!t->is_root()) {
      auto *q = t->p;
      if(q->is_root()) { // zig
	push(q), push(t);
	if(q->l == t) rotr(t);
	else rotl(t);
      } else {
	auto *r = q->p;
	push(r), push(q), push(t);
	if(r->l == q) {
	  if(q->l == t) rotr(q), rotr(t); // zig zig
	  else rotl(t), rotr(t); // zig zag
	} else {
	  if(q->r == t) rotl(q), rotl(t); // zig zig
	  else rotr(t), rotl(t); // zig zag
	}
      }
    }
  }

  Node *expose(Node *t) {
    Node *rp = nullptr;
    for(Node *cur = t; cur; cur = cur->p /*Light-edgeで移動*/) {
      splay(cur);
      cur->r = rp; // Heavy-edgeでつなぐ(元のHeavy-edgeは切れる)
      update(cur);
      rp = cur;
    }
    splay(t);
    return rp;
  }

  void link(Node *child, Node *parent) {
    expose(child);
    expose(parent);
    child->p = parent;
    parent->r = child;
  }

  void cut(Node *child) {
    expose(child);
    auto *parent = child->l;
    child->l = nullptr;
    parent->p = nullptr;
  }

  void evert(Node *t) {
    expose(t);
    toggle(t);
    push(t);
  }

  Node *lca(Node *u, Node *v) {
    expose(u);
    return expose(v);
  }

  vector<int> get_path(Node *x) {
    vector<int> vs;
    function<void(Node*)> dfs = [&](Node *cur) {
      if(!cur) return;
      dfs(cur->r);
      vs.push_back(cur->idx);
      dfs(cur->l);
    };
    expose(x);
    dfs(x);
    return vs;
  }

  void set_propagate(Node *t, const OperatorMonoid &x) {
    expose(t);
    propagate(t, x);
    push(t);
  }
};

signed main() {
  int n;
  cin >> n;
  auto f = [&](int a, int b) { return a + b; };
  auto g = [&](int a, int b, int len) { return a + b*len; };
  auto h = [&](int a, int b) { return a + b; };
  LinkCutTree<int> tree(f, g, h, 0, 0);
  vector<LinkCutTree<int>::Node*> nodes(n);
  for(int i = 0; i < n; ++i) nodes[i] = tree.make_node(i);
  for(int i = 0; i < n; ++i) {
    int k;
    cin >> k;
    while(k--) {
      int c;
      cin >> c;
      tree.link(nodes[c], nodes[i]);
    }
  }
  int q;
  cin >> q;
  while(q--) {
    int k;
    cin >> k;
    if(k) {
      int u;
      cin >> u;
      tree.expose(nodes[u]);
      cout << nodes[u]->sum << endl;
    } else {
      int v, w;
      cin >> v >> w;
      tree.set_propagate(nodes[v], w);
      tree.set_propagate(nodes[0], -w);
    }
  }
  return 0;
}