M. Marriage Proposals
time limit per test
7 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

In the town where Jack lives, there are $$$N$$$ villages and exactly $$$N - 1$$$ bidirectional roads which connect every village; there is $$$\textbf{exactly one}$$$ shortest path for commuting between any two villages. There is also $$$\textbf{exactly one}$$$ pearl shop in each road. Each shop sells $$$\textbf{exactly one}$$$ type of pearl. The shop on the $$$i^{th}$$$ road sells pearl type $$$a_i$$$ and is limited to $$$b_i$$$ balls of pearl for each person. It is guaranteed that the shop will be able to provide any customers up to $$$b_i$$$ balls.

In this town, there are $$$M$$$ types of pearls. For each type, the price per ball will be the same in any shop.

There is a custom in this town that when a man wants to propose to a woman in a different village, he will pick one type of pearl and buy that type $$$\textbf{as many balls as possible}$$$ from shops along the shortest path from his village to her village. He will pick a type of pearl that $$$\textbf{maximizes money spent}$$$. Later, the pearls will be made into a necklace.

Jack has recently become an accountant of the bachelor club of the town. The bachelor club mainly collects money from its members to support those who are going to make proposals. When he became the accountant, he just realized that the old accountant forgot to record the expenses during a period of time. Fortunate enough, there are records of events that occurred during that period, and also the records of pearl prices. Initially, the cost per ball of pearl type $$$j$$$ is $$$c_j$$$. Then, there are $$$Q$$$ following events in total which can be classified as two types:

  • $$${Type\ 1:}$$$ A man in village $$$x$$$ proposed to a woman in village $$$y$$$.
  • $$${Type\ 2:}$$$ The cost for a single ball of pearl type $$$j$$$ was changed to $$$c^{'}_{j}$$$ dollars. Pearl type $$$j$$$ will have price $$$c^{'}_{j}$$$ until there is an event that updates the price of pearl type $$$j$$$.

Help Jack find the expense for each proposal, and Jack will reward you with his grasshoppers!

Input

The first line contains three integers $$$N$$$ and $$$M\ (2 \leq N \leq 100,000,\ 1 \leq M \leq 100,000)$$$ — the number of villages in the town, and the number of types of pearls, respectively.

Each of the following $$$N - 1$$$ lines contains four integers $$$u,\ v,\ a,$$$ and $$$b$$$ $$$(1 \leq u, v \leq N,u \neq v, 1 \leq a \leq M, 1 \leq b \leq 10,000)$$$ respectively. Those integers indicate that there is a road from village $$$u$$$ to village $$$v$$$. The pearl shop on that road sells pearls of type $$$a$$$ and is limited to $$$b$$$ balls for each person.

The sum of the purchase limitation in each shop for each type of pearl does not exceed $$$10,000$$$, i.e. $$$$$$\text{for all}\ 1 \leq j \leq M, \displaystyle\sum_{a_i=j}b_i \leq 10,000\ .$$$$$$

The next line contains $$$M$$$ integers $$$c_1,c_2,\dots,c_M(1 \leq c_1,c_2,\dots,c_M \leq 1,000) $$$ — the initial price for each type of pearl.

The next line contains one integer $$$Q$$$ $$$(1 \leq Q \leq 10^5)$$$ — the number of events.

The following $$$Q$$$ lines contain the description of the events from earliest to latest. The first integer in each line is $$$t$$$ — the type of the event.

Case $$$t=1$$$, the line contains two additional integers $$$x$$$ and $$$y$$$ $$$(1 \leq x, y \leq N, x \neq y)$$$ respectively. This means that a man in village $$$x$$$ proposed to a woman in village $$$y$$$.

Case $$$t=2$$$, the line contains two additional integers $$$j$$$ and $$$c^{'}_{j}$$$ $$$(1 \leq j \leq M, 1 \leq c^{'}_{j} \leq 1,000)$$$ respectively. This means that the price of pearl type $$$j$$$ changed to $$$c^{'}_{j}$$$ dollars per ball.

Output

For each $$$type\ 1$$$ event, output a single integer — the total expense for the proposal in dollars. The output should be one integer per line.

Example
Input
5 2
1 2 1 3
2 3 2 2
2 4 1 1
1 5 1 1
1 1
7
1 1 3
1 2 4
1 3 4
2 2 10
1 1 3
2 1 2
1 4 5
Output
3
1
2
20
10
Note
Fig. M.1: Illustration of the town in the example.
In example $$$1$$$, there are two types of pearl, let visualize it as white and black respectively. Initially, both pearls cost $$$1$$$ dollar per ball.

In the first event, the man walked from village $$$1$$$ to $$$2$$$, then from $$$2$$$ to $$$3$$$. He could buy $$$3$$$ balls of white pearl, which would cost $$$3$$$ dollars, or he could buy $$$2$$$ balls of black pearl, which would cost $$$2$$$ dollars. Hence, he bought the white pearl which would cost him more money.

In event $$$3$$$, the man could buy $$$2$$$ black pearl balls or $$$1$$$ white pearl ball. Both of them cost $$$1$$$ dollar per ball, so he chose black pearl which would cost him $$$2$$$ dollars.

In event $$$4$$$, the cost of black pearl was changed to $$$10$$$ dollars. Therefore, the man in event $$$5$$$, who travelled the same path as the man in event $$$1$$$, chose black pearls instead. That cost him $$$20$$$ dollars.

In other events, the men only walked past white pearl shop(s). That made the costs in those events equal to $$$\textbf{(sum of purchase limit in each shop)}\times\textbf{(cost of white pearl per ball at the time)}.$$$