時間制限 : sec, メモリ制限 : KB
English / Japanese  

Range Query on a Tree II

与えられた重み付き根付き木 $T$ に対して、次の2つの操作を行うプログラムを作成せよ。

  • $add(v,w)$: 根から節点 $v$ の間にある辺の重みを $w$ 増加させる。
  • $getSum(u)$: 根から節点 $u$ までの間にある辺の重みの総和を報告する。

ここでは、与えられる木 $T$ は $n$ 個の節点を持ち、 それぞれ0から $n-1$ の番号が割り当てられており、 節点0が根となっているものとする。
また、すべての辺の重みは0で初期化されているものとする。

Input

入力は以下の形式で与えられる。

$n$
$node_0$
$node_1$
$node_2$
$:$
$node_{n-1}$
$q$
$query_1$
$query_2$
$:$
$query_{q}$

入力の最初の行に、木 $T$ の節点の個数 $n$ が与えられる。
続く $n$ 行に、節点 $i$ の情報を表す $node_i$ が以下の形式で与えられる。

k c1 c2 ... ck

$k$ は次数を表す。$c_1$ $c_2$ ... $c_k$ は1番目の子の節点の番号、 2番目の子の節点の番号、... $k$ 番目の子の節点の番号を表す。

続いてクエリの数 $q$ が与えられる。
続く $q$ 行には、 $i$ 番目のクエリを表す $query_i$ が以下の形式で与えられる。

0 v w

または

1 u

各クエリの最初の数字はクエリの種類を示し、'0'が$add(v, w)$、'1'が$getSum(u)$を表す。

Constraints

  • 入力はすべて整数である。
  • $ 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 $

Output

各$getSum$クエリについて、値を1行ずつ出力せよ。

Sample Input 1

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

Sample Output 1

0
0
40
150

Sample Input 2

4
1 1
1 2
1 3
0
6
0 3 1000
0 2 1000
0 1 1000
1 1
1 2
1 3

Sample Output 2

3000
5000
6000