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>
using namespace std;
using ll = long long;
using graph = vector<vector<int>>;

struct RS {
	using type = ll;
	static type id() { return 0; }
	static type op(const type& l, const type & r) {
		return l + r;
	}
};

class lct_node {
	using M = RS;
	using T = typename M::type;
	using U = ll;

	lct_node *l, *r, *p;
	T val, all;
	int size;
	bool flag;
	U lazy;

	int pos() {
		if (p && p->l == this) return -1;
		if (p && p->r == this) return 1;
		return 0;
	}
	void update() {
		size = (l ? l->size : 0) + (r ? r->size : 0) + 1;
		all = M::op(l ? l->all : M::id(), M::op(val, r ? r->all : M::id()));
	}
	void update_lazy(U v) {
		val += v;
		all += v * size;
		if (!flag) {
			lazy = v;
			flag = true;
		}
		else {
			lazy += v;
		}
	}
	void rev_data() {}
	void push() {
		if (pos()) p->push();
		if (flag) {
			if (l) l->update_lazy(lazy);
			if (r) r->update_lazy(lazy);
			flag = false;
		}
	}
	void rot() {
		lct_node *par = p;
		lct_node *mid;
		if (p->l == this) {
			mid = r;
			r = par;
			par->l = mid;
		}
		else {
			mid = l;
			l = par;
			par->r = mid;
		}
		if (mid) mid->p = par;
		p = par->p;
		par->p = this;
		if (p && p->l == par) p->l = this;
		if (p && p->r == par) p->r = this;
		par->update();
		update();
	}
	void splay() {
		push();
		while (pos()) {
			int st = pos() * p->pos();
			if (!st) rot();
			else if (st == 1) p->rot(), rot();
			else rot(), rot();
		}
	}

public:
	lct_node() : l(nullptr), r(nullptr), p(nullptr), val(M::id()), all(M::id()), size(1), flag(false) {}
	lct_node(const T& v) : l(nullptr), r(nullptr), p(nullptr), val(v), all(v), size(1), flag(false) {}
	void init(U v) {
		val = all = T(v);
	}
	void expose() {
		for (lct_node *x = this, *y = nullptr; x; y = x, x = x->p) x->splay(), x->r = y, x->update();
		splay();
	}
	void link(lct_node *x) {
		x->expose();
		expose();
		p = x;
	}
	void cut() {
		expose();
		l->p = nullptr;
		l = nullptr;
		update();
	}
	T find() {
		expose();
		return all;
	}
	void update(U v) {
		expose();
		update_lazy(v);
	}
};

const int MAX = 1e5;

lct_node lct[MAX];

void build(int v, const graph& G) {
	for (auto to : G[v]) {
		lct[to].link(&lct[v]);
		build(to, G);
	}
}

int main()
{
	ios::sync_with_stdio(false), cin.tie(0);
	int n;
	cin >> n;
	graph G(n);
	for (int i = 0; i < n; i++) {
		int k;
		cin >> k;
		for (int j = 0; j < k; j++) {
			int c;
			cin >> c;
			G[i].push_back(c);
		}
	}
	build(0, G);
	int q;
	cin >> q;
	while (q--) {
		int com;
		cin >> com;
		if (com == 0) {
			int v, w;
			cin >> v >> w;
			lct[v].update(w);
		}
		else {
			int u;
			cin >> u;
			printf("%lld\n", lct[u].find() - lct[0].find());
		}
	}
	return 0;
}