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

#define REP(i,n) for (int i=0;i<(n);++i)

struct edge {
    typedef size_t weight_type;

    size_t m_to;

    edge(size_t to) : m_to(to) { }

    inline size_t to() const { return m_to; }

    inline weight_type weight() const { return 1; }

    friend std::ostream& operator<<(std::ostream &os, const edge &e) {
        os << "{ to: " << e.m_to << " }";
        return os;
    }
};

template <typename Weight>
struct weighted_edge : public edge {
    typedef Weight weight_type;

    weight_type m_weight;

    weighted_edge(size_t to, weight_type weight) : edge(to), m_weight(weight) { }

    inline weight_type weight() const { return m_weight; }

    friend std::ostream& operator<<(std::ostream &os, const weighted_edge &e) {
        os << "{ to: " << e.m_to << ", weight = " << e.m_weight << " }";
        return os;
    }
};

template <class Edge>
struct graph {
    typedef Edge edge_type;

    size_t m_n_vertices;
    std::vector<std::vector<edge_type>> m_edges;

    graph(size_t n_vertices) : m_n_vertices(n_vertices), m_edges(n_vertices) { }

    inline size_t n_vertices() const { return m_n_vertices; }

    inline void make_edge(size_t from, size_t to, typename edge_type::weight_type weight) {
        m_edges[from].emplace_back(edge_type(to, weight));
    }

    inline void make_edge(size_t from, size_t to) {
        m_edges[from].emplace_back(edge(to));
    }

    inline void make_edge(size_t from, const edge_type &e) {
        m_edges[from].emplace_back(e);
    }

    inline std::vector<edge_type> edges_from(size_t v) const {
        return m_edges[v];
    }
};

template<class T>
class fenwick_tree {
private:
    const size_t size;
    const std::function<T(T, T)> f;
    const T unit;
    std::vector<T> a;
public:
    fenwick_tree(size_t size, std::function<T(T, T)> f, T unit) : size(size), f(f), unit(unit), a(size, unit) { }

    void update(size_t i, T x) {
        for (size_t j = i; j < size; j |= j + 1) {
            a[j] = f(a[j], x);
        }
    }

    T query(size_t i) const {
        T result = unit;
        for (size_t j = i; j > 0; j = (j & (j + 1))) {
            result = f(result, a[--j]);
        }
        return result;
    }
};

template <class T>
class range_add_sum_query {
private:
    fenwick_tree<T> fenwick_1;
    fenwick_tree<T> fenwick_2;
public:
    range_add_sum_query(size_t n) : fenwick_1(n + 1, [](T x, T y) { return x + y; }, 0),
                                    fenwick_2(n + 1, [](T x, T y) { return x + y; }, 0) { }

    void update(size_t first, size_t last, T x) {
        fenwick_1.update(first, x);
        fenwick_1.update(last, -x);
        fenwick_2.update(first, first * x);
        fenwick_2.update(last, -last * x);
    }

    T query(size_t last) const {
        return fenwick_1.query(last) * last - fenwick_2.query(last);
    }

    T query(size_t first, size_t last) const {
        return query(last) - query(first);
    }
};

template <class Graph, class RangeQuery>
struct heavy_light_decomposition {
    using Edge = typename Graph::edge_type;
    using Weight = typename Edge::weight_type;

    size_t n_vertices;
    size_t m_root;
    std::vector<size_t> branch_vertices;
    std::vector<size_t> pos;
    std::vector<size_t> pos_end;
    std::vector<size_t> depth;
    RangeQuery range_query;
    const size_t NIL;

    heavy_light_decomposition(const Graph &g, size_t root) : n_vertices(g.n_vertices()), m_root(root), range_query(n_vertices), NIL(n_vertices) {
        std::vector<size_t> sizes(n_vertices);
        std::vector<size_t> heavy_children(n_vertices);
        branch_vertices.resize(n_vertices);
        pos.resize(n_vertices);
        pos_end.resize(n_vertices);
        depth.resize(n_vertices);

        std::function<size_t(size_t, size_t)> dfs = [&](size_t v, size_t parent) {
            sizes[v] = 1;
            heavy_children[v] = NIL;
            size_t child_size_max = 0;
            for (const Edge &e: g.edges_from(v)) {
                size_t child = e.to();
                if (child == parent) {
                    continue;
                }
                dfs(child, v);
                sizes[v] += sizes[child];
                if (child_size_max < sizes[child]) {
                    child_size_max = sizes[child];
                    heavy_children[v] = child;
                }
            }
            return sizes[v];
        };

        dfs(root, NIL);

        size_t cur_pos = n_vertices;

        std::function<void(size_t, size_t, size_t, size_t)> decompose = [&](size_t v, size_t parent, size_t bv, size_t ep) {
            branch_vertices[v] = bv;
            pos[v] = --cur_pos;
            pos_end[v] = ep;
            if (heavy_children[v] != NIL) {
                decompose(heavy_children[v], v, bv, ep);
            }
            for (const Edge &e: g.edges_from(v)) {
                size_t child = e.to();
                if (child != parent && child != heavy_children[v]) {
                    decompose(child, v, v, cur_pos);
                }
            }
        };

        decompose(root, n_vertices, n_vertices, n_vertices - 1);
    }

    void update(size_t v, Weight w) {
        do {
            range_query.update(pos[v], pos_end[v], w);
        } while ((v = branch_vertices[v]) != NIL);
    }

    Weight query(size_t v) {
        Weight result = 0;
        do {
            result += range_query.query(pos[v], pos_end[v]);
        } while ((v = branch_vertices[v]) != NIL);
        return result;
    }
};

int main() {
    using namespace std;

    cin.tie(0);
    ios::sync_with_stdio(false);

    using Graph = graph<edge>;

    int n;
    cin >> n;
    Graph g(n);
    REP(v, n) {
        int k;
        cin >> k;
        REP(_, k) {
            int c;
            cin >> c;
            g.make_edge(v, c);
        }
    }

    heavy_light_decomposition<Graph, range_add_sum_query<long long>> hld(g, 0);

    int q;
    cin >> q;
    REP(_, q) {
        int query_type;
        cin >> query_type;
        if (query_type == 0) {
            int v, w;
            cin >> v >> w;
            hld.update(v, w);
        } else {// if (query_type == 1) {
            int u;
            cin >> u;
            cout << hld.query(u) << endl;
        }
    }

    return 0;
}