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;
typedef long long ll;
#define int ll
typedef pair<int,int> pii;
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define all(a) (a).begin(),(a).end()
#define pb emplace_back

//0-index 抽象化半開区間遅延セグツリー
template<typename T, typename E>
class segment_tree{
    typedef function<T(T,T)> F; //要素に適用する演算
    typedef function<T(T,E)> G; //作用素の適用
    typedef function<E(E,E)> H; //作用素の合成
    typedef function<E(E,int)> P;
    private:
    int num_of_elm_;
    vector<T> dat_, lazy_;
    F f_;
    G g_;
    H h_;
    P p_;
    T ident_;
    E op_ident_;
    public:
    segment_tree(int n, F f, G g, H h, P p, T ident, E op_ident):f_(f), g_(g), h_(h), p_(p), ident_(ident), op_ident_(op_ident){
        num_of_elm_ = 1;
        while(num_of_elm_<n)num_of_elm_*=2;
        dat_ .resize(2*num_of_elm_,ident);
        lazy_.resize(2*num_of_elm_,op_ident);
    }
    
    void build(vector<T> vec){
        rep(i,vec.size()) dat_[num_of_elm_+i] = vec[i];
        for(int i=num_of_elm_-1;i>=1;i--)dat_[i] = f_(dat_[i*2],dat_[i*2+1]);
    }
    
    void eval(int k, int len){
        if(lazy_[k] == op_ident_)return ;
        
        if(k<num_of_elm_){
            lazy_[k*2]=h_(lazy_[k*2], lazy_[k]);
            lazy_[k*2+1]=h_(lazy_[k*2+1], lazy_[k]);
        }
        dat_[k] = g_(dat_[k],p_(lazy_[k], len));
        lazy_[k] = op_ident_;
    }
    
    T update(int L, int R, int val, int l=0, int r=0, int k=1){
        if(k==1)r = num_of_elm_;
        
        eval(k,r-l);
        if(r<=L || R<=l)return dat_[k];
        else if(L<=l && r<=R){
            lazy_[k] = h_(lazy_[k], val);
            return g_(dat_[k], p_(lazy_[k], r-l));
        }
        else{
            return dat_[k] = f_(update(L,R,val,l,(l+r)/2,k*2), update(L,R,val,(l+r)/2,r,k*2+1));
        }
        
    }
    
    T query(int L, int R,int l=0,int r=0, int k=1){
        if(k==1)r = num_of_elm_;
        
        eval(k,r-l);
        if(r<=L || R<=l)return ident_;
        else if(L<=l && r<=R){
            return dat_[k];
        }
        else{
            return f_(query(L,R,l,(l+r)/2,k*2), query(L,R,(l+r)/2,r,k*2+1));
        }
    }
};

template<typename T, typename E>
class HLDecomposition{    //verified NJPC-H
    typedef function<T(T,T)> F; //要素に適用する演算
    typedef function<T(T,E)> G; //作用素の適用
    typedef function<E(E,E)> H; //作用素の合成
    typedef function<E(E,int)> P;
    
    public:
    vector<vector<int>> Graph;
    
    vector<int> vid, head, heavy, par, depth, inv;
    segment_tree<T,E> segt;
    
    HLDecomposition(int V, F f, G g, H h, P p, T ident, E op_ident): Graph(V), vid(V,-1), head(V), heavy(V,-1), par(V), depth(V), inv(V), segt(V, f, g, h, p, ident, op_ident) {}
    
    void add_edge(int u,int v){
        Graph[u].pb(v);
        Graph[v].pb(u);
    }
    
    void build(){
        dfs(0,-1);
        bfs();
    }
    
    int dfs(int cur, int prev){
        par[cur] = prev;
        int sub=1, chil_sub_max=0;
        for(auto e:Graph[cur]){
            if(e==prev)continue;
            depth[e] = depth[cur]+1;
            int res = dfs(e,cur);
            sub += res;
            if(chil_sub_max<res)chil_sub_max = res, heavy[cur] = e;
        }
        return sub;
    }
    
    void bfs(){
        int num = 0;
        queue<int> q({0});
        while(q.size()){
            int headv = q.front(); q.pop();
            int cur = headv;
            while(cur!=-1){
                vid[cur] = num++;
                inv[vid[cur]] = cur;
                head[cur] = headv;
                for(auto e:Graph[cur]){
                    if(e!=par[cur]&&e!=heavy[cur])q.push(e);
                }
                cur = heavy[cur];
            }
        }
    }
    
    //u-vパスをchainに分解し、それぞれの頂点に対して処理を行う
    void for_each(int u, int v, function<void(int, int)> f){
        if(vid[u]>vid[v])swap(u,v);
        f(max(vid[head[v]],vid[u]), vid[v]);
        if(head[u]!=head[v])for_each(u,par[head[v]], f);
    }
    
    //u-vパスをchainに分解し、それぞれの辺に対して処理を行う
    void for_each_edge(int u, int v, function<void(int, int)> f){
        if(vid[u]>vid[v])swap(u,v);
        if(head[u]!=head[v]){
            f(vid[head[v]],vid[v]);
            for_each_edge(u,par[head[v]],f);
        }else{
            if(u!=v)f(vid[u]+1,vid[v]);
        }
    }
    
    int lca(int u, int v) {
        if(vid[u]>vid[v])swap(u,v);
        if(head[u]==head[v])return u;
        return lca(u, par[head[v]]);
    }
    
};

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

    auto f = [](int a, int b){ return a+b; };
    auto g = f;
    auto h = f;
    auto p = [](int a, int num){ return a*num; };
    HLDecomposition<int,int> hld(v, f, g, h, p, 0, 0);
    
    rep(i,v){
        int k;
        cin>>k;
        rep(j,k){
            int to;
            cin>>to;
            hld.add_edge(i, to);
        }
    }
    hld.build();
    
    int q;
    cin>>q;
    rep(i,q){
        
        int type;
        cin>>type;
        if(type==0){
            int u,w;
            cin>>u>>w;
            hld.for_each_edge(0, u, [&](int l, int r){ hld.segt.update(l, r+1, w); });
        }else{
            int x;
            cin>>x;
            int res = 0;
            hld.for_each_edge(0, x, [&](int l, int r){ res += hld.segt.query(l, r+1); });
            cout<<res<<endl;
        }
    }
    
}