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
class RSAQ{
public:
  typedef long long ll;
  ll n;
  vector<ll> dat,td;
  
  RSAQ(){n = -1;}
  RSAQ(int n_){
    n=1;
    while(n<n_)n*=2; //要素数nを2のべき乗に
    dat.resize(2*n-1,0),td.resize(2*n-1,0);
  }
  
  //[a,b)の区間にxを加算する,query(a,b,x);
  ll add(int a,int b,ll x,int k=0,int l=0,int r=-1){
    if(r==-1) r=n, assert(a <= n && b <= n);
    if(r<=a||b<=l)return 0;
    if(a<=l&&r<=b){
      dat[k]+=(r-l)*x; 
      td[k]+=x;
      return dat[k];
    }

    dat[k]+=(min(r,b)-max(l,a))*x;
    ll kl=k*2+1,kr=k*2+2,t=td[k]*(r-l)/2;
    dat[kl]+=t, dat[kr]+=t;
    td[kl]+=td[k], td[kr]+=td[k];
    td[k]=0;

    ll vl=add(a,b,x,k*2+1,l,(l+r)/2);
    ll vr=add(a,b,x,k*2+2,(l+r)/2,r);
    return vl+vr;
  }
  
  //[a,b)の総和を得る
  ll sum(int a,int b){return add(a,b,0);}
};


class HLD{
public:
  int V;                     //ノード数
  int root;                  //根の頂点番号
  vector<vector<int> > G;    //Grapth
  vector<int> par;           //parent: par[元の頂点番号]->元の頂点番号
  vector<int> Hchild;        //各ノードから伸びるHeavy Childの頂点番号: Hedge[元の頂点番号]->元の頂点番号
  vector<int> number;        //各ノードに割り当てなおした頂点番号: number[元の頂点番号]->振り直した頂点番号
  vector<int> id;            //割り当て直した数字の元のノード番号: id[振り直した頂点番号]->元の頂点番号
  vector<int> group;         //各ノードが所属するグループ番号: group[元の頂点番号]->元の頂点番号
  vector<int> depth;         //根からの各ノードの深さ: depth[元の頂点番号]
  bool ok;                   //build()が済んでいるか
  
  HLD(){root = V = -1;}
  HLD(int V):V(V), root(0), G(V), par(V,-1), Hchild(V,-1), 
             number(V,-1),id(V,-1),group(V,-1),depth(V,0),ok(false){}
  
  void add_edge(int a,int b){
    assert(a < V && b < V);
    G[a].push_back(b);
    G[b].push_back(a);
  }
  
  void build(int _root = 0){
    root = _root;
    int num = 0;
    ok = true;
    dfs1(); numbering(num); dfs2();
  }

  int dfs1(int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    int mx = -1, weight = 1;
    for(int to:G[pos]){
      if(to == pre) continue;
      int cweight = dfs1(to,pos);
      weight += cweight;
      if(mx < cweight) Hchild[pos] = to, mx = cweight;
    }
    return weight;
  }
  
  void dfs2(int pos = -1,int pre = -1,int dep = 0,int g = -1){
    if(pos == -1) pos = g = root;
    par[pos] = pre;
    depth[pos] = dep;
    group[pos] = g;
    for(int to:G[pos]) if(to!=pre) dfs2(to,pos,dep+1,Hchild[pos]==to? g:to);
  }
  
  void numbering(int &cnt,int pos = -1,int pre = -1){
    if(pos == -1) pos = root;
    number[pos] = cnt++;
    id[number[pos]] = pos;
    if(Hchild[pos]>=0) numbering(cnt,Hchild[pos],pos);
    for(int to:G[pos])if(to!=pre && to!=Hchild[pos]) numbering(cnt,to,pos);
  }
  
  typedef pair<int,int> P;
  vector<P> paths;  //[u,v]間の経路をいくつかの「閉区間の連番の経路」に分解する。(最大logN個に分解される)
  vector<P> Ledges; //paths同士を結ぶライトエッジ
  
  //より浅い区間が最初に追加される。
  void buildPaths(int u,int v){
    if(depth[group[u]] < depth[group[v]]) swap(u,v);// 深い方のノードから処理する。
    int nu=number[u], nv=number[v];
    if(same(u,v)){ paths.push_back(P(min(nu,nv),max(nu,nv)));return;} 

    int gu = group[u];
    buildPaths(par[gu],v);

    paths.push_back(P(number[gu], number[u]));
    Ledges.push_back(P(number[par[gu]], number[gu]));
  }
  
  //lca(元の頂点番号,元の頂点番号) -> 元の頂点番号
  int lca(int u,int v){
    assert(ok && "Please Build");
    if(depth[group[u]] < depth[group[v]]) swap(u,v);
    if(same(u,v)) return depth[u] < depth[v]? u:v;
    return lca(par[group[u]],v);
  }
  
  //getPath(元の頂点番号,元の頂点番号) -> 振り直した頂点番号
  pair<vector<P>, vector<P> > getPath(int u,int v){
    assert(ok && "Please Build");
    paths.clear();
    Ledges.clear();
    buildPaths(u,v);
    return make_pair(paths,Ledges);
  }

  /*(元の頂点番号,元の頂点番号)*/ 
  bool same(int a,int b){return group[a] == group[b];}
};

signed main(){
  int n;
  cin>>n;

  HLD hld(n);
  for(int i=0;i<n;i++){
    int k;
    cin>>k;
    for(int j=0;j<k;j++) {
      int c;
      cin>>c;
      hld.add_edge(i, c);
    }
  }

  hld.build();
  RSAQ A(n);

  auto query0=[&](int u,int w){
    auto path = hld.getPath(0,u).first;
    path[0].first++;
    for(auto p:path){
      int l = p.first;
      int r = p.second;
      A.add(l,r+1,w);
    }
  };

  auto query1=[&](int u){
    auto path = hld.getPath(0,u).first;
    path[0].first++;
    int res = 0;
    for(auto p:path){
      int l = p.first;
      int r = p.second;
      res += A.sum(l,r+1);
    }
    return res;
  };
  
  int q;
  cin>>q;
  while(q--){
    int cmd;
    cin>>cmd;

    if(cmd == 0){
      int v,w;
      cin>>v>>w;
      query0(v, w);
    }
    if(cmd == 1){
      int u;
      cin>>u;
      int ans = query1(u);
      cout<<ans<<endl;
    }

  }
  return 0;
}