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>
#include <cmath>

using namespace std;
typedef long long ll;
//typedef unsigned long long ll;

#define rep(i, n) for (int i = 0; i < (n); ++i)
//#define rep(i, n) for (ll i = 0; i < (n); ++i)
//#define sz(x) ll(x.size())
//typedef pair<ll, int> P;
typedef pair<ll, ll> P;
//const double INF = 1e10;
const ll INF = LONG_LONG_MAX / 100;
//const ll INF = (1ll << 31) - 1;
//const ll INF = 1e15;
const ll MINF = LONG_LONG_MIN;
//const int INF = INT_MAX / 10;
#define cmin(x, y) x = min(x, y)
#define cmax(x, y) x = max(x, y)
//typedef pair<int, int> P;
//typedef pair<double, double> P;

bool contain(set<P> &s, P a) { return s.find(a) != s.end(); }

//ifstream myfile("C:\\Users\\riku\\Downloads\\0_00.txt");
//ofstream outfile("log.txt");
//outfile << setw(6) << setfill('0') << prefecture << setw(6) << setfill('0') << rank << endl;
// std::cout << std::bitset<8>(9);
const int mod = 1000000007;
typedef priority_queue<long long, vector<long long>, greater<long long>> PQ_ASK;


void print_line(vector<string> &line) {
    if (line.size() == 0ll) {
        cout << endl;
        return;
    }
    for (ll i = 0; i < line.size(); i++) {
        cout << line[i];
        if (i == line.size() - 1) cout << endl;
        else cout << ' ';
    }
}


// 何もわからん。写経
// https://onlinejudge.u-aizu.ac.jp/solutions/problem/GRL_5_E/review/2929438/ei1333/C++14
template<typename data_t, typename lazy_t>
struct LCNode {
    using LP = LCNode *;

    LP l, r, p;
    int idx, sz;
    bool rev;
    data_t key, sum;
    lazy_t lazy;

    void init_node(int idx, const data_t &v) {
        this->sz = 1;
        this->idx = idx;
        this->lazy = 0;
        this->key = this->sum = v;
    }

    void update() {
        sz = 1;
        sum = key;
        if (l) sz += l->sz, sum = l->sum + sum;
        if (r) sz += r->sz, sum = sum + r->sum;
    }

    void propagate(const lazy_t &v) {
        lazy += v;
        key += v;
        sum += v * sz;
    }

    void toggle() {
        swap(l, r);
        rev ^= true;
    }

    bool is_root() {
        return !p || (p->l != this && p->r != this);
    }

    void push() {
        if (lazy) {
            if (l) l->propagate(lazy);
            if (r) r->propagate(lazy);
            lazy = 0;
        }
        if (rev) {
            if (l) l->toggle();
            if (r) r->toggle();
            rev = false;
        }
    }

    void rotr() {
        LP x = p, y = x->p;
        if ((x->l = r)) r->p = x;
        r = x, x->p = this;
        x->update(), update();
        if ((p = y)) {
            if (y->l == x) y->l = this;
            if (y->r == x) y->r = this;
            y->update();
        }
    }

    void rotl() {
        LP x = p, y = x->p;
        if ((x->r = l)) l->p = x;
        l = x, x->p = this;
        x->update(), update();
        if ((p = y)) {
            if (y->l == x) y->l = this;
            if (y->r == x) y->r = this;
            y->update();
        }
    }

    void splay() {
        push();
        while (!is_root()) {
            LP q = p;
            if (q->is_root()) {
                q->push(), push();
                if (q->l == this) rotr();
                else rotl();
            } else {
                LP r = q->p;
                r->push(), q->push(), push();
                if (r->l == q) {
                    if (q->l == this) q->rotr(), rotr();
                    else rotl(), rotr();
                } else {
                    if (q->r == this) q->rotl(), rotl();
                    else rotr(), rotl();
                }
            }
        }
    }

    LP expose() {
        LP rp = nullptr;
        for (LP cur = this; cur; cur = cur->p) {
            cur->splay();
            cur->r = rp;
            cur->update();
            rp = cur;
        }
        splay();
        return rp;
    }

    void link(LP parent) {
        expose();
        parent->expose();
        p = parent;
        parent->r = this;
    }

    void cut() {
        expose();
        LP parent = l;
        l = nullptr;
        parent->p = nullptr;
    }

    void evert() {
        expose();
        toggle();
        push();
    }

    LP lca(LP v) {
        expose();
        return v->expose();
    }

    void set_propagate(const lazy_t &x) {
        expose();
        propagate(x);
        push();
    }
};

using int64 = long long;

int main() {
    int N;
    scanf("%d", &N);
    auto f = [&](int64 x, int64 y) { return x + y; };
    auto g = [&](int64 x, int64 y, int64 z) { return x + y * z; };
    using LCTree = LCNode<int64, int64>;
    vector<LCTree *> uku(N);
    for (int i = 0; i < N; i++) {
        uku[i] = new LCTree();
        uku[i]->init_node(i, 0);
    }
    for (int i = 0; i < N; i++) {
        int K;
        scanf("%d", &K);
        while (K--) {
            int T;
            scanf("%d", &T);
            uku[T]->link(uku[i]);
        }
    }
    int Q;
    scanf("%d", &Q);
    int64 all = 0;
    while (Q--) {
        int T;
        scanf("%d", &T);
        if (T == 0) {
            int V, W;
            scanf("%d %d", &V, &W);
            uku[V]->set_propagate(W);
            all += W;
        } else {
            int U;
            scanf("%d", &U);
            uku[U]->expose();
            printf("%lld\n", uku[U]->sum - all);
        }
    }
}