주 대가와 리카

모두가 알다시피, 주 대가는 우주에서 가장 강한 사람이다. 그는 세계를 지킬 무한한 힘을 가진다.

주 대가의 정원에는 마법의 뿌리 있는 트리가 자란다. 트리는 $n$개의 정점과 $n - 1$개의 간선으로 이루어져 있다. 트리의 뿌리는 정점 $1$이다. 각 정점 $i$에는 $a\_i$만큼의 주 파워가 담겨 있다.

꼬마 리카는 호기심 많은 소녀로, 주 대가에게 물어볼 질문이 $m$개 있다. 하지만 지금 주 대가는 세계를 지키느라 바쁘기 때문에, 리카의 질문에 답하는 일을 당신에게 맡기려 한다.

리카의 각 질문은 "$t$ $u$ $v$ $a$ $b$" 형식이다.

• $t$가 $1$이면 $u$는 $v$와 같고, 리카는 정점 $u$를 뿌리로 하는 부분 트리를 보며 $S\_a$와 $S\_b$의 최대공약수(GCD)를 알고 싶어 한다. 여기서 $S\_a$는 이 부분 트리에서 정확히 $a$번 나타나는 수들의 합이고, $S\_b$는 정확히 $b$번 나타나는 수들의 합이다.
• $t$가 $2$이면 리카는 정점 $u$와 $v$ 사이의 단순 경로를 보며 $T\_a$와 $T\_b$의 최대공약수를 알고 싶어 한다. 여기서 $T\_a$는 이 경로에서 정확히 $a$번 나타나는 수들의 합이고, $T\_b$는 정확히 $b$번 나타나는 수들의 합이다.

여기서 모든 $x$에 대해 $\mathrm{GCD} (x, 0) = \mathrm{GCD} (0, x) = x$로 정의한다.

첫째 줄에는 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 10$).

각 테스트 케이스의 첫째 줄에는 두 정수 $n$과 $m$이 주어진다. 각각 마법의 트리에 있는 정점의 수와 리카의 질문 수이다 ($1 \le n, m \le 10^5$).

다음 줄에는 $n$개의 정수 $a\_1$, $a\_2$, $\ldots$, $a\_n$이 주어진다. 각 정점에 담긴 주 파워의 양이다 ($1 \le a\_i \le 10^9$).

다음 $n - 1$개의 줄에는 각각 두 정수 $u$와 $v$가 주어지며, 정점 $u$와 $v$를 잇는 간선을 나타낸다 ($1 \le u, v \le n$). 이 간선들이 트리를 이룬다는 것이 보장된다.

다음 $m$개의 줄에는 위에서 설명한 형식의 리카의 질문이 하나씩 주어진다 ($1 \le u, v \le n$, $1 \le a, b \le n$).

리카의 각 질문에 대해 답을 한 줄에 하나씩 출력한다.