Chinese Version

Russian Version

You are given a tree with N nodes and each has a value associated with it. You are given Q queries, each of which is either an update or a retrieval operation.

The update query is of the format

i j X

This means you'd have to add a GP series to the nodes which lie in the path from node i to node j (both inclusive) with first term of the GP as X on node i and the common ratio as R (given in the input)

The retrieval query is of the format

i j

You need to return the sum of the node values (S) lying in the path from node i to node j modulo 100711433.

Input Format

The first line contains two integers (N and R respectively) separated by a space.

In the next N-1 lines, the$ i^{th}$ line describes the $i^{th} $edge: a line with two integers a b separated by a single space denotes an edge between a, b.

The next line contains 2 space separated integers (U and Q respectively) representing the number of Update and Query operations to follow.

U lines follow. Each of the next U lines contains 3 space separated integers (i,j, and X respectively).

Each of the next Q lines contains 2 space separated integers, i and j respectively.

Output Format

It contains exactly Q lines and each line containing the answer of the$ i^{th}$ query.

Constraints

2 <= N <= 100000

2 <= R <= $10^{9}$

1 <= U <= 100000

1 <= Q <= 100000

1 <= X <= 10

1 <= a, b, i, j <= N

Sample Input

6 2
1 2
1 4
2 6
4 5
4 3
2 2
1 6 3
5 3 5
6 4
5 1

Sample Output

31
18

Explanation

The node values after the first updation becomes :

3 6 0 0 0 12

The node values after second updation becomes :

3 6 20 10 5 12

Answer to Query #1: 12 + 6 + 3 + 10 = 31

Answer to Query #2: 5 + 10 +3 = 18

见题面

见题面