Umaru's older brother Taihei is off to work again, which means it is time for her to sit back, relax, play some video games, and enjoy delicious snacks including potato chips and cola. Taihei has been trying to teach Umaru the importance of sharing, so to put this into practice, she will be buying bags of chips to distribute to her friends.
The town Umaru lives in can be modeled as a set of $$$N$$$ houses and $$$N - 1$$$ roads such that there is a unique simple (no edges or nodes reused) path between any two houses. Additionally, Umaru has $$$a_i$$$ friends that live in the $$$i$$$-th house. Taihei will be gone for $$$Q$$$ hours, so Umaru plans to go on at most $$$Q$$$ "snack runs". At the $$$i$$$-th point in time (for each $$$i$$$ at most $$$Q$$$), one of two things may happen. The first possibility is that Umaru will go on a snack run. If so, Umaru travels from house $$$u_i$$$ to house $$$v_i$$$ and gives snacks to her friends along the way. If not, she tells her friends to gather at a particular house $$$w_i$$$, in which case the number of friends that live at house $$$w_i$$$ becomes multiplied by a factor of $$$f_i$$$ (these friends come from out of town, friends never leave their houses).
Umaru is having trouble figuring out how many snacks to bring with her on each snack run. Being lazy, she wants to bring the smallest positive integer number of snacks that will be evenly divisible by the number of people in each of the houses that she visits along the way (including her starting city and destination). Given information regarding each of her snack runs, can you help her figure out how many snacks to bring?
The input will begin with two integers, $$$N$$$ and $$$Q$$$ ($$$1 \leq N, Q \leq 10^3$$$), the number of houses and the number of snack runs, respectively.
The next line will contain $$$N$$$ integers, the $$$i$$$-th of which represents $$$a_i$$$ ($$$1 \leq a_i \leq 10^7$$$), the number of friends of Umaru who live in the $$$i$$$-th house.
The $$$i$$$-th of each of the next $$$N - 1$$$ lines will each contain two integers, $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i, \leq N, u_i \neq v_i$$$), meaning that houses $$$u_i$$$ and $$$v_i$$$ are connected by a (bidirectional) road.
The $$$i$$$th of each of the final $$$Q$$$ lines will each contain three integers, either a 1 followed by $$$u_i$$$ and $$$v_i$$$ ($$$1 \leq u_i, v_i \leq N$$$), denoting that the $$$i$$$-th snack run is between houses $$$u_i$$$ and $$$v_i$$$, or a 2 followed by $$$w_i$$$ and $$$f_i$$$ ($$$1 \leq w_i \leq N, 1 \leq f_i \leq 10^7$$$). It is guaranteed that there will be at least one type 1 snack run in the input.
The output should consist of as many lines as there are type 1 snack runs, the $$$i$$$-th of which denotes the minimum positive integer number of snacks that Umaru can bring from house $$$u_i$$$ to $$$v_i$$$ such that the number of snacks is divisible by the number of people living in each of the houses in the unique simple path from house $$$u_i$$$ to house $$$v_i$$$. Note that, since the answers may be quite large, print them modulo $$$10^9+7$$$.
6 3 1 6 5 3 4 3 1 2 1 3 1 4 2 5 4 6 1 1 5 2 2 4 1 1 2
12 24
For the first snack run, the houses along the way are 1, 2, and 5 which house 1, 6, and 4 people, respectively. The smallest positive integer which is divisible by 1, 6, and 4 is 12.
For the second snack run, the number of friends that live at house 2 is multiplied by a factor of 4, so now 24 friends of Umaru's live at house 2.
For the third snack run, the houses along the way are 1 and 2 which house 1 and 24 people, respectively. The smallest positive integer which is divisible by 1 and 24 is 24.
