Đất nước XYZ từ lâu đã nổi tiếng về việc trồng táo. Ở đây có ~n~ ngôi làng được đánh số từ ~1~ đến ~n~ và ~n-1~ con đường hai chiều, mỗi con đường nối giữa hai ngôi làng, đảm bảo việc đi lại giữa tất cả các ngôi làng. Ở ngôi làng thứ ~i~ có trồng ~a_i~ cây táo. Để tăng quy mô trồng trọt cũng như đảm bảo lượng táo xuất khẩu, uỷ ban trồng trọt đã lên ~Q~ kế hoạch để trồng thêm táo hoặc để thu hoạch táo. Để thuận tiện cho việc vận chuyển, mỗi kế hoạch đều sẽ gắn với một đường đi. Một kế hoạch trồng thêm táo sẽ là: Chọn ra hai ngôi làng ~u~ và ~v~, sau đó một xe chở cây sẽ đi từ ~u~ đến ~v~ và trồng thêm ~k~ cây táo ở mỗi ngôi làng đi qua (bao gồm cả ~u~ và ~v~); xe sẽ đi theo đường đi sao cho không có ngôi làng nào được đi qua ~2~ lần. Nói cách khác, mỗi kế hoạch trồng thêm táo sẽ tăng ~a_i~ lên ~k~ đơn vị với mọi ~i~ nằm trên đường đi đơn từ ~u~ đến ~v~. Một kế hoạch thu hoạch táo sẽ là: Chọn ra hai ngôi làng ~u~ và ~v~, sau đó một xe chở ~d~ người được thuê và đi từ ~u~ đến ~v~. Khi đến một ngôi làng, ~d~ người này sẽ chia đều số cây táo ở ngôi làng đó để hái. Để không gây lãng phí nhân lực nhưng vẫn đảm bảo tốc độ thu hoạch, số ~d~ được chọn là số lớn nhất có thể sao cho số lượng cây táo ở mỗi ngôi làng đều chia hết cho ~d~. Nói cách khác, ~d~ là ước chung lớn nhất của các ~a_i~ với ~i~ nằm trên đường đi đơn từ ~u~ đến ~v~. Lưu ý là việc thu hoạch táo không ảnh hưởng đến số lượng cây táo cho quả, vì táo ở đây sẽ chín theo từng ngày. Tức là ~a_i~ sẽ không thay đổi sau các kế hoạch thu hoạch táo.

Cho ~Q~ kế hoạch như trên, hãy giúp uỷ ban trồng trọt tính toán số người cần thuê trong các kế hoạch thu hoạch táo.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~n, Q~.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~.

• Mỗi dòng trong số ~n-1~ dòng tiếp theo chứa hai số nguyên ~x, y~ cho biết có một con đường hai chiều giữa ngôi làng ~x~ và ngôi làng ~y~.

• Dòng tiếp theo chứa ~n~ số nguyên dương ~a_1, a_2, \dots, a_n~.

• Mỗi dòng trong số ~Q~ dòng tiếp theo mô tả cho một kế hoạch, có dạng: 1 ~u~ ~v~ ~k~ hoặc 2 ~u~ ~v~ tương ứng là trồng thêm ~k~ cây táo ở mỗi ngôi làng trên đường đi đơn từ ~u~ đến ~v~ hoặc thu hoạch táo ở các ngôi làng trên đường đi đơn từ ~u~ đến ~v~.

Output

Với mỗi kế hoạch thu hoạch táo, in ra trên một dòng số ~d~ là số người cần thuê để hái táo.

Scoring

Trong tất cả các test: ~1 \le n, Q \le 10^5~; ~1 \le k, a_i \le 10^4~.

Sample Input 1

6 6
4 3 2 5 3 4
1 2
1 3
2 4
2 5
3 6
2 4 5
2 2 6
1 2 2 3
2 2 6
1 4 6 4
2 4 5

Sample Output 1

1
1
2
1