There is a network consisting of N machines (sequentially numbered from 0 to N-1) interconnected through N-1 bidirectional communication cables. Any two machines can perform bidirectional communication through one or more cables. From time to time, machines in the network are renewed. When a new machine is introduced, the cables directly connected to it are also replaced with thicker ones to cope with the increased volume of communication traffic.
The communication fee arising from communication traffic between any two machines is calculated by summing the charges assigned to all the cables routing via the two. A unique charging scheme is employed in this system: if the size of a cable is a multiple of K, then the cable is not charged (free of charge). Other cables are charged according to their sizes.
Based on the given information on the network topology and Q instructions, write a program to execute each instruction.
The input is given in the following format.
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
The first line provides the number of machines N (2 ≤ N ≤ 105) and the cable size K (1 ≤ K ≤ 105) (the reference value for determining free of charge cables). Each of subsequent N-1 lines provides the i-th cable information that directly connects two machines a_i and b_i (0 ≤ a_i < b_i ≤ N-1), followed by the cable’s initial size c_i (1 ≤ c_i ≤ 105). For any pair of machines, the number of cables directly connecting them is either one or zero. The next line following them provides the number of instructions Q (1 ≤ Q ≤ 105). Each of the Q lines following it provides the i-th instruction query_i, which is either one of the following two:
add x d
or
send s t
The instruction add x d increase the size of all cables directly connected to machine x (0 ≤ x ≤ N-1) by d (1 ≤ d ≤ 105).
The instruction send s t reports the charge imposed to the communication between the two machines s (0 ≤ s ≤ N-1) and t (0 ≤ t ≤ N-1), where s ≠ t.
At least one send instruction is included in the input information.
For each send command, output the communication charge between s and 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