Truck

In a faraway world, there are N towns. Heroes live in these towns and are preparing for an impending battle. While preparing their stores, they needed more gold! They needed money to buy more food and weapons. So, to deliver gold between towns, the heroes use their safest and most reliable vehicles, trucks.

The N towns are connected by N - 1 roads such that there is exactly one path between any two towns using one or more roads. The roads are numbered from 1 to N - 1 and each has its own length Di. Each road also has a gatekeeper who collects a certain amount of gold bars as a toll for using the road. The toll can differ from road to road, and vehicles must pay the toll before using the road. In particular, the ith road connects towns Ai and Bi, has length Di, and has toll cost Ti.

Of course, the heroes must also pay for the fuel used by the trucks. The amount of fuel a truck uses depends on the amount of gold it is currently carrying. In particular, if a truck is carrying X gold bars and travels 1 unit of distance, it uses up X units of fuel.

The heroes have arranged a number of trips. The ith trip requires G gold bars to be transported from town Ai to Bi. (G is the same for all trips.) That is, besides the gold bars used to pay the tolls, an additional G must be delivered to the destination town at the end of the trip. The heroes want to minimise the amount of fuel used, and they will take the optimal route and carry the optimal number of gold bars for paying tolls to minimise fuel usage. However, between trips the toll cost of certain roads may change, which affects the fuel used in later trips.

The heroes are busy preparing for battle, so they have no time to calculate their fuel usage and want you to do it 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 plan and the toll changes on roads, calculate their fuel consumption for each trip. The result can be very large, so output 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 of gold bars each trip transports.

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

The next line contains a single integer Q, the total number of trips and changes to road tolls (that is, the total number of query and update operations).

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

• If Vi = 0, this is an update operation; the line contains 3 more integers X Y T, meaning the toll of the road connecting towns X and Y is changed to T.
• If Vi = 1, this is a query operation; the line contains 2 more integers X Y, meaning a trip from town X to town Y.

Your program must print to standard output.

For each query operation, output one line containing a single integer: the minimum fuel used in that trip modulo 109 + 7.

Output the result of each trip 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