Cho một cây có \(N\) đỉnh. Các cạnh của cây là \((u_i,v_i)\) và một hàm tuyến tính \(f_i(x)=a_i x + b_i\) được viết trên đỉnh \(i\) cho mỗi \(i\). Hãy xử lý \(Q\) truy vấn như sau:

• "0 p c d": Thiết lập \(f_p \leftarrow cx + d\) (nghĩa là cập nhật hàm tuyến tính tại đỉnh \(p\) thành \(cx+d\)).
• "1 u v x": Xét các đỉnh trên đường đi \(u\) và \(v\) là \(p_1 = u, p_2,...p_k=v\). In ra giá trị của \(f_{pk}(..(f_{p2}(f_{p1}(x))))\) mod \(998244353\)

Ràng buộc

• \(1 \le N,Q \le 2 \times 10^5\)
• \(1 \le a_i, c \lt 998244353\)
• \(0 \le b_i,d,x \lt 998244353\)
• \(0 \le p,u,v \lt N\)

Dữ liệu vào

• \(N\) \(Q\)
• \(a_0\) \(b_0\)
• ..
• \(a_{N-1}\) \(b_{N-1}\)
• \(u_0\) \(v_0\)
• \(u_1\) \(v_1\)
• ..
• \(u_{N-2}\) \(v_{N-2}\)
• \(Query_0\)
• \(Query_0\)
• ..
• \(Query_{Q-1}\)

Input 1

5 5
1 2
3 4
5 6
7 8
9 10
0 1
1 2
2 3
2 4
1 0 3 11
1 2 4 12
0 2 13 14
1 0 4 15
1 2 2 16

Output 1

1555
604
6571
222

Input 2

7 7
1 2
2 3
3 4
4 5
5 6
6 7
7 8
0 1
1 2
0 3
3 4
0 5
5 6
1 2 4 1
1 4 6 1
1 6 2 1
0 1 20 30
1 2 4 1
1 4 6 1
1 6 2 1

Output 2

411
2199
607
3471
2199
6034