p02375 Range Query on a Tree II
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
```python
#!/usr/bin/env python3
# GRL_5_E: Tree - Range Query on Tree 2


# Undirected Graph
class Edge:
    __slots__ = ('v', 'w')

    def __init__(self, v, w):
        self.v = v
        self.w = w

    def either(self):
        return self.v

    def other(self, v):
        if v == self.v:
            return self.w
        else:
            return self.v


class Graph:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, e):
        self._edges[e.v].append(e)
        self._edges[e.w].append(e)

    def adj(self, v):
        return self._edges[v]

    def edges(self):
        for es in self._edges:
            for e in es:
                yield e


class HeavyLightDecomposition:
    class _Path:
        __slots__ = ('nodes', '_index')

        def __init__(self):
            self.nodes = []
            self._index = None

        @property
        def head(self):
            return self.nodes[0]

        @property
        def size(self):
            return len(self.nodes)

        def append(self, v):
            self.nodes.append(v)

        def index(self, v):
            if self._index is None:
                self._index = {v: i for i, v in enumerate(self.nodes)}
            return self._index[v]

        def next(self, v):
            return self.nodes[self.index(v)+1]

    def __init__(self, graph, root):
        self._paths = {}
        self._parent = [root] * graph.v
        self._head = [-1] * graph.v
        self._find_paths(graph, root)

    def _find_paths(self, graph, root):
        def create_path(v):
            path = self._Path()
            u = v
            while u != -1:
                path.append(u)
                self._head[u] = v
                u = heavy[u]
            return path

        size = [1] * graph.v
        maxsize = [0] * graph.v
        heavy = [-1] * graph.v
        visited = [False] * graph.v

        stack = [root]
        while stack:
            v = stack.pop()
            if not visited[v]:
                visited[v] = True
                stack.append(v)
                for e in graph.adj(v):
                    w = e.other(v)
                    if not visited[w]:
                        self._parent[w] = v
                        stack.append(w)
            else:
                if v != root:
                    p = self._parent[v]
                    if size[v] > maxsize[p]:
                        maxsize[p] = size[v]
                        heavy[p] = v
                    size[p] += size[v]
                for e in graph.adj(v):
                    w = e.other(v)
                    if w != self._parent[v] and w != heavy[v]:
                        self._paths[w] = create_path(w)

        self._paths[root] = create_path(root)

    def parent(self, v):
        return self._parent[v]

    def paths(self):
        return self._paths.values()

    def get_path(self, v):
        return self._paths[self._head[v]]


class PathSum2:
    """PathSum with range update.
    """
    def __init__(self, graph, root):
        self.root = root
        self.hld = HeavyLightDecomposition(graph, root)
        self.rq = {p.head: RangeQuery(p.size) for p in self.hld.paths()}

    def add(self, v, val):
        u = v
        while u != self.root:
            path = self.hld.get_path(u)
            head = path.head
            if head != self.root:
                i = path.index(head)
            else:
                i = path.index(path.next(head))
            j = path.index(u)
            self.rq[head].add(i+1, j+1, val)
            u = self.hld.parent(head)

    def get(self, v):
        weight = 0
        u = v
        while u != self.root:
            path = self.hld.get_path(u)
            head = path.head
            i = path.index(head)
            j = path.index(u)
            weight += self.rq[head].sum(i+1, j+1)
            u = self.hld.parent(head)

        return weight


# Binary Indexed Tree
class BinaryIndexedTree:
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (self.size+1)

    def add(self, i, v):
        while i <= self.size:
            self.bit[i] += v
            i += (i & -i)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= (i & -i)
        return s


class RangeQuery:
    def __init__(self, n):
        self.size = n
        self.bit1 = BinaryIndexedTree(n+1)
        self.bit2 = BinaryIndexedTree(n+1)

    def add(self, i, j, v):
        self.bit1.add(i, v * -i)
        self.bit1.add(j+1, v * (j+1))
        self.bit2.add(i, v)
        self.bit2.add(j+1, -v)

    def sum(self, i, j):
        s = self.bit1.sum(j+1) + (j+1)*self.bit2.sum(j+1)
        s -= self.bit1.sum(i) + i*self.bit2.sum(i)
        return s


def run():
    n = int(input())
    g = Graph(n)

    for i in range(n):
        k, *cs = [int(i) for i in input().split()]
        if k > 0:
            for j in cs:
                g.add(Edge(i, j))

    ps = PathSum2(g, 0)
    q = int(input())
    for _ in range(q):
        com, *args = [int(i) for i in input().split()]
        if com == 0:
            u, val = args
            ps.add(u, val)
        elif com == 1:
            u, = args
            print(ps.get(u))
        else:
            raise ValueError('invalid command')


if __name__ == '__main__':
    run()


```