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 <iostream>
#include <vector>
#include <functional>

using ll = long long;

/* -------------------- Graph -------------------- */

template <class Cost = int>
struct Edge {
    int from, to;
    Cost cost;
    Edge(int from = -1, int to = -1, Cost cost = 1)
        : from(from), to(to), cost(cost){};

    bool operator<(const Edge<Cost>& e) const { return this->cost < e.cost; }
    bool operator>(const Edge<Cost>& e) const { return this->cost > e.cost; }
};

template <class Cost = int>
using Edges = std::vector<Edge<Cost>>;

template <class Cost = int>
class Graph {
public:
    int size;
    std::vector<std::vector<Edge<Cost>>> path;

    explicit Graph(int N = 0) : size(N), path(size) {}
    void span(int from, int to, Cost cost = 1) {
        path[from].push_back(Edge<Cost>(from, to, cost));
    }
    std::vector<Edge<Cost>>& operator[](int v) { return path[v]; }
};

/* -------------------- Lazy-Propagation SegmentTree -------------------- */

template <class Data, class Operator>
class LazySegmentTree {
    using DataMerger = std::function<Data(Data, Data)>;
    using OperatorMerger = std::function<Operator(Operator, Operator)>;
    using Applier = std::function<Data(Data, Operator, int)>;

private:
    int length;
    std::vector<Data> dat;
    std::vector<Operator> ope;
    Data dat_id;            // データの単位元
    Operator ope_id;        // 作用素の単位元
    DataMerger dmerge;      // データをマージする関数
    OperatorMerger omerge;  // 作用素をマージする関数
    Applier app;            // データに作用素を適用する関数 第三引数に区間長を取る

    void eval(int nidx, int len) {
        if (ope[nidx] == ope_id) return;
        // 子に作用素を伝播
        if (nidx * 2 + 1 < length * 2) {
            ope[nidx * 2] = omerge(ope[nidx * 2], ope[nidx]);
            ope[nidx * 2 + 1] = omerge(ope[nidx * 2 + 1], ope[nidx]);
        }
        // 値に作用素を反映
        dat[nidx] = app(dat[nidx], ope[nidx], len);
        ope[nidx] = ope_id;
    }

    Data update(int ql, int qr, Operator e, int nidx, int nl, int nr) {
        eval(nidx, nr - nl);
        if (nr <= ql || qr <= nl) return dat[nidx];
        if (ql <= nl && nr <= qr) {
            ope[nidx] = omerge(ope[nidx], e);
            return app(dat[nidx], ope[nidx], nr - nl);
        }
        // 子を再帰的に更新
        Data vl = update(ql, qr, e, nidx * 2, nl, (nl + nr) / 2);
        Data vr = update(ql, qr, e, nidx * 2 + 1, (nl + nr) / 2, nr);
        // 子の更新後から値を更新
        return dat[nidx] = dmerge(vl, vr);
    }

    Data query(int ql, int qr, int nidx, int nl, int nr) {
        eval(nidx, nr - nl);
        if (nr <= ql || qr <= nl) return dat_id;
        if (ql <= nl && nr <= qr) return dat[nidx];
        Data vl = query(ql, qr, nidx * 2, nl, (nl + nr) / 2);
        Data vr = query(ql, qr, nidx * 2 + 1, (nl + nr) / 2, nr);
        return dmerge(vl, vr);
    }

public:
    // 長さ, 値と作用素の単位元, 値同士, 作用素同士をマージさせる関数, 作用素を値に適用する関数
    explicit LazySegmentTree(int N, Data dat_id, Operator ope_id, DataMerger dmerge, OperatorMerger omerge, Applier app)
        : length(1), dat_id(dat_id), ope_id(ope_id), dmerge(dmerge), omerge(omerge), app(app) {
        while (length < N) length *= 2;
        dat.assign(length * 2, dat_id);
        ope.assign(length * 2, ope_id);
    }

    // half-open interval [ql, qr)
    Data update(int ql, int qr, Operator e) { return update(ql, qr, e, 1, 0, length); }

    // half-open interval [ql, qr)
    Data query(int ql, int qr) { return query(ql, qr, 1, 0, length); }
};

/* -------------------- Heavy-Light Decomposition -------------------- */

template <class Cost = int>
class HeavyLightDecomposition {
private:
    Graph<Cost> graph;
    std::vector<int>
        size,       // 部分木の頂点数
        in, rev,    // 行きがけ順と復元
        par, head;  // 1つ上とパスの根の頂点
    int time;       // inを埋めるのに使う

    // par, sizeを埋める
    int sz_dfs(int v, int r) {
        par[v] = r;
        size[v] = 1;

        // 先頭が親だと不便なので末尾と交換
        if (!graph[v].empty() && graph[v].front().to == r) {
            std::swap(graph[v].front(), graph[v].back());
        }

        for (auto& e : graph[v]) {
            if (e.to == r) continue;
            size[v] += sz_dfs(e.to, v);
            // graph[v]の先頭に一番sizeが大きい子が来るようにする
            if (size[graph[v][0].to] < size[e.to]) std::swap(graph[v][0], e);
        }
        return size[v];
    }

    // in, rev, headを埋める
    void in_dfs(int v, int r) {
        in[v] = time++;
        rev[in[v]] = v;

        for (auto& e : graph[v]) {
            if (e.to == r) continue;
            // 先にgraph[v]の先頭に一番sizeが大きい子が来るようにした
            // よって先頭の子をvのパスに加える
            head[e.to] = (graph[v][0].to == e.to ? head[v] : e.to);
            in_dfs(e.to, v);
        }
    }

public:
    HeavyLightDecomposition(const Graph<Cost>& g, int root)
        : graph(g), size(g.size), in(g.size), rev(g.size), par(g.size), head(g.size) {
        sz_dfs(root, -1);
        time = 0;
        in_dfs(root, -1);
    }

    int lca(int u, int v) {
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) break;
            v = par[head[v]];
        }
        // u, vは同じパス上にある
        // in[u] <= in[v]よりuはvより上にあるため、uがLCAとなる
        return u;
    }

    template <class Data>
    using Query = std::function<Data(int, int)>;
    template <class Data>
    using Merger = std::function<Data(Data, Data)>;
    template <class Data>
    // Dataの単位元, 飛ばしたい区間クエリ, クエリの結果をマージする関数, 辺に対する操作か否か
    Data query(int u, int v, const Data& id, const Query<Data>& qry, const Merger<Data>& merge, bool edge = false) {
        Data l = id, r = id;
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) break;
            l = merge(qry(in[head[v]], in[v] + 1), l);  // [head[v], in[v]]にクエリを飛ばす
            v = par[head[v]];
        }
        return merge(merge(qry(in[u] + edge, in[v] + 1), l), r);
        // [u, v]にクエリを飛ばし、l, rを結合
    }

    using Operation = std::function<void(int, int)>;
    // 区間に大して施したい操作, 辺に対する操作か否か
    void update(int u, int v, const Operation& ope, bool edge = false) {
        while (true) {
            if (in[u] > in[v]) std::swap(u, v);
            if (head[u] == head[v]) break;
            ope(in[head[v]], in[v] + 1);  // [head[v], in[v]]に適用
            v = par[head[v]];
        }
        ope(in[u] + edge, in[v] + 1);  // [u, v]に適用
    }
};


int main() {
    int N;
    std::cin >> N;
    Graph<> tree(N);
    for (int v = 0; v < N; ++v) {
        int k;
        std::cin >> k;
        for (int i = 0; i < k; ++i) {
            int c;
            std::cin >> c;
            tree.span(v, c);
        }
    }

    HeavyLightDecomposition<> hld(tree, 0);
    LazySegmentTree<ll, ll> seg(N, 0, 0,
                                [](ll a, ll b) { return a + b; },
                                [](ll e, ll f) { return e + f; },
                                [](ll a, ll e, int k) { return a + e * k; });

    int Q;
    std::cin >> Q;
    for (int q = 0; q < Q; ++q) {
        int t;
        std::cin >> t;
        if (t == 0) {
            int v, w;
            std::cin >> v >> w;

            hld.update(0, v, [&](int l, int r) { seg.update(l, r, w); }, true);
        } else {
            int v;
            std::cin >> v;
            ll ans = hld.query<ll>(0, v, 0,
                                   [&](int l, int r) { return seg.query(l, r); },  // クエリ
                                   [](ll a, ll b) { return a + b; },               // クエリの結果をマージ
                                   true);                                          // 辺に対する操作
            std::cout << ans << std::endl;
        }
    }
    return 0;
}