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 PYTHON3):

Solution:
from collections import deque
import sys
from typing import List

sys.setrecursionlimit(200000)


N = int(input())
G: List[List[int]] = [[0]] * N
for i in range(N):
    k, *c = map(lambda x: int(x), input().split())
    G[i] = c

H = [0] * N
prv = [None] * N


def dfs(v):
    s = 1
    heavy = None
    m = 0
    for w in G[v]:
        prv[w] = v
        c = dfs(w)
        if m < c:
            heavy = w
            m = c
        s += c
    H[v] = heavy
    return s


dfs(0)


SS: List[List[int]] = []
D: List[int] = []
L = [0] * N
I = [0] * N  # noqa: E741
que = deque([(0, 0)])
while que:
    v, d = que.popleft()
    S: List[int] = []
    k = len(SS)
    while v is not None:
        I[v] = len(S)
        S.append(v)
        L[v] = k
        h = H[v]
        for w in G[v]:
            if h == w:
                continue
            que.append((w, d + 1))
        v = h
    SS.append(S)
    D.append(d)


C = list(map(len, SS))
DS0 = [[0] * (c + 1) for c in C]
DS1 = [[0] * (c + 1) for c in C]


def add(K, data, k, x):
    while k <= K:
        data[k] += x
        k += k & -k


def get(K, data, k):
    s = 0
    while k:
        s += data[k]
        k -= k & -k
    return s


def query_add(v, x):
    while v is not None:
        l = L[v]  # noqa: E741
        i = I[v]
        add(C[l], DS1[l], i + 1, -x)
        add(C[l], DS1[l], 1, x)
        add(C[l], DS0[l], i + 1, x * (i + 1))
        v = prv[SS[l][0]]


def query_sum(v):
    s = - get(C[0], DS1[L[0]], 1) - get(C[0], DS0[L[0]], 1)
    while v is not None:
        l = L[v]  # noqa: E741
        i = I[v]
        s += get(C[l], DS1[l], i + 1) * (i + 1) + get(C[l], DS0[l], i + 1)
        v = prv[SS[l][0]]
    return s


Q = int(input())
ans = []
for q in range(Q):
    t, *cmd = map(lambda x: int(x), input().split())
    if t:
        ans.append(str(query_sum(cmd[0])))
    else:
        v, w = cmd
        query_add(v, w)
print("\n".join(ans))