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 Int = long long;
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;

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

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

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

  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 propagete(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);
    /* note: ここに反転の処理 */
    t->rev ^= true;
  }

  void push(Node *t) {
    if(t->lazy != OM0) {
      if(t->l) propagete(t->l, t->lazy);
      if(t->r) propagete(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()) {
        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);
          else rotl(t), rotr(t);
        } else {
          if(q->r == t) rotl(q), rotl(t);
          else rotr(t), rotl(t);
        }
      }
    }
  }

  Node *expose(Node *t) {
    Node *rp = nullptr;
    for(Node *cur = t; cur; cur = cur->p) {
      splay(cur);
      cur->r = rp;
      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 > getpath(Node *x) {
    vector< Int > vs;
    function< void(Node *) > dfs = [&](Node *cur) {
      if(!cur) return;
      push(cur);
      dfs(cur->r);
      vs.push_back(cur->idx);
      dfs(cur->l);
    };
    expose(x);
    dfs(x);
    return vs;
  }

  void set_propagete(Node *t, const OperatorMonoid &x) {
    expose(t);
    propagete(t, x);
    push(t);
  }
};
//INSERT ABOVE HERE
signed main(){
  Int n;
  cin>>n;
  using LCT = LinkCutTree<Int,int>;
  LCT::F f=[](Int a,Int b){return a+b;};
  LCT::G g=[](Int a,Int b,Int c){return a+b*c;};
  LCT lc(f,g,f,0,0);

  vector<LCT::Node*> v(n);
  for(Int i=0;i<n;i++) v[i]=lc.make_node(i);
  for(Int i=0;i<n;i++){
    Int k;
    cin>>k;
    for(Int j=0;j<k;j++){
      Int c;
      cin>>c;
      lc.link(v[c],v[i]);
    }
  }
  
  Int q;
  cin>>q;
  Int c=0;
  for(Int i=0;i<q;i++){
    Int t;
    cin>>t;
    if(t==0){
      Int a,b;
      cin>>a>>b;
      lc.set_propagete(v[a],b);
      c+=b;
    }
    if(t==1){
      Int a;
      cin>>a;
      lc.expose(v[a]);
      cout<<v[a]->sum-c<<endl;
    }
  }  
  return 0;
}