Đất nước XYZ 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. 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.

• Một kế hoạch trồng thêm táo: Chọn ra hai ngôi làng ~u~ và ~v~, 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: Chọn ra hai ngôi làng ~u~ và ~v~, thuê ~d~ người để hái táo, trong đó ~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~.

Yêu cầu: Với mỗi kế hoạch thu hoạch táo, hãy tính số người ~d~ cần thuê.

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 hoặc thu hoạch táo 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.

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