Problem: Write a program which manipulates a weighted rooted tree $T$ with the following operations:

* $add(v,w)$: add $w$ to the edge which connects node $v$ and its parent

* $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
10
60


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

1000
2000
3000


Input

2
1 1
0
4
0 1 1
1 1
0 1 1
1 1


Output

1
2

Solution (in CPP):

Solution:
#include <algorithm>
#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 <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];
    }
};

unsigned long long clp(unsigned long long x) {
    x -= 1;
    x = x | (x >>  1);
    x = x | (x >>  2);
    x = x | (x >>  4);
    x = x | (x >>  8);
    x = x | (x >> 16);
    x = x | (x >> 32);
    return x + 1;
}

template <class T>
class segment_tree {
private:
    const size_t n;
    const T UNIT;
    const std::function<T(const T&, const T&)> f;
    T *a;
public:
    segment_tree(size_t size, T UNIT, std::function<T(const T&, const T&)> f) : n(clp(size)), UNIT(UNIT), f(f) {
        a = new T[2 * n - 1];
        std::fill(a, a + 2 * n - 1, UNIT);
    }
    ~segment_tree() {
        delete [] a;
    }
    void update(size_t i, const T &x) {
        i += n - 1;
        a[i] += x;
        while (i) {
            i = (i - 1) / 2;
            a[i] = f(a[2 * i + 1], a[2 * i + 2]);
        }
    }
    T query(size_t query_first, size_t query_last, size_t k = 0, size_t node_first = 0, size_t node_last = 0) const {
        if (k == 0) {
            node_last = n;
        }
        if (node_last <= query_first || query_last <= node_first) {
            return UNIT;
        }
        if (query_first <= node_first && node_last <= query_last) {
            return a[k];
        } else {
            size_t node_mid = (node_first + node_last) / 2;
            T vl = query(query_first, query_last, k * 2 + 1, node_first, node_mid);
            T vr = query(query_first, query_last, k * 2 + 2, node_mid, node_last);
            return f(vl, vr);
        }
    }
};

template <class Graph>
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;
    segment_tree<Weight> seg_tree;
    const size_t NIL;

    heavy_light_decomposition(const Graph &g, size_t root) : n_vertices(g.n_vertices()), m_root(root) , seg_tree(n_vertices, 0, [](Weight x, Weight y) { return x + y; }), 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);
    }

    void update(size_t v, Weight w) {
        seg_tree.update(pos[v], w);
    }

    Weight query(size_t v) {
        Weight result = 0;
        do {
            result += seg_tree.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> 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;
}