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:
#define _USE_MATH_DEFINES

#include <cstdio>
#include <cstdlib>
#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <vector>
#include <queue>
#include <map>
#include <set>
#include <unordered_map> 
#include <unordered_set>
#include <functional>

using namespace std;

typedef pair<long long int, long long int> P;
typedef tuple<int, int, int> T;

long long int INF = 1e18;
long long int MOD = 1e9 + 7;

/*

訪問順（行きがけ順）をもとに、セグ木に各頂点を割り振る。

・頂点 u は、in[u] 番目に割り振られる。

・頂点 u の部分木は、区間 [in[u], out[u]) に割り振られる。

・頂点 u から根までのパスは、区間[in[nxt[u]], in[u]] を、
　u = par[nxt[u]] と代入しながら根まで処理すれば良い。

*/

int sz[210000]; // 部分木の大きさ
vector<int> g[210000]; // 親から子への辺
int par[210000]; // 子から親への辺
int nxt[210000]; // HL分解後の、各パスの終点
int in[210000]; // 訪問順（行きがけ順）
int out[210000]; // 部分木に含まれる訪問順（行きがけ順）の最大値
int t = 0; // 

void dfs_sz(int v) {
	sz[v] = 1;
	for(int &u: g[v]) {
		dfs_sz(u);
		sz[v] += sz[u];
		if(sz[u] > sz[g[v][0]]) {
			swap(u, g[v][0]);
		}
	}
}

void dfs_hld(int v) {
	in[v] = t++;
	for(int u: g[v]) {
		nxt[u] = (u == g[v][0] ? nxt[v] : u);
		dfs_hld(u);
	}
	out[v] = t;
}

int const TREE_SIZE = (1 << 20);

// Add が通用するのは、min, max, sum のいずれかに限りそう
class LazySegTreeAdd{
	public:
	// コンストラクタ
	LazySegTreeAdd(function<long long int(long long int, long long int)> monoidFunc_, 
		function<long long int(long long int, long long int)> nodeUpdateFunc_, long long int invalidValue_){
		monoidFunc = monoidFunc_;
		nodeUpdateFunc = nodeUpdateFunc_;
		invalidValue = invalidValue_;
	}
	// 値の初期化
	void init(long long int initValue){
		for(int i = 0; i < TREE_SIZE; i++){
			segTree[i] = initValue;
			beforeProp[i] = 0;
		}
	}
	// 区間 [a, b] (0-indexed)にwを足す O(log N)
	void add(int a, int b, long long int w){
		add_(a + 1, b + 2, 1, w, 0, 0, TREE_SIZE / 2);
	}
	// 区間 [a, b] (0-indexed)の値を求める O(log N)
	long long int query(int a, int b){
		return query_(a + 1, b + 2, 1, 0, 0, TREE_SIZE / 2);
	}
	private:
	function<long long int(long long int, long long int)> monoidFunc;
	function<long long int(long long int, long long int)> nodeUpdateFunc;
	long long int invalidValue;
	long long int segTree[TREE_SIZE]; // 1-indexed
	long long int beforeProp[TREE_SIZE]; // 子に伝搬してない値、1-indexed

	// [a, b) に num を足す
	long long int add_(int a, int b, int index, long long int num, long long int diff, int l, int r){
		segTree[index] += nodeUpdateFunc(diff, r - l);
		beforeProp[index] += diff;
		if(r <= a || b <= l){
			return segTree[index];
		}
		if(a <= l && r <= b){
			segTree[index] += nodeUpdateFunc(num, r - l);
			beforeProp[index] += num;
			return segTree[index];
		}
			
		long long int ret = monoidFunc(
			add_(a, b, index * 2, num, beforeProp[index], l, (l + r) / 2),
			add_(a, b, index * 2 + 1, num, beforeProp[index], (l + r) / 2, r)
		);
		beforeProp[index] = 0;
		return segTree[index] = ret;
	}
	// 区間 [a, b) の値を求める O(log N)
	long long int query_(int a, int b, int index, long long int diff, int l, int r){
		segTree[index] += nodeUpdateFunc(diff, r - l);
		beforeProp[index] += diff;
		if(r <= a || b <= l){
			return invalidValue;
		}
		if(a <= l && r <= b){
			return segTree[index];
		}
		long long int ret = monoidFunc(
			query_(a, b, index * 2, beforeProp[index], l, (l + r) / 2), 
			query_(a, b, index * 2 + 1, beforeProp[index], (l + r) / 2, r)
		);
		beforeProp[index] = 0;
		return ret;
	}
};

long long int monoidFunc(long long int a, long long int b){
	return a + b;
}
// 親から伝搬した値が diff、子のカバーする区間幅が len のときに、子に加算する値
long long int nodeUpdateFunc(long long int diff, long long int len){
	return diff * len;
}
LazySegTreeAdd segTree(monoidFunc, nodeUpdateFunc, 0);

int main(){
	int n;
	cin >> n;
	for(int i = 0; i < n; i++){
		int k;
		cin >> k;
		for(int loop = 0; loop < k; loop++){
			int c;
			cin >> c;
			g[i].push_back(c);
			par[c] = i;
		}
	}
	par[0] = -1;
	dfs_sz(0);
	dfs_hld(0);
	/*
	cout << "in : ";
	for(int i = 0; i < n; i++){
		cout << in[i] << " ";
	}
	cout << endl;
	cout << "out : ";
	for(int i = 0; i < n; i++){
		cout << out[i] << " ";
	}
	cout << endl;
	cout << "sz : ";
	for(int i = 0; i < n; i++){
		cout << sz[i] << " ";
	}
	cout << endl;
	cout << "nxt : ";
	for(int i = 0; i < n; i++){
		cout << nxt[i] << " ";
	}
	cout << endl;
	cout << "par : ";
	for(int i = 0; i < n; i++){
		cout << par[i] << " ";
	}
	cout << endl;
	*/
	segTree.init(0);
	int q;
	cin >> q;
	for(int loop = 0; loop < q; loop++){
		int tp;
		cin >> tp;
		if(tp == 0){
			long long int v, w;
			cin >> v >> w;
			while(v != -1){
				segTree.add(in[nxt[v]], in[v], w);
				v = par[nxt[v]];
			}
			segTree.add(in[0], in[0], -w);
		}else{
			int u;
			cin >> u;
			long long int ans = 0;
			while(u != -1){
				ans += segTree.query(in[nxt[u]], in[u]);
				u = par[nxt[u]];
			}
			cout << ans << endl;
		}
	}
	return 0;
}