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 <cstdio>
#include <cstring>
#include <iostream>
#include <string>
#include <cmath>
#include <bitset>
#include <vector>
#include <map>
#include <set>
#include <queue>
#include <deque>
#include <algorithm>
#include <complex>
#include <unordered_map>
#include <unordered_set>
#include <random>
#include <cassert>
#include <fstream>
#include <utility>
#include <functional>
#define popcount __builtin_popcount
using namespace std;
typedef long long int ll;
typedef pair<int, int> P;

template<typename Monoid=int, typename OperatorMonoid=Monoid>
struct LinkCutTree{
	using F=function<Monoid(Monoid, Monoid)>;
	using G=function<Monoid(Monoid, OperatorMonoid, int)>;
	using H=function<OperatorMonoid(OperatorMonoid, OperatorMonoid)>;
	using S=function<Monoid(Monoid)>;

	struct Node{
		Node *l, *r, *p;
		int idx;
		Monoid key, sum;
		OperatorMonoid lazy;

		bool rev;
		int sz;

		bool is_root(){
			return !p || (p->l!=this && p->r!=this);
		}

		Node(int idx, const Monoid &key, const OperatorMonoid &om):idx(idx), key(key), sum(key), lazy(om), sz(1), l(nullptr), r(nullptr), p(nullptr), rev(false) {}
	};

	const Monoid M1;
	const OperatorMonoid OM0;
	const F f;
	const G g;
	const H h;
	const S s;

	LinkCutTree():LinkCutTree([](Monoid a, Monoid b){ return a+b;}, [](Monoid a){ return a;}, Monoid()){}
	LinkCutTree(const F &f, const S &s, const Monoid &M1):LinkCutTree(f, G(), H(), s, M1, OperatorMonoid()){}
	LinkCutTree(const F &f, const G &g, const H &h, const Monoid &M1, const OperatorMonoid &OM0):LinkCutTree(f, g, h, S(), M1, OM0){}
	LinkCutTree(const F &f, const G &g, const H &h, const S &s, const Monoid &M1, const OperatorMonoid &OM0):f(f), g(g), h(h), s(s), M1(M1), OM0(OM0){}

	Node *make_node(int idx, const Monoid &v=Monoid()){
		return new Node(idx, v, OM0);
	}

	void propagate(Node *t, const OperatorMonoid &x){
		t->lazy=h(t->lazy, x);
		t->key=g(t->key, x, 1);
		t->sum=g(t->sum, x, t->sz);
	}

	void toggle(Node *t){
		assert(t);
		swap(t->l, t->r);
		t->sum=s(t->sum);
		t->rev^=true;
	}

	void push(Node *t){
		if(t->lazy!=OM0){
			if(t->l) propagate(t->l, t->lazy);
			if(t->r) propagate(t->r, t->lazy);
			t->lazy=OM0;
		}
		if(t->rev){
			if(t->l) toggle(t->l);
			if(t->r) toggle(t->r);
			t->rev=false;
		}
	}

	void update(Node *t){
		t->sz=1;
		t->sum=t->key;
		if(t->l) t->sz+=t->l->sz, t->sum=f(t->l->sum, t->sum);
		if(t->r) t->sz+=t->r->sz, t->sum=f(t->sum, t->r->sum);
	}

	void rotr(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->l=t->r)) t->r->p=x;
		t->r=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void rotl(Node *t){
		auto *x=t->p, *y=x->p;
		if((x->r=t->l)) t->l->p=x;
		t->l=x, x->p=t;
		update(x), update(t);
		if((t->p=y)){
			if(y->l==x) y->l=t;
			if(y->r==x) y->r=t;
			update(y);
		}
	}

	void splay(Node* t){
		push(t);
		while(!t->is_root()){
			auto *q=t->p;
			if(q->is_root()){
				push(q), push(t);
				if(q->l==t) rotr(t);
				else rotl(t);
			}else{
				auto *r=q->p;
				push(r), push(q), push(t);
				if(r->l==q){
					if(q->l==t) rotr(q), rotr(t);
					else rotl(t), rotr(t);
				}else{
					if(q->r==t) rotl(q), rotl(t);
					else rotr(t), rotl(t);
				}
			}
		}
	}

	Node *expose(Node *t){
		Node *rp=nullptr;
		for(Node *cur=t; cur; cur=cur->p){
			splay(cur);
			cur->r=rp;
			update(cur);
			rp=cur;
		}
		splay(t);
		return rp;
	}

	void link(Node *child, Node *parent){
		expose(child);
		expose(parent);
		child->p=parent;
		parent->r=child;
		update(parent);
	}

	void cut(Node *child){
		expose(child);
		auto *parent=child->l;
		child->l=nullptr;
		parent->p=nullptr;
		update(child);
	}

	void evert(Node *t){
		expose(t);
		toggle(t);
		push(t);
	}

	Node *lca(Node *u, Node *v){
		if(get_root(u)!=get_root(v)) return nullptr;
		expose(u);
		return expose(v);
	}

	Node *get_root(Node *x){
		expose(x);
		while(x->l){
			push(x);
			x=x->l;
		}
		return x;
	}

	void set_propagate(Node *t, const OperatorMonoid &x){
		expose(t);
		propagate(t, x);
		push(t);
	}
};
int main()
{
	int n;
	cin>>n;
	using LCT=LinkCutTree<ll>;
	auto f=[](ll a, ll b){ return a+b;};
	auto g=[](ll a, ll x, int len){ return a+x*len;};
	auto h=[](ll x, ll y){ return x+y;};
	LCT lct(f, g, h, 0, 0);
	vector<LCT::Node*> nodev(n);
	for(int i=0; i<n; i++){
		nodev[i]=lct.make_node(i, 0);
	}
	for(int i=0; i<n; i++){
		int k; cin>>k;
		for(int j=0; j<k; j++){
			int c; cin>>c;
			lct.link(nodev[c], nodev[i]);
		}
	}
	int Q; cin>>Q;
	ll tot=0;
	for(int t=0; t<Q; t++){
		int k; cin>>k;
		if(k==0){
			int v;
			ll w;
			cin>>v>>w;
			tot+=w;
			lct.set_propagate(nodev[v], w);
		}else{
			int u;
			cin>>u;
			lct.expose(nodev[u]);
			cout<<nodev[u]->sum-tot<<endl;
		}
	}
	return 0;
}