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
#define endl '\n'
#define maxn 100010

vector<pair<int, int>> g[maxn];
vector<vector<int>> up;
int tout[maxn], tin[maxn], sz[maxn];
int timer = 0, L;

int chainNo, base[maxn], head[maxn], pos, chainId[maxn];
int tree[4 * maxn], lazy[4 *maxn];

int doit(int a, int b) {
    return a + b;
}

void divide(int index, int l, int r) {
    tree[index] += (r - l + 1) *lazy[index];
    if (l != r) {
        lazy[2 * index] += lazy[index];
        lazy[2 * index + 1] += lazy[index];
    }
    lazy[index] = 0;
}

int queryTree(int start, int end, int l, int r, int index = 1) {
    if (lazy[index] != 0) {
        divide(index, start, end);
    }

    if (r < start or l > end)
        return 0;

    if (l <= start and r >= end){
        return tree[index];
    }

    int mid = start + end >> 1;
    return doit(queryTree(start, mid, l, r, 2 * index), queryTree(mid + 1, end, l, r, 2 * index + 1));
}

void update(int start, int end, int l, int r, int value, int index) {
    if (lazy[index] != 0) {
        divide(index, start, end);
    }

    if (r < start or l > end)
        return;

    if (l <= start and r >= end) {
        lazy[index] += value;
        divide(index, start, end);
        return;
    }

    int mid = start + end >> 1;
    update(start, mid, l, r, value, 2 * index);
    update(mid + 1, end, l, r, value, 2 * index + 1);
    tree[index] = doit(tree[2 * index], tree[2 * index + 1]);
}

void dfs(int u, int p) {
    tin[u] = ++timer;
    up[u][0] = p;
    sz[u] = 1;
    for (int i = 1; i <= L; i++)
        up[u][i] = up[up[u][i - 1]][i - 1];

    for (auto &x: g[u]) {
        if (x.first == p)continue;
        dfs(x.first, u);
        sz[u] += sz[x.first];
    }
    tout[u] = ++timer;
}

bool isAncestor(int u, int v) {
    return tin[u] <= tin[v] and tout[u] >= tout[v];
}

int lca(int u, int v) {
    if (isAncestor(u, v))
        return u;
    if (isAncestor(u, v))
        return v;
    for (int i = L; i >= 0; i--) {
        if (!isAncestor(up[u][i], v))
            u = up[u][i];
    }
    return up[u][0];
}

void hld(int u, int cost, int p) {
    if (head[chainNo] == 0)
        head[chainNo] = u;

    chainId[u] = chainNo;
    base[u] = pos++;

    int bg = -1, sizz = 0;
    for (auto x: g[u]) {
        if (x.first == p)continue;
        if (bg == -1 or sizz < sz[x.first])
            bg = x.first, cost = x.second, sizz = sz[x.first];
    }

    if (bg != -1)
        hld(bg, cost, u);

    for (auto x: g[u]) {
        if (x.first == p or x.first == bg)continue;
        chainNo++;
        hld(x.first, x.second, u);
    }
}

void preprocess() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; ++i) {
        int k;
        cin >> k;

        for (int j = 0; j < k; j++) {
            int a;
            cin >> a;
            a++;

            g[i].push_back({a, 0});
            g[a].push_back({i, 0});
        }
    }

    L = ceil(log2(n));
    up.assign(n + 1, vector<int>(L + 1));
    dfs(1, 1);
    hld(1, 0, 1);
}

int query_up(int a, int b) {
    if (a == b)
        return 0;

    int uchain, vchain = chainId[b], ans = 0;
    while (true) {
        uchain = chainId[a];
        if (uchain == vchain) {
            if (a == b)break;
            ans += queryTree(0, pos - 1, base[b] + 1, base[a], 1);
            break;
        }
        ans += queryTree(0, pos - 1, base[head[uchain]], base[a], 1);
        a = up[head[uchain]][0];
    }
    return ans;
}

int query(int a, int b) {
    int LCA = lca(a, b);
    return query_up(a, LCA) + query_up(b, LCA);
}

void update(int a, int w, int b = 1) {
    if (a == b)
        return;

    int uchain, vchain = chainId[b];
    while (true) {
        uchain = chainId[a];
        if (uchain == vchain) {
            if (a == b)break;
            update(0, pos - 1, base[b] + 1, base[a], w, 1);
            break;
        }
        update(0, pos - 1, base[head[uchain]], base[a], w, 1);
        a = up[head[uchain]][0];
    }
}

void solve() {
    preprocess();
    int q;
    cin >> q;

    for (int i = 0; i < q; i++) {
        int type;
        cin >> type;

        if (type == 0) {
            int p, c;
            cin >> p >> c;

            p++;
            update(p, c);
        } else {
            int u;
            cin >> u;
            u++;

            cout << query(u, 1) << endl;
        }
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    int t = 1;
//    cin >> t;

    while (t--)
        solve();
    return 0;
}