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 <stdio.h>
#include <vector>
using namespace std;
const int N=1e5+10;
struct SEG{
    vector<long long int> v,f;
    int size;
    void init(int n){
        size=n;
        v.resize(size*4,0);
        f.resize(size*4,0);
        return ;
    }
    void add(int n,int pos,int l,int r,int x){
        if(pos>=r){
            f[n]+=x;
            v[n]+=(r-l+1)*(long long int)x;
        }
        else if(pos>=l){
            int mid=(l+r)>>1;
            if(f[n]!=0){
                v[n*2+1]+=(mid-l+1)*f[n];
                v[n*2+2]+=(r-mid)*f[n];
                f[n*2+1]+=f[n];
                f[n*2+2]+=f[n];
                f[n]=0;
            }
            add(n*2+1,pos,l,mid,x);
            add(n*2+2,pos,mid+1,r,x);
            v[n]=v[n*2+1]+v[n*2+2];
        }
        return ;
    }
    long long int ask(int n,int pos,int l,int r){
        if(pos>=r)return v[n];
        else if(pos<l)return 0;
        else{
            int mid=(l+r)>>1;
            if(f[n]!=0){
                v[n*2+1]+=(mid-l+1)*f[n];
                v[n*2+2]+=(r-mid)*f[n];
                f[n*2+1]+=f[n];
                f[n*2+2]+=f[n];
                f[n]=0;
            }
            return ask(n*2+1,pos,l,mid)+ask(n*2+2,pos,mid+1,r);
        }
    }
};
vector<int> graph[N];
int top[N],dep[N],to[N],size[N],p[N],val[N];
SEG b[N];
void dfs(int now){
    int temp=0;
    size[now]=1;
    for(int i:graph[now]){
        p[i]=now;
        dep[i]=dep[now]+1;
        dfs(i);
        if(size[i]>temp){
            temp=size[i];
            to[now]=i;
        }
        size[now]+=size[i];
    }
}
void init(int now){
    if(graph[now].empty()&&top[now]!=now)b[top[now]].init(dep[now]-dep[top[now]]);
    for(int i:graph[now]){
        if(i==to[now])top[i]=top[now];
        else top[i]=i;
        init(i);
    }
    return ;
}
void fix(int n,int w){
    while(n>0){
        if(top[n]!=n)b[top[n]].add(0,dep[n]-dep[top[n]]-1,0,b[top[n]].size-1,w);
        if(top[n]!=0)val[top[n]]+=w;
        n=p[top[n]];
    }
    return ;
}
long long int query(int n){
    long long int ans=0;
    while(n>0){
        if(n!=top[n])ans+=b[top[n]].ask(0,dep[n]-dep[top[n]]-1,0,b[top[n]].size-1);
        if(top[n]!=0)ans+=val[top[n]];
        n=p[top[n]];
    }
    return ans;
}
int main(){
    int n,k,temp,q;
    scanf("%d",&n);
    for(int i=0;i<n;i++){
        scanf("%d",&k);
        for(int j=0;j<k;j++){
            scanf("%d",&temp);
            graph[i].push_back(temp);
        }
    }
    p[0]=-1;
    dep[0]=0;
    top[0]=0;
    dfs(0);
    init(0);
    scanf("%d",&q);
    while(q--){
        scanf("%d",&k);
        if(k==0){
            scanf("%d%d",&k,&temp);
            fix(k,temp);
        }
        else{
            scanf("%d",&temp);
            printf("%lld\n",query(temp));
        }
    }
}