それぞれ 0 から N -1 までの番号が割り当てられたN 台のマシンが、合計 N-1 本の双方向に通信できるケーブルで接続され、ネットワークを形成している。どの２つのマシンも、いくつかのケーブルをたどって双方向に通信を行うことができる。このネットワークでは、マシンが更新されると、通信量の増大に備えるために、そのマシンに直接接続されているすべてのケーブルをより太いものに交換する。
２つのマシンの間の通信料金は、その間を経由するすべてのケーブルの通信料金の総和になる。ただし、このネットワークはユニークな課金システムで運営されており、太さが K の倍数であるようなケーブルは、そのケーブルの分の通信料金が無料になる。それ以外のケーブルは、太さと同じ通信料金がかかる。あなたの仕事は、このネットワークの料金計算システムを開発することである。
ネットワークの形状とQ 個の命令が与えられたとき、それぞれの命令を処理するプログラムを作成せよ。ただし、命令は以下の２種類である。
入力は以下の形式で与えられる。
N K
a_1 b_1 c_1
a_2 b_2 c_2
:
a_{N−1} b_{N−1} c_{N−1}
Q
query_1
query_2
:
query_Q
１行目に、マシンの総数 N (2 ≤ N ≤ 105) と、通信料金が無料になる太さを決める数 K (1 ≤ K ≤ 105) が与えられる。続く N-1 行に、２つのマシンを直接つなぐケーブルの情報が与えられる。a_i と b_i (0 ≤ a_i < b_i ≤ N-1) は i 番目のケーブルがつなぐ２つのマシンの番号を表し、c_i (1 ≤ c_i ≤ 105) はそのケーブルの初期状態での太さを表す。ただし、どの２つのマシンについても、それらを直接つなぐケーブルは１本以下とする。続く１行に、命令の数 Q (1 ≤ Q ≤ 105) が与えられる。続く Q 行に i 番目の命令 query_i が与えられる。各 query_i は、以下のいずれかの形式で与えられる。
add x d
または
send s t
add x d は、マシン x (0 ≤ x ≤ N-1) に直接接続されているすべてのケーブルの太さを d (1 ≤ d ≤ 105) だけ増加させる。
send s t は、マシン s (0 ≤ s ≤ N-1) とマシン t (0 ≤ t ≤ N-1) の間の通信料金を報告する。ただし、s ≠ t である。
入力には必ず１つ以上の send 命令が含まれる。
各 send 命令について、マシン s とマシン t の間の通信料金を、それぞれ１行に出力する。
6 3 0 1 1 0 2 1 0 3 1 2 4 1 2 5 1 3 send 1 4 add 2 2 send 1 4
3 1