시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
3 초 | 512 MB | 10 | 1 | 1 | 100.000% |
As we all know, Master Zhu is the most powerful man in the universe. He has infinite power to protect the world.
A magical rooted tree grows in Master Zhu's garden. The tree contains $n$ vertices and $n - 1$ edges. The root of the tree is in vertex $1$. Each vertex $i$ contains an amount of Zhu power equal to $a_i$.
Little Rikka is a curious girl: she has $m$ questions to ask to Master Zhu. But now Master Zhu is busy protecting our world, so he wants you to help him answer Rikka's questions.
Each Rikka's question has the format "$t$ $u$ $v$ $a$ $b$".
Here, for any $x$, we define $\mathrm{GCD} (x, 0) = \mathrm{GCD} (0, x) = x$.
The first line of input contains an integer $T$, the number of test cases ($1 \le T \le 10$).
The first line of each test case contains two integers $n$ and $m$: the number of vertices in the magical tree and the number of Rikka's questions ($1 \le n, m \le 10^5$).
The next line contains $n$ integers $a_1$, $a_2$, $\ldots$, $a_n$: the amount of Zhu power in each vertex ($1 \le a_i \le 10^9$).
Each of the next $n - 1$ lines contains two integers $u$ and $v$ and denotes an edge connecting vertices $u$ and $v$ ($1 \le u, v \le n$). It is guaranteed that together, these edges form a tree.
Each of the next $m$ lines contains one of Rikka's questions in the format described above ($1 \le u, v \le n$, $1 \le a, b \le n$).
For each Rikka's question, print the answer on a separate line.
1 5 5 1 2 4 1 2 1 2 2 3 3 4 4 5 1 1 1 1 1 1 1 1 1 2 2 1 5 1 1 2 1 5 1 2 2 1 1 2 2
4 1 4 1 0