Practice on Toph

Participate in exhilarating programming contests, solve unique algorithm and data structure challenges and be a part of an awesome community.

Ajob Commute II

By CLown1331 · Limits 2s, 256 MB

Once again we return to Ajobshohor, the capital city and the heart of Ajobdesh. Ajobshohor’s road system can be represented as a tree. There are n tollbooths, connected with n - 1 roads. Each tollbooth has an x-factor associated with it. The government has issued a new regulation, where every person traveling via that tollbooth has to pay an amount which is determined by a formula of F(x). However, the government can reissue the x-factor associated with any tollbooth, and update it in a single day.

F (x) => F (x -1) * k + F (x - 3) *( k - 2)
F (1) => 1
F (2) => 2
F (3) => 5

John is a freshly graduate software engineer who is relocating to Ajobshohor for his new internship; where he will stay for a duration of q days. Since his company has a rather flexible working environment, John can sometimes work remotely from his home; but on regular days he has to travel from point u to v. For each of the q days, he asks you to either find the total amount spent by John commuting via the tollbooths or update the x-factor of the tollbooth due to reissuance of the government.

So the two types of queries are:

  • Type 1:
    • 1 u v, print the total toll paid by John, going from point u to v.
  • Type 2:
    • 2 u x, update the x-factor of tollbooth u.

As the sum can be quite big, print the sum modulo 109+7.

Input

The first line contains three integers n, q and k ( 1 ≤ n, q ≤ 105, and 1 ≤ k ≤ 50). The second line contains n integers x1, x2, …, xn, where xi is the initial x-factor of the node i. Each of the next n - 1 lines contains two integers ui, vi, ( 1 ≤ ui, vi ≤ n ), meaning there is an edge between ui and vi. Each of the next q lines contains a query as described above.

Constraints

1 ≤ n, q ≤ 105
2 <= k <= 50
1 <= xi <= 1018
1 ≤ ui , vi ≤ n

Output

For each query of type 1, print the sum in a new line.

Samples

InputOutput
5 5 2
4 1 1 4 2
2 1
3 1
5 2
4 1
2 3 3
1 3 4
1 5 1
1 4 3
2 3 4
25
13
25
InputOutput
5 5 3
2 2 3 1 5
5 1
3 1
2 1
4 3
1 4 5
2 1 4
2 1 4
2 5 4
1 1 5
58
32
InputOutput
5 5 5
2 5 3 3 5
2 1
5 4
3 1
4 3
1 1 5
2 4 2
2 2 1
2 2 5
2 1 3
158

Discussion

Statistics


86% Solution Ratio

mahdi.hasnatEarliest, 9M ago

nahid08Fastest, 0.5s

NJRafiLightest, 11 MB

omar24Shortest, 5236B

Submit

Login to submit

Editorial

LCA, Euler Tour + Binary Indexed Tree, Matrix Expo