Dế Mèn có một bài toán thú vị về cây như sau: cậu có một cây gồm ~n~ đỉnh, đỉnh thứ ~i~ có một hàm tuyến tính ~f_i(x) = a_i x + b_i~ và cạnh thứ ~i~ nối đỉnh ~u_i~ với ~v_i~. Bạn phải xử lý ~q~ truy vấn sau:

• ~0~ ~p~ ~c~ ~d~: Gán ~f_p~ thành ~cx + d~.

• ~1~ ~u~ ~v~ ~x~: Coi các đỉnh trên đường đi từ ~u~ đến ~v~ lần lượt là ~p_1 = u~, ~p_2~, ~\cdots~, ~p_k = v~. Tính ~f_{p_k}(...f_{p_2}(f_{p_1}(x)))~ ~\bmod~ ~998244353~

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ — số đỉnh và số truy vấn.

• Trong ~n~ dòng sau, dòng thứ ~i~ gồm hai số nguyên ~a_i, b_i~ — chỉ số hàm tuyến tính của đỉnh ~i~.

• Trong ~n - 1~ dòng kế tiếp, dòng thứ ~i~ gồm hai số nguyên ~u_i, v_i~ — cạnh ~i~ nối hai đỉnh ~u_i~ và ~v_i~.

• Trong ~q~ dòng cuối cùng, truy vấn ~i~ thuộc một trong hai loại trên.

Constraints

• ~1 \le n, q \le 2 \times 10^5~

• ~1 \le a_i, c < 998244353~

• ~0 \le b_i, d, x < 998244353~

• ~1 \le p, u, v \le n~

• ~1 \le u_i, v_i \le n~

Output

Với mỗi truy vấn ~1~ in ra kết quả trên một dòng.

Scoring

Sample Input 1

4 3
1 5
4 0
1 1
3 2
1 3
2 4
3 4
1 1 4 3
0 3 2 1
1 4 4 4

Sample Output 1

29
14

Notes

Ở truy vấn thứ nhất, ta có ~f_{4}(f_{3}(f_{1}(x))) = 3(1(1x + 5) + 1) + 2 = 3(1(3 + 5) + 1) + 2 = 29~

Ở truy vấn thứ hai, ta đặt ~f_{3}(x) = 2x + 1~

Ở truy vấn thứ ba, vì đường đi chỉ có một đỉnh nên ta có ~f_{4}(x) = 3x + 2 = 3 \cdot 4 + 2 = 14~