시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

문제

In a faraway world, there are N towns, in these towns are heroes and they are preparing for an impending battle. However, while preparing their stores, they needed more gold! They needed money to buy more food and weapons. Thus, to deliver gold between towns, the heroes utilise their safest and most reliable transportation vehicles, Trucks.

The N towns are connected via N − 1 roads in a way such that there is exactly one path between any two towns using one or more roads. These roads are numbered from 1 to N − 1 each having their own length Di. Also, there is a gatekeeper on each road which will collect a certain amount of gold bars as a toll for using the road, the toll for each road can be different and vehicles are required to pay this toll before using the road. Notably, the ith road connects towns Ai and Bi, has distance of Di and toll cost of Ti.

Obviously, the heroes have to pay for the fuel costs of travelling in the trucks. The amount of fuel used by a truck depends on the amount of gold it is currently carrying. Notably, if the truck is carrying X gold bars and travels 1 unit distance, it will use up X units of fuel.

The heroes have arranged a bunch of trips where the ith trip requires G gold bars to be transported from town Ai to Bi. (Note that G is constant across all trips.) Which is to say, in addition to the gold bars being used to pay for the tolls, an additional G have to be delivered to the destination town at the end of the trip. The heroes would like to minimise the amount of fuel used and would take the optimal route and carry the optimal number of gold bars to pay the tolls and minimise fuel usage. However, between trips the toll cost of certain roads may change and thus affect the fuel used in future trips.

Since, the heroes are busy preparing for battle, they do not have time to calculate their fuel usage and would like you to do so for them for each trip (this is a query operation). Keep in mind that between trips the toll cost of certain roads may change (this is an update operation). Given the correct order of events with the trips they are planning and the toll changes of roads, calculate their fuel consumption for each trip. As the result can be very large, you should give the answer modulo 109 + 7.

입력

Your program must read from standard input.

The first line contains two integers N and G, the number of towns and the number gold bars each trip will transport.

N − 1 lines will follow. The ith line contains 4 integers, Ai, Bi, Di and Ti.

The next line contains a single integer Q representing the total number of trips and changes to tolls on the roads (i.e. the total number of query and update operations).

Q lines will follow. The ith line will begin with an integer Vi:

  • If Vi = 0, this represents a update operation; the line will contain 3 more integers X Y T, which indicates that the toll of the road that connects town X and Y is changed to T.
  • If Vi = 1, this represents a query operation; the line will contain 2 more integers X Y, which indicates a trip from town X to town Y .

출력

Your program must print to standard output.

For each query operation, you should output a line containing a single integer — the minimum fuel used in the trip modulo 109 + 7.

The result of each trip needs to be outputted in the same order as given in the input.

제한

  • 2 ≤ N ≤ 100 000
  • 1 ≤ Q ≤ 100 000
  • 1 ≤ Ai, Bi ≤ N
  • 1 ≤ Di, Ti, G ≤ 109

서브태스크 1 (5점)

  • Vi = 1
  • Each town has at most two roads connected to it
  • Ti = 0

서브태스크 2 (9점)

  • Vi = 1
  • Ti = 0

서브태스크 3 (12점)

  • Vi = 1
  • Ti = Tj for all i ≠ j
  • Di = 1

서브태스크 4 (17점)

  • Vi = 1
  • Each town has at most two roads connected to it

서브태스크 5 (20점)

  • 0 ≤ Vi ≤ 1
  • Each town has at most two roads connected to it

서브태스크 6 (18점)

  • 0 ≤ Vi ≤ 1
  • N, Q ≤ 5000

서브태스크 7 (19점)

  • 0 ≤ Vi ≤ 1

예제 입력 1

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

예제 출력 1

23
18

The first query asks for a journey from node 3 to 6, transporting 2 gold bars. The truck will start at node 3 with 11 gold bars as it is the minimum number of gold bars required to end at node 6 with 2 gold bars. Travelling from node 3 to 2, we first pay 2 gold bars for the toll, ending up with 9 gold bars. Travelling a distance of 1 unit with 9 gold bars consumes 9 units of fuel. Similarly, from node 2 to 4 we have 6 gold bars, consuming 12 units of fuel and from node 4 to 6 we have 2 gold bars consuming 2 units of fuel. Totaling up to 9 + 12 + 2 = 23 units of fuel.

For the second query we change the toll on the road connecting 4 and 5 to 5. Then the third query asks for a journey from node 2 to 5 to transport 2 gold bars. Optimally, we begin at node 2 with 10 gold bars. To travel from node 2 to 4 we first spend 3 gold bars on the toll, to be left with 7 bars and then travel the road, consuming 14 units of fuel. Similarly, we travel on the road from node 4 to 5 with 2 gold bars consuming 4 units of fuel, totalling to 14 + 4 = 18 units of fuel.

예제 입력 2

4 3
1 2 3 0
2 3 1 0
3 4 4 0
1
1 1 4

예제 출력 2

24

There are no tolls, hence the truck can just start will 3 gold bars and travel from node 1 to 4. Travelling a distance of 8 units, thus consuming 8 × 3 = 24 units of fuel.

채점 및 기타 정보

  • 예제는 채점하지 않는다.