Don't play HSR! But Firefly so cute :3

MACKSAY đang trên đường khai phá cùng đội tàu Astral. Họ vừa đến Xianzhou Luofu thì Feixiao và Jing Yuan đã giao cho họ một nhiệm vụ rất khó, đó là tính toán tất cả sức mạnh giữa các Mỏ neo không gian.

Các Mỏ neo hình thành một đồ thị dạng cây ~N~ đỉnh, với ~N - 1~ đường đi. Đường đi nối giữa hai Mỏ neo ~u_i~ và ~v_i~ có khoảng cách là ~d_i~. Mỗi Mỏ neo ~i~ có một chỉ số gọi là sức mạnh không gian ~A_i~. Sức mạnh của đường đi giữa hai mỏ neo ~u~ và ~v~ được tính bằng công thức ~f(u,v) = s(u,v) \times dist(u,v)~, trong đó ~s(u,v)~ là tổng các ước chung của ~A_u~ và ~A_v~ và ~dist(u,v)~ là độ dài đường đi ngắn nhất giữa ~u~ và ~v~.

Tướng quân Feixiao và Jing Yuan muốn các bạn tính tổng của ~f(i,j)~ với mọi ~1 \leq i < j \leq N~.

MACKSAY ngay lập tức gọi Firefly (người yêu của anh!) đến ứng cứu. Và Firefly, tất nhiên với trí thông minh và sự xinh đẹp của mình, đã giải xong bài toán trong ~0.2~ giây! Vậy còn các bạn, liệu các bạn có giải được bài toán này?

Input

• Dòng đầu chứa số nguyên dương ~N, \ (1 \leq N\leq 150000)~.
• Dòng thứ hai chứa ~N~ số nguyên dương ~A_1, A_2, \dots, A_N \ (1 \leq A_i \leq 150000)~ là chỉ số sức mạnh của các Mỏ neo không gian.
• ~N-1~ dòng tiếp theo là các số nguyên dương ~u_i~, ~v_i~ và ~d_i~ ~(1 \le u_i, v_i \le N, \ u_i \neq v_i,\ 1 \le d_i \le 10^9)~ tương ứng với các cạnh của cây.

Output

• In ra một số nguyên duy nhất là đáp án của bài toán. Vì kết quả có thể rất lớn, hãy in ra phần dư của đáp án sau khi chia ~998244353~.

Scoring

• Subtask 1 ~(11p)~: ~N \leq 300~.
• Subtask 2 ~(16p)~: ~N \leq 2000~.
• Subtask 3 ~(27p)~: ~A_1 = A_2 = \ldots = A_N~.
• Subtask 4 ~(27p)~: ~u_i + 1 = v_i~ với ~i = 1, 2, \ldots, N - 1~.
• Subtask 5 ~(19p)~: Không có giới hạn gì thêm.

Sample Input 1

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

Sample Output 1

71

Notes

• ~f(1, 2) = 2~, ~f(1, 3) = 4~, ~f(1, 4) = 5~, ~f(1, 5) = 1~
• ~f(2, 3) = 6~, ~f(2, 4) = 3~, ~f(2, 5) = 9~
• ~f(3, 4) = 20~, ~f(3, 5) = 15~
• ~f(4, 5) = 6~