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;

using int64 = long long;

template< typename data_t, typename lazy_t >
struct LCNode {
  using LP = LCNode *;

  LP l, r, p;
  int idx, sz;
  bool rev;
  data_t key, sum;
  lazy_t lazy;

  void init_node(int idx, const data_t &v) {
    this->sz = 1;
    this->idx = idx;
    this->lazy = 0;
    this->key = this->sum = v;
  }

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

  void propagate(const lazy_t &v) {
    lazy += v;
    key += v;
    sum += v * sz;
  }

  void toggle() {
    swap(l, r);
    rev ^= true;
  }

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

  void push() {
    if(lazy) {
      if(l) l->propagate(lazy);
      if(r) r->propagate(lazy);
      lazy = 0;
    }
    if(rev) {
      if(l) l->toggle();
      if(r) r->toggle();
      rev = false;
    }
  }

  void rotr() {
    LP x = p, y = x->p;
    if((x->l = r)) r->p = x;
    r = x, x->p = this;
    x->update(), update();
    if((p = y)) {
      if(y->l == x) y->l = this;
      if(y->r == x) y->r = this;
      y->update();
    }
  }

  void rotl() {
    LP x = p, y = x->p;
    if((x->r = l)) l->p = x;
    l = x, x->p = this;
    x->update(), update();
    if((p = y)) {
      if(y->l == x) y->l = this;
      if(y->r == x) y->r = this;
      y->update();
    }
  }

  void splay() {
    push();
    while(!is_root()) {
      LP q = p;
      if(q->is_root()) {
        q->push(), push();
        if(q->l == this) rotr();
        else rotl();
      } else {
        LP r = q->p;
        r->push(), q->push(), push();
        if(r->l == q) {
          if(q->l == this) q->rotr(), rotr();
          else rotl(), rotr();
        } else {
          if(q->r == this) q->rotl(), rotl();
          else rotr(), rotl();
        }
      }
    }
  }

  LP expose() {
    LP rp = nullptr;
    for(LP cur = this; cur; cur = cur->p) {
      cur->splay();
      cur->r = rp;
      cur->update();
      rp = cur;
    }
    splay();
    return rp;
  }

  void link(LP parent) {
    expose();
    parent->expose();
    p = parent;
    parent->r = this;
  }

  void cut() {
    expose();
    LP parent = l;
    l = nullptr;
    parent->p = nullptr;
  }

  void evert() {
    expose();
    toggle();
    push();
  }

  LP lca(LP v) {
    expose();
    return v->expose();
  }

  void set_propagate(const lazy_t &x) {
    expose();
    propagate(x);
    push();
  }
};

using int64 = long long;

int main() {
  int N;
  scanf("%d", &N);
  auto f = [&](int64 x, int64 y) { return x + y; };
  auto g = [&](int64 x, int64 y, int64 z) { return x + y * z; };
  using LCTree = LCNode< int64, int64 >;
  vector< LCTree * > uku(N);
  for(int i = 0; i < N; i++) {
    uku[i] = new LCTree();
    uku[i]->init_node(i, 0);
  }
  for(int i = 0; i < N; i++) {
    int K;
    scanf("%d", &K);
    while(K--) {
      int T;
      scanf("%d", &T);
      uku[T]->link(uku[i]);
    }
  }
  int Q;
  scanf("%d", &Q);
  int64 all = 0;
  while(Q--) {
    int T;
    scanf("%d", &T);
    if(T == 0) {
      int V, W;
      scanf("%d %d", &V, &W);
      uku[V]->set_propagate(W);
      all += W;
    } else {
      int U;
      scanf("%d", &U);
      uku[U]->expose();
      printf("%lld\n", uku[U]->sum - all);
    }
  }
}