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 int ll;
typedef vector<ll> vl;
typedef pair<ll, ll> PP;
#define rep(i, n) for(ll i = 0; i < ll(n); i++)
template <class T> void corner(bool flg, T hoge) {
    if(flg) {
        cout << hoge << endl;
        exit(0);
    }
}
#define all(v) v.begin(), v.end()
#define inputv(v, n)                                                           \
    vl v;                                                                      \
    rep(i, n) {                                                                \
        ll x;                                                                  \
        cin >> x;                                                              \
        v.push_back(x);                                                        \
    }
const ll INF = 999999999999999;
const ll MOD = 1000000007;
const ll MAX_N = 500010;
ll a, b, c, d, e, f, p, t, x, y, z, q, m, n, r, h, k, w, l, ans;
struct edge {
    ll to, cost;
};
vector<edge> g[MAX_N];
vl visited,par(MAX_N,-1);

void add(ll a, ll b, ll c = 1) { g[a].push_back((edge) { b, c }); }

void resetv(void) { visited = vl(n, 0); }

vl sz(MAX_N,-1), in(MAX_N), out(MAX_N),nxt(MAX_N,0), HLcost(MAX_N, 0); // sz:size of root_

void dfs_sz(ll v = 0) {
    sz[v] = 1;
    for (auto &u : g[v]) {
        dfs_sz(u.to);
        sz[v] += sz[u.to];
        if (sz[u.to] > sz[g[v][0].to]) {
            swap(u, g[v][0]);
        }
    }
}

void dfs_hld(ll v = 0) {
    in[v] = t++;
        for (auto u : g[v]) {
            nxt[u.to] = (u.to == g[v][0].to ? nxt[v] : u.to);
            dfs_hld(u.to);
        }
    out[v] = t;
}

void HLD(ll v = 0) {
    t = 0;
    resetv();
    dfs_sz();
	dfs_hld();
}

struct LazySegmentTree {
private:
    int n;
    vector<ll> node, lazy;

public:
    LazySegmentTree(vector<ll> v) {
        int sz = (int)v.size();
        n = 1;
        while (n < sz)
            n *= 2;
        node.resize(2 * n - 1);
        lazy.resize(2 * n - 1, 0);

        for (int i = 0; i < sz; i++)
            node[i + n - 1] = v[i];
        for (int i = n - 2; i >= 0; i--)
            node[i] = node[i * 2 + 1] + node[i * 2 + 2];
    }

    // k 番目のノードについて遅延評価を行う
    void eval(int k, int l, int r) {

        // 遅延配列が空でない場合、自ノード及び子ノードへの
        // 値の伝播が起こる
        if (lazy[k] != 0) {
            node[k] += lazy[k];

            // 最下段かどうかのチェックをしよう
            // 子ノードは親ノードの 1/2 の範囲であるため、
            // 伝播させるときは半分にする
            if (r - l > 1) {
                lazy[2 * k + 1] += lazy[k] / 2;
                lazy[2 * k + 2] += lazy[k] / 2;
            }

            // 伝播が終わったので、自ノードの遅延配列を空にする
            lazy[k] = 0;
        }
    }

    void add(int a, int b, ll x, int k = 0, int l = 0, int r = -1) {
        if (r < 0)
            r = n;

        // k 番目のノードに対して遅延評価を行う
        eval(k, l, r);

        // 範囲外なら何もしない
        if (b <= l || r <= a)
            return;

        // 完全に被覆しているならば、遅延配列に値を入れた後に評価
        if (a <= l && r <= b) {
            lazy[k] += (r - l) * x;
            eval(k, l, r);
        }

        // そうでないならば、子ノードの値を再帰的に計算して、
        // 計算済みの値をもらってくる
        else {
            add(a, b, x, 2 * k + 1, l, (l + r) / 2);
            add(a, b, x, 2 * k + 2, (l + r) / 2, r);
            node[k] = node[2 * k + 1] + node[2 * k + 2];
        }
    }

    ll getsum(int a, int b, int k = 0, int l = 0, int r = -1) {
        if (r < 0)
            r = n;
        if (b <= l || r <= a)
            return 0;

        // 関数が呼び出されたら評価！
        eval(k, l, r);
        if (a <= l && r <= b)
            return node[k];
        ll vl = getsum(a, b, 2 * k + 1, l, (l + r) / 2);
        ll vr = getsum(a, b, 2 * k + 2, (l + r) / 2, r);
        return vl + vr;
    }
};

LazySegmentTree seg(vl(MAX_N,0));

void HL_add(ll v, ll x) {
    while (v != -1) {
        seg.add(in[nxt[v]], in[v]+1, x);
        v = par[nxt[v]];
    }
}
ll HL_querry(ll v) {;
    ll k = 0;
    while (v != -1) {
        k += seg.getsum(in[nxt[v]], in[v]+1);
        v = par[nxt[v]];
    }
    k-=seg.getsum(0,1);
    return k;
}



int main() {
    cin >> n;
    rep(i, n) {
        cin >> x;
        rep(j, x) {
            cin >> a;
            add(i, a, 0);
            par[a]=i;
        }
    }
    

    HLD();
    
    
    cin >> q;
    rep(i, q) {
        cin >> x;
        if (x == 0) {
        	cin>>a>>b;
            HL_add(a, b);
        }
        else {
            cin >> a;
            cout<<HL_querry(a)<<endl;
        }
    }
}