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 <bits/stdc++.h>
using namespace std;

using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>;
using ll = long long int;
using vll = vector<ll>; using vvll = vector<vll>; using vvvll = vector<vvll>;
using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>;
using P = pair<int, int>;
using Pll = pair<ll, ll>;
using cdouble = complex<double>;

const double eps = 1e-7;
#define Loop(i, n) for(int i = 0; i < int(n); i++)
#define Loopll(i, n) for(ll i = 0; i < ll(n); i++)
#define Loop1(i, n) for(int i = 1; i <= int(n); i++)
#define Loopll1(i, n) for(ll i = 1; i <= ll(n); i++)
#define Loopr(i, n) for(int i = int(n) - 1; i >= 0; i--)
#define Looprll(i, n) for(ll i = ll(n) - 1; i >= 0; i--)
#define Loopr1(i, n) for(int i = int(n); i >= 1; i--)
#define Looprll1(i, n) for(ll i = ll(n); i >= 1; i--)
#define Foreach(buf, container) for(const auto &buf : container)
template<class T> T reversed(T container) { reverse(container.begin(), container.end()); return container; }
#define Foreachr(buf, container)  for(const auto &buf : reversed(container))
#define Loopdiag(i, j, h, w, sum) for(int i = ((sum) >= (h) ? (h) - 1 : (sum)), j = (sum) - i; i >= 0 && j < (w); i--, j++)
#define Loopdiagr(i, j, h, w, sum) for(int j = ((sum) >= (w) ? (w) - 1 : (sum)), i = (sum) - j; j >= 0 && i < (h); j--, i++)
#define Loopdiagsym(i, j, h, w, gap) for (int i = ((gap) >= 0 ? (gap) : 0), j = i - (gap); i < (h) && j < (w); i++, j++)
#define Loopdiagsymr(i, j, h, w, gap) for (int i = ((gap) > (h) - (w) - 1 ? (h) - 1 : (w) - 1 + (gap)), j = i - (gap); i >= 0 && j >= 0; i--, j--)
#define Loopitr(itr, container) for(auto itr = container.begin(); itr != container.end(); itr++)
#define printv(vector) Loop(ex_i, vector.size()) { cout << vector[ex_i] << " "; } cout << endl;
#define printmx(matrix) Loop(ex_i, matrix.size()) { Loop(ex_j, matrix[ex_i].size()) { cout << matrix[ex_i][ex_j] << " "; } cout << endl; }
#define quickio() ios::sync_with_stdio(false); cin.tie(0);
#define bitmanip(m,val) static_cast<bitset<(int)m>>(val)
#define Comp(type_t) bool operator<(const type_t &another) const
#define fst first
#define snd second
#define INF INFINITY
bool feq(double x, double y) { return abs(x - y) <= eps; }
bool inrange(ll x, ll t) { return x >= 0 && x < t; }
bool inrange(vll xs, ll t) { Foreach(x, xs) if (!(x >= 0 && x < t)) return false; return true; }
int ceillog2(ll x) { return int(ceil(log2(x))); }
int floorlog2(ll x) { return int(floor(log2(x))); }
ll rndf(double x) { return (ll)(x + (x >= 0 ? 0.5 : -0.5)); }
ll floorsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (m * m <= x ? 0 : -1); }
ll ceilsqrt(ll x) { ll m = (ll)sqrt((double)x); return m + (x <= m * m ? 0 : 1); }
ll rnddiv(ll a, ll b) { return (a / b + (a % b * 2 >= b ? 1 : 0)); }
ll ceildiv(ll a, ll b) { return (a / b + (a % b == 0 ? 0 : 1)); }
ll gcd(ll m, ll n) { if (n == 0) return m; else return gcd(n, m % n); }
ll lcm(ll m, ll n) { return m * n / gcd(m, n); }

//========================================================================//

struct tree_t {
	using nodeval_t = int;
	using edgeval_t = int;
	int n;           // |V|, index begins with 0
	vector<P> edges; // E
	vector<nodeval_t> vals; // value of nodes
	vector<edgeval_t> costs; // cost, distance, or weight of edges
};


// a should be sorted, return will be the root
template<class val_t, class tree_t>
int make_treap(const vector<val_t> &a, const tree_t &T, int l = 0, int r = -1, int p = -1) {
	if (r == -1) { r = a.size(); T.n = a.size(); }
	if (r - l == 0) return -1;
	int mid = (l + r) / 2;
	if (p != -1) T.edges.push_back({ mid, p });
	make_treap(a, T, l, mid, mid);
	make_treap(a, T, mid + 1, r, mid);
	return mid;
}

#define ANCESTOR
#define HLD
class Tree {
	using nodeval_t = int;
	using edgeval_t = int;
private:
	struct node {
		vi childs; int parent = -1;
		int deg = -1; // the number of edges of the path to the root
		int eid = -1; // edge id of the edge connected by its parent and itself
		int subtree_n = 1; // the number of nodes of the partial tree rooted by itself
#ifdef ANCESTOR
		int visited = -1; // time stamp of visiting on DFS, call solve_sprs_ancestors() for activation
		int departed = -1; // time stamp of departure on DFS, call solve_sprs_ancestors() for activation
#endif
#ifdef HLD
		int pid = -1; // path id of heavy light decompotion
		int qid = -1; // id in its path
#endif
		nodeval_t val; // value of the node itself
		edgeval_t cost; // cost of the edge connected by its parent and itself
	};
	struct edgeinfo_t {
		int eid; int to; edgeval_t cost;
	};
	int n;
	static const nodeval_t init_val = 0;
	static const edgeval_t init_cost = 1;
#ifdef ANCESTOR
	vvi sprs_ancestors; // (1 << j)-th ancestors in each node_id = i
#endif
#ifdef HLD
	vvi hld_paths; // paths
#endif
	void tree_construction(const vector<vector<edgeinfo_t>> &edges) {
		leaves = {};
		queue<int> que;
		que.push(root);
		while (que.size()) {
			int a = que.front(); que.pop();
			deg_order.push_back(a);
			if (a == Tree::root) nodes[a].deg = 0;
			int leaf_flag = true;
			Loop(i, edges[a].size()) {
				int b = edges[a][i].to;
				if (nodes[b].deg != -1) {
					nodes[a].parent = b;
					nodes[a].eid = edges[a][i].eid;
					nodes[a].cost = edges[a][i].cost;
					nodes[a].deg = nodes[b].deg + 1;
				}
				else {
					leaf_flag = false;
					nodes[a].childs.push_back(b);
					que.push(b);
				}
			}
			if (leaf_flag) leaves.push_back(a);
		}
		Loopr(i, n) {
			int a = deg_order[i];
			Loop(j, nodes[a].childs.size()) {
				int b = nodes[a].childs[j];
				nodes[a].subtree_n += nodes[b].subtree_n;
			}
		}
	}
public:
	vector<node> nodes;
	vi deg_order; // node ids, sorted by deg
	vi leaves;
	int root;
public:
	// T should be non-empty tree
	Tree(const tree_t &T, int root) {
		this->n = T.n;
		this->root = root;
		nodes.resize(n);
		Loop(i, n) {
			nodes[i].val = (int)(T.vals.size()) > i ? T.vals[i] : init_val;
			nodes[i].cost = init_cost;
		}
		vector<vector<edgeinfo_t>> edges(n);
		Loop(i, n - 1) {
			edges[T.edges[i].fst].push_back({ i, T.edges[i].snd, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
			edges[T.edges[i].snd].push_back({ i, T.edges[i].fst, ((int)(T.costs.size()) > i ? T.costs[i] : init_cost) });
		}
		tree_construction(edges);
		return;
	}
	int solve_diameter() {
		vi d(n, -1);
		queue<int> que;
		d[deg_order[n - 1]] = 0;
		que.push(deg_order[n - 1]);
		while (que.size()) {
			int a = que.front(); que.pop();
			int p = nodes[a].parent;
			if (d[p] == -1) {
				d[p] = d[a] + 1;
				que.push(nodes[a].parent);
			}
			Foreach(b, nodes[a].childs) {
				if (d[b] == -1) {
					d[b] = d[a] + 1;
					que.push(b);
				}
			}
		}
		return *max_element(d.begin(), d.end());
	}
	pair<int, vi> solve_center_of_gravity() {
		pair<int, vi> ret = { INT_MAX,{} };
		vi record(n, 1);
		Foreach(a, deg_order) {
			int x = n - 1, max_x = INT_MIN;
			Foreach(b, nodes[a].childs) {
				max_x = max(max_x, record[b]);
				x -= record[b];
				record[a] += record[b];
			}
			max_x = max(max_x, x);
			if (max_x < ret.fst) ret = { max_x,{ a } };
			else if (max_x == ret.fst) ret.snd.push_back(a);
		}
		sort(ret.snd.begin(), ret.snd.end());
		return ret;
	}
	vi solve_node_inclusion_cnt_in_all_path(bool enable_single_node_path) {
		vi ret(n, 0);
		Loop(i, n) {
			int a = i;
			// desendants to desendants
			Foreach(b, nodes[a].childs) {
				ret[i] += nodes[b].subtree_n * (nodes[a].subtree_n - nodes[b].subtree_n - 1);
			}
			ret[i] /= 2; // because of double counting
			ret[i] += (nodes[a].subtree_n - 1) * (n - nodes[a].subtree_n); // desendants to the others except for itself
			ret[i] += n - 1; // itself to the others
			if (enable_single_node_path) ret[i]++; // itself
		}
		return ret;
	}
	vi solve_edge_inclusion_cnt_in_all_path() {
		vi ret(n - 1, 0);
		Loop(i, n) {
			int eid = nodes[i].eid;
			if (eid < 0) continue;
			ret[eid] = nodes[i].subtree_n * (n - nodes[i].subtree_n); // members in the partial tree to the others
		}
		return ret;
	}
#ifdef ANCESTOR
	void solve_sprs_ancestors() {
		sprs_ancestors.resize(n);
		vector<int> current_ancestors;
		stack<int> stk;
		stk.push(Tree::root);
		int time_stamp = 0;
		while (stk.size()) {
			int a = stk.top(); stk.pop();
			nodes[a].visited = time_stamp++;
			for (int i = 1; i <= (int)(current_ancestors.size()); i *= 2) {
				sprs_ancestors[a].push_back(current_ancestors[current_ancestors.size() - i]);
			}
			if (nodes[a].childs.size()) {
				Loop(i, nodes[a].childs.size()) {
					stk.push(nodes[a].childs[i]);
				}
				current_ancestors.push_back(a);
			}
			else {
				nodes[a].departed = time_stamp++;
				while (current_ancestors.size() && (stk.empty() || nodes[stk.top()].parent != current_ancestors.back())) {
					nodes[current_ancestors.back()].departed = time_stamp++;
					current_ancestors.pop_back();
				}
			}
		}
		return;
	}
	bool is_ancestor(int descendant, int ancestor) {
		return nodes[ancestor].visited < nodes[descendant].visited
			&& nodes[descendant].departed < nodes[ancestor].departed;
	}
	int get_lowest_common_ancestor(int u, int v) {
		if (u == v) return u;
		if (is_ancestor(u, v)) return v;
		if (is_ancestor(v, u)) return u;
		int a = u;
		while (!is_ancestor(v, sprs_ancestors[a][0])) {
			int b = sprs_ancestors[a][0];
			Loop1(i, sprs_ancestors[a].size() - 1) {
				if (is_ancestor(v, sprs_ancestors[a][i])) break;
				else b = sprs_ancestors[a][i - 1];
			}
			a = b;
		}
		return sprs_ancestors[a][0];
	}
	int get_ancestor(int descendant, int k) {
		if (k == 0) return descendant;
		int l = (int)log2(k);
		if (l >= sprs_ancestors[descendant].size()) return -1;
		else return get_ancestor(sprs_ancestors[descendant][l], k - (1 << l));
	}
	// return first value causing "t" in evalfunc that returns descendant->[f,...,f,t,...,t]->root
	// NOTE: if [f,...,f] then return -1
	template<typename bsargv_t>
	int binary_search_upper_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
		if (evalfunc(descendant, bsargv)) return descendant;
		if (descendant == root) return -1;
		Loop(i, sprs_ancestors[descendant].size()) {
			if (evalfunc(sprs_ancestors[descendant][i], bsargv)) {
				if (i == 0) return binary_search_upper_ancestor(sprs_ancestors[descendant][0], bsargv, evalfunc);
				else return binary_search_upper_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
			}
		}
		return binary_search_upper_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
	}
	// return last value causing "t" in evalfunc that returns descendant->[t,...,t,f,...,f]->root
	// NOTE: if [f,...,f] then return -1
	template<typename bsargv_t>
	int binary_search_lower_ancestor(int descendant, const bsargv_t &bsargv, bool(*evalfunc)(int, const bsargv_t&)) {
		if (!evalfunc(descendant, bsargv)) return -1;
		if (descendant == root) return root;
		Loop(i, sprs_ancestors[descendant].size()) {
			if (!evalfunc(sprs_ancestors[descendant][i], bsargv)) {
				if (i == 0) return descendant;
				else return binary_search_lower_ancestor(sprs_ancestors[descendant][i - 1], bsargv, evalfunc);
			}
		}
		return binary_search_lower_ancestor(sprs_ancestors[descendant].back(), bsargv, evalfunc);
	}
	// static bool evalfunc(int id, bsargv_t bsargv);
#endif
#ifdef HLD
	void solve_hld() {
		Foreach(a, deg_order) {
			if (nodes[a].pid == -1) {
				nodes[a].pid = int(hld_paths.size());
				nodes[a].qid = 0;
				hld_paths.push_back({ a });
			}
			int max_id = -1;
			int max_subtree_n = 0;
			Foreach(b, nodes[a].childs) {
				if (nodes[b].subtree_n > max_subtree_n) {
					max_id = b;
					max_subtree_n = nodes[b].subtree_n;
				}
			}
			if (max_id == -1) continue;
			nodes[max_id].pid = nodes[a].pid;
			nodes[max_id].qid = nodes[a].qid + 1;
			hld_paths[nodes[a].pid].push_back(max_id);
		}
	}
	struct pathinfo_t {
		int id;
		int l, r; // [l, r)
	};
	// if weight is for each node, include_lca = true
	// if weight is for each edge, include_lca = false
	vector<pathinfo_t> get_path_in_hld(int u, int v, bool include_lca) {
		vector<pathinfo_t> ret;
		int w = get_lowest_common_ancestor(u, v);
		if (include_lca && u == v) {
			ret.push_back({ nodes[w].pid, nodes[w].qid, nodes[w].qid + 1 });
		}
		else {
			Foreach(x, vector<int>({ u, v })) {
				int a = x;
				while (a != w) {
					if (nodes[a].pid != nodes[w].pid) {
						ret.push_back({ nodes[a].pid, 0, nodes[a].qid + 1 });
						a = nodes[hld_paths[nodes[a].pid][0]].parent;
					}
					else {
						ret.push_back({ nodes[a].pid, nodes[w].qid + (include_lca ? 0 : 1), nodes[a].qid + 1 });
						a = w;
					}
				}
			}
		}
		return ret;
	}
	vi get_hldpathsize() {
		vi ret(hld_paths.size());
		Loop(i, hld_paths.size()) {
			ret[i] = int(hld_paths[i].size());
		}
		return ret;
	}
#endif
};

class SegTreeSum {
	using val_t = ll;
private:
	struct segval_t {
		bool enable;
		val_t upd, add, sum;
	};
	int n, N; // n is the original size, while N is the extended size
	int base;
	vector<segval_t> nodes;
	vi idl, idr, cover_size;
	void merge(int id) {
		nodes[id].sum = nodes[idl[id]].sum + nodes[idl[id]].add * cover_size[idl[id]]
			+ nodes[idr[id]].sum + nodes[idr[id]].add * cover_size[idr[id]];
	}
	void lazy(int id) {
		if (id >= base) return;
		if (nodes[id].enable) {
			val_t upd = nodes[id].upd + nodes[id].add;
			nodes[idl[id]] = { true, upd, 0, upd * cover_size[idl[id]] };
			nodes[idr[id]] = { true, upd, 0, upd * cover_size[idr[id]] };
			nodes[id] = { false, 0, 0, upd * cover_size[id] };
		}
		else {
			nodes[idl[id]].add += nodes[id].add;
			nodes[idr[id]].add += nodes[id].add;
			nodes[id].add = 0;
			merge(id);
		}
	}
	enum change_t {
		UPD, ADD
	};
	void change_rec(int s, int t, int l, int r, int id, val_t x, change_t op) {
		if (s == l && t == r) {
			if (op == UPD) nodes[id] = { true, x, 0, x * cover_size[id] };
			if (op == ADD) nodes[id].add += x;
		}
		else {
			lazy(id);
			int m = (l + r) >> 1;
			if (s < m && m < t) {
				change_rec(s, m, l, m, idl[id], x, op);
				change_rec(m, t, m, r, idr[id], x, op);
			}
			else if (s < m) {
				change_rec(s, t, l, m, idl[id], x, op);
			}
			else if (m < t) {
				change_rec(s, t, m, r, idr[id], x, op);
			}
			merge(id);
		}
	}
	val_t solve_rec(int s, int t, int l, int r, int id) {
		val_t v = 0;
		if (s == l && t == r) {
			v = nodes[id].sum;
		}
		else {
			lazy(id);
			int m = (l + r) >> 1;
			if (s < m && m < t) {
				val_t v0 = solve_rec(s, m, l, m, idl[id]);
				val_t v1 = solve_rec(m, t, m, r, idr[id]);
				v = v0 + v1;
			}
			else if (s < m) {
				v = solve_rec(s, t, l, m, idl[id]);
			}
			else if (m < t) {
				v = solve_rec(s, t, m, r, idr[id]);
			}
		}
		v += nodes[id].add * (t - s);
		return v;
	}
	void common_init() {
		idl.resize(base + N, -1);
		idr.resize(base + N, -1);
		Loop(i, base) {
			idl[i] = (i << 1) + 1;
			idr[i] = (i << 1) + 2;
		}
		cover_size.resize(base + N);
		Loop(i, n) {
			cover_size[base + i] = 1;
		}
		Loopr(i, base) {
			cover_size[i] = cover_size[idl[i]] + cover_size[idr[i]];
		}
	}
public:
	SegTreeSum(int n, val_t init = 0) {
		this->n = n;
		N = 1 << ceillog2(n);
		base = N - 1;
		nodes = vector<segval_t>(base + N, { false, 0, 0, 0 });
		common_init();
		upd(0, n, init);
	}
	SegTreeSum(const vector<val_t> &a) {
		this->n = int(a.size());
		N = 1 << ceillog2(n);
		base = N - 1;
		nodes = vector<segval_t>(base + N, { false, 0, 0, 0 });
		common_init();
		Loop(i, n) {
			nodes[base + i] = { true, a[i], 0, a[i] };
		}
		Loopr(i, base) {
			merge(i);
		}
	}
	void upd(int s, int t, val_t x) {
		if (s >= t) return;
		change_rec(s, t, 0, N, 0, x, UPD);
	}
	void add(int s, int t, val_t x) {
		if (s >= t) return;
		change_rec(s, t, 0, N, 0, x, ADD);
	}
	val_t sumof(int s, int t) {
		if (s >= t) return 0;
		return solve_rec(s, t, 0, N, 0);
	}
};

int main() {
	quickio();
	tree_t T;
	cin >> T.n;
	Loop(i, T.n) {
		int k; cin >> k;
		Loop(_, k) {
			int c; cin >> c;
			T.edges.push_back({ i, c });
		}
	}
	Tree *tree = new Tree(T, 0);
	tree->solve_sprs_ancestors();
	tree->solve_hld();
	vi ps = tree->get_hldpathsize();
	vector<SegTreeSum*> sts(ps.size());
	Loop(i, sts.size()) sts[i] = new SegTreeSum(ps[i]);
	int q; cin >> q;
	Loop(_, q) {
		int op; cin >> op;
		if (op == 0) {
			int v, w; cin >> v >> w;
			auto paths = tree->get_path_in_hld(tree->nodes[v].parent, v, false);
			Foreach(path, paths) {
				sts[path.id]->add(path.l, path.r, w);
			}
		}
		else {
			int u; cin >> u;
			auto paths = tree->get_path_in_hld(u, 0, false);
			ll ans = 0;
			Foreach(path, paths) {
				ans += sts[path.id]->sumof(path.l, path.r);
			}
			cout << ans << endl;
		}
	}
}