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:
// g++ macro.cpp -std=c++14
#include <bits/stdc++.h>
typedef long long ll;
const int INF = 1e9;
const int MOD = 1e9+7;
const ll LINF = 1e18;
using namespace std;
 
#define dump(x)  cout << #x << " = " << (x) << endl;
#define YES(n) cout << ((n) ? "YES" : "NO"  ) << endl
#define Yes(n) cout << ((n) ? "Yes" : "No"  ) << endl
#define POSSIBLE(n) cout << ((n) ? "POSSIBLE" : "IMPOSSIBLE"  ) << endl
#define Possible(n) cout << ((n) ? "Possible" : "Impossible"  ) << endl
#define possible(n) cout << ((n) ? "possible" : "impossible"  ) << endl
 
#define SANKOU(n,a,b) cout << ((n) ? (#a) : (#b) ) << endl
 
#define FOR(i,a,b) for(ll i=(a);i<(b);++i)
#define REP(i,n) for(ll i=0;i<(n);++i)
#define REPR(i,n) for(ll i=n;i>=0;i--)
 
#define FOREACH(x,a) for(auto&& (x) : (a) )
 
#define WFA(d,v) REP(k,v)REP(i,v)REP(j,v)d[i][j]=min(d[i][j],d[i][k]+d[k][j])
 
#define SCOUT(x) cout<<(x)<<" "
#define ENDL cout<<endl
 
#define VECCIN(x) for(auto&youso_: (x) )cin>>youso_
#define VECIN2(x,y) REP(i,x.size())cin>>x[i]>>y[i]
#define VECCOUT(x) if(1){for(auto tt=x.begin();tt!=x.end();tt++){if(tt!=x.begin())cout<<" ";cout<<(*tt);}cout<<endl;}

#define ALL(obj) (obj).begin(),(obj).end()
 
#define EXIST(n,x) (find(ALL(n),x)!=n.end())
#define UNIQUE(obj) sort(ALL( obj )); obj.erase(unique(ALL(obj)),obj.end())
#define EN(x) if(1){cout<<#x<<endl;return 0;}
#define COUT(x) cout<<(x)<<endl
void CINT(){}
template <class Head,class... Tail>
void CINT(Head&& head,Tail&&... tail){
    cin>>head;
    CINT(move(tail)...);
}
#define CIN(...) int __VA_ARGS__;CINT(__VA_ARGS__)
#define LCIN(...) ll __VA_ARGS__;CINT(__VA_ARGS__)
#define SCIN(...) string __VA_ARGS__;CINT(__VA_ARGS__)
 
template <class T = ll>
T IN(){T x;cin>>x;return (x);}
 
template <class Head>
void VT(Head head){}
template <class Head,class Seco,class... Tail>
void VT(Head&& head,Seco&& seco,Tail&&... tail){
    seco.resize(head);
    VT(head,move(tail)...);
}
void VT2(){}
template <class Head,class... Tail>
void VT2(Head&& head,Tail&&... tail){
  VECCIN(head);
  VT2(move(tail)...);
}
 
template <class Head>
void VT3(Head&& head){}
template <class Head,class Seco,class... Tail>
void VT3(Head&& head,Seco&& seco,Tail&&... tail){
  seco[head]=IN();
  VT3(head,move(tail)...);
}
 
#define VC1(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);VT2(__VA_ARGS__); //aaabbbccc
#define VC2(n,...) V __VA_ARGS__;VT(n,__VA_ARGS__);REP(i,n)VT3(i,__VA_ARGS__); //abcabcabc
 
// #include <boost/multiprecision/cpp_int.hpp>
// using namespace boost::multiprecision; // cpp_int
 
#define P pair<ll,ll>
#define V vector<ll>
#define M map<ll,ll>
#define S set<ll>
 
#define pb(a) push_back(a)
#define mp make_pair


using value_type = ll;


class Node;
using np = shared_ptr<Node>;

class Node{
public:

	value_type val, sum, lazy = 0;

	int index = -1;

	np p,l,r;

	int size = 1;
	bool rev = false;

	Node() : val(value_type()), sum(value_type()){}
	Node(value_type v) : val(v), sum(v){}
	Node(value_type v, int idx) : val(v), sum(v), index(idx){}


};

class LinkCutTree{

public:

	LinkCutTree()
	{
	}

	np makenode(value_type v){
		return make_shared<Node>(v);
	}

	np makenode(value_type v, int idx){
		return make_shared<Node>(v, idx);
	}

	void update(np x){
		x->size = 1;
		x->sum = x->val;

		if(x->r){
			x->size += x->r->size;
			x->sum += x->r->sum;
		}
		if(x->l){
			x->size += x->l->size;
			x->sum += x->l->sum;
		}
	}


	bool isroot(np x){
		return !(x->p)  || (x->p->l != x && x->p->r != x);
	};

	void rotr(np x){
		np q = x->p; // 一つ上の親
		np qq = q->p; // 二つ上の親

		if((q->l = x->r)) // xの右に子があったらqに付け替える
			x->r->p = q;

		x->r = q; // qとxで親子関係の入れ替え
		q->p = x;

		update(q);
		update(x);

		if((x->p = qq)){
			// 二つ上の親からみた子(qがあった所)をxに更新
			if(qq->l == q)
				qq->l = x;
			if(qq->r == q)
				qq->r = x;

			update(qq);
		}
	}

	void rotl(np x){
		np q = x->p; // 一つ上の親
		np qq = q->p; // 二つ上の親

		if((q->r = x->l)) // xの左に子があったらqに付け替える
			x->l->p = q;

		x->l = q; // qとxで親子関係の入れ替え
		q->p = x;

		update(q);
		update(x);

		if((x->p = qq)){
			// 二つ上の親からみた子(qがあった所)をxに更新
			if(qq->l == q)
				qq->l = x;
			if(qq->r == q)
				qq->r = x;

			update(qq);
		}
	}

	// 対象のノードをsplay木の親まで持っていく
	np splay(np x){
		push(x);

		while(!isroot(x)){
			np q = x->p;

			if(isroot(q)){

				push(q);
				push(x);

				if(q->l == x)
					rotr(x);
				else
					rotl(x);
				break;
			}

			np qq = q->p;

			push(qq);
			push(q);
			push(x);

			if(qq->l == q){
				if(q->l == x){
					rotr(q); // 一直線なら
					rotr(x);
				}else{
					rotl(x);
					rotr(x);
				}
			}else{
				if(q->r == x){
					rotl(q); // 一直線なら
					rotl(x);
				}else{
					rotr(x);
					rotl(x);
				}
			}
		}

		return x;
	}

	// xと根のパスを繋げて、根を返す
	np expose(np x){
		np y;
		// どんどん親に向かっていく
		for(np q = x; q; q = q->p){
			splay(q);
			q->r = y;
			update(q);
			y = q;
		}
		splay(x);

		return y;
	}

	// 反転処理 遅延評価で呼び出す
	void toggle(np x){
		swap(x->l, x->r);
		x->rev ^= 1;
	}

	// パスへの値追加 遅延評価で呼び出す
	void propagate(np x, value_type val){

		x->lazy += val;
		x->val += val;
		x->sum += (val * x->size);
	}


	// 遅延評価
	void push(np x){

		if(x->lazy){
			if(x->r)
				propagate(x->r, x->lazy);
			if(x->l)
				propagate(x->l, x->lazy);

			x->lazy = 0;
		}

		if(x->rev){
			if(x->r)
				toggle(x->r);
			if(x->l)
				toggle(x->l);

			x->rev = false;
		}
	}

	// xとyを繋げる xが根になる
	void link(np x, np y){
		expose(y);
		expose(x);
		x->r = y;
		y->p = x;
	}

	// xを根から切る
	void cut(np x){
		expose(x);
		np y = x->l;
		x->l.reset();
		y->p.reset();
	}

	// xを根にする
	void evert(np x){
		expose(x);
		toggle(x);
		push(x);
	}

	np lca(np x, np y){
		expose(x);
		return expose(y);
	}

	// 根とxとのパスに重みを加算
	void set_propagate(np x, value_type val){
		expose(x);
		propagate(x, val);
		push(x);
	}

};


int main(){

	CIN(n);
	LinkCutTree t;

	vector<np> nodes(n);
	REP(i,n)
		nodes[i] = t.makenode(0,i);

	REP(i,n){
		CIN(k);
		REP(j,k)
			t.link(nodes[i], nodes[IN()]);
	}


	CIN(q);
	
	ll sum = 0;
	REP(f,q){
		if(IN()){
			CIN(k);
			t.expose(nodes[k]);

			COUT(nodes[k]->sum - sum);
		}else{
			CIN(a,b);
			sum += b;
			t.set_propagate(nodes[a], b);
		}
	}

}