Vào những ngày cuối năm 2025, Gấu Tuyết quyết định trang trí một cây mai khổng lồ để lì xì toàn bộ user của CLAOJ khi sang năm 2026.

Cây mai có ~n~ đỉnh, được kết nối với nhau thông qua các nhánh. Đỉnh thứ ~i~ có treo một phong bao lì xì có giá trị là ~a_i~.

Do Rùa Biển vô tình biết kế hoạch của Gấu Tuyết, Gấu Tuyết đã nói những lời yêu thương với Rùa Biển. Vì vậy, Rùa Biển đã tự nguyện giúp đỡ và được giao ~q~ nhiệm vụ, thuộc 3 loại:

~1~ ~u~ ~v~ : Thay đổi giá trị phong bì tại đỉnh thứ ~u~ thành ~v~.

~2~ ~u~ ~v~ : Kiểm tra xem các giá trị phong bì trên đường từ ~u~ đến ~v~ có giống nhau không. Nếu tất cả bằng nhau thì in Noooo, ngược lại in Happy New Year 2026!.

~3~ ~u~ ~v~ : Gọi dãy ~d_1, d_2, ..., d_i~ là giá trị của phong bì trên đường đi đơn từ ~u~ đến ~v~, tính tổng mọi ~d_i\cdot d_j~ với ~(i < j)~ chia dư cho ~10^9+7~.

Dữ liệu vào

• Dòng đầu tiên gồm hai số nguyên ~n~, ~q~ (~1 \leq n, q \leq 2.10^5~).
• Dòng thứ hai gồm ~n~ số nguyên ~a_1, a_2, ..., a_n~ (~1 \leq a_i \leq 10^9~).
• ~n-1~ dòng tiếp theo, mỗi dòng gồm hai số nguyên ~u~, ~v~ biểu diễn nhánh nối đỉnh ~u~ và ~v~.
• ~q~ dòng cuối cùng, mỗi dòng gồm ba số nguyên ~t~, ~u~, ~v~ biểu diễn truy vấn.

Dữ liệu ra

Ghi ra kết quả của các truy vấn loại 2 và loại 3 theo thứ tự xuất hiện:

• Với truy vấn loại 2: in Noooo nếu tất cả giá trị trên đường bằng nhau, ngược lại in Happy New Year 2026!.
• Với truy vấn loại 3: in ra tổng mọi ~d_i\cdot d_j~ ~(i < j)~ modulo ~10^9+7~.

Ví dụ

Đầu vào

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

Đầu ra

41
68
Happy New Year 2026!
Happy New Year 2026!

Tính điểm

• Subtask ~1~ ~(20~ điểm~) : n, q \leq 100~.
• Subtask ~2~ ~(20~ điểm~)~ : Cây là đường thẳng, ~u_i = i, v_i = i+1~.
• Subtask ~3~ ~(20~ điểm~)~ : Không có truy vấn loại 2.
• Subtask ~4~ ~(40~ điểm~)~ : Không có ràng buộc gì thêm.