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>
#define int long long
using namespace std;

class BIT{
public:
  typedef long long ll;
  ll n;
  vector<ll> bit0, bit1;
  BIT(){n=-1;}
  BIT(ll n_){
    n=1;
    while(n<n_)n*=2;
    bit0.resize(n+1,0);
    bit1.resize(n+1,0);
  }
  
  ll sum(vector<ll> &b,ll i){
    ll s=0;
    while(i>0){
      s=(s+b[i]);
      i-=i&-i;
    }
    return s;
  }

  void add(vector<ll> &b,ll i,ll v){
    while(i<=n){
      b[i]=(b[i]+v);
      i+=i&-i;
    }
  }

  //[a,b]にxを加算(1<=a)
  void add (ll a,ll b,ll x){
    assert(a > 0 && n >= 0);

    add(bit0,a,-x*(a-1));
    add(bit1,a,x);
    add(bit0,b+1,x*b);
    add(bit1,b+1,-x);
  }

  //[a,b]のsumを得る(1<=a)
  ll sum(ll a,ll b){
    assert(a > 0 && n >= 0);
    ll res=0;
    res+=sum(bit0,b)+sum(bit1,b)*b;
    res-=sum(bit0,a-1)+sum(bit1,a-1)*(a-1);
    return res;
  }
};

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]));
  }
  
  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];}
};

typedef pair<int,int> P;

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

  HLD 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();
  
  BIT bit=BIT(n);
  
  int q;
  cin>>q;

  while(q--){
    
    int a;
    cin>>a;

    if(a==0){
      
      int v, w;
      cin>>v>>w;
      
      pair<vector<P>, vector<P> > tmp=hld.getPath(0, v);
    
      vector<P> path=tmp.first;
      vector<P> le=tmp.second;
      
      for(int i=0;i<path.size();i++){
	
	int s=path[i].first+2, t=path[i].second+1;
	
	if(s>t) continue;
	
	bit.add(s, t, w);
	
      }

      for(int i=0;i<le.size();i++){
	
	int node=le[i].second+1;
	
	bit.add(node, node, w);
      }
      
    }
    else{
      
      int u;
      cin>>u;
      
      pair<vector<P>, vector<P> > tmp=hld.getPath(0, u);
      
      vector<P> path=tmp.first;
      vector<P> le=tmp.second;
      
      int sum=0;
      
      for(int i=0;i<path.size();i++){
	
	int s=path[i].first+2, t=path[i].second+1;
	
	if(s>t) continue;
	
	sum+=bit.sum(s, t);
	
      }
      
      for(int i=0;i<le.size();i++){
	
	int node=le[i].second+1;
	
	sum+=bit.sum(node, node);
      }

      cout<<sum<<endl;
    }
  }
  
  /*
cout<<"group"<<endl;
  
  for(int i=0;i<n;i++) cout<<i<<' '<<hld.group[i]<<endl;
  
  cout<<"num"<<endl;
  
  for(int i=0;i<n;i++) cout<<i<<' '<<hld.number[i]<<endl;
  
  while(1){
    
    int a, b;
    cin>>a>>b;
    
    pair<vector<P>, vector<P> > r=hld.getPath(a, b);
    
    vector<P> path=r.first;
    vector<P> le=r.second;
    
    cout<<"path"<<endl;
    
    for(int i=0;i<path.size();i++) cout<<path[i].first<<' '<<path[i].second<<endl;


    cout<<"le"<<endl;

    for(int i=0;i<le.size();i++) cout<<le[i].first<<' '<<le[i].second<<endl;
  }
  */
  return 0;
}