Ghép Hàm Trên Đường · canuc80k5816

Đặt $MOD = 998244353$ . Cho một cây gồm $n$ đỉnh, đánh số từ $0$ đến $n - 1$ . Tại đỉnh $i$ có hàm affine

f_{i} (x) = a_{i} \cdot x + b_{i} (mod MOD) .

Bạn cần xử lý $q$ thao tác:

$0$ $p$ $c$ $d$ : thay hàm tại đỉnh $p$ bằng $f_{p} (x) = c \cdot x + d (mod MOD)$ ;
$1$ $u$ $v$ $x$ : đi theo đường đơn từ $u$ đến $v$ , lần lượt áp dụng hàm tại từng đỉnh vào giá trị hiện tại. Hàm tại $u$ được áp dụng đầu tiên và hàm tại $v$ được áp dụng cuối cùng. In giá trị thu được modulo $MOD$ .

Cả hai đầu mút của đường đều được tính. Vì phép hợp hàm không giao hoán, thứ tự từ $u$ đến $v$ là một phần của truy vấn.

Input

Dòng đầu chứa hai số nguyên $n$ và $q$ .
Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $a_{i}$ và $b_{i}$ , mô tả hàm ban đầu tại đỉnh $i$ , theo thứ tự $i = 0, 1, \dots, n - 1$ .
Mỗi dòng trong $n - 1$ dòng tiếp theo chứa hai số nguyên $u$ và $v$ , biểu diễn một cạnh của cây.
Mỗi dòng trong $q$ dòng cuối có một trong hai dạng $0$ $p$ $c$ $d$ hoặc $1$ $u$ $v$ $x$ .

Output

Với mỗi thao tác loại $1$ , in kết quả của phép áp dụng tuần tự, mỗi đáp án trên một dòng.

Constraints

$1 \leq n, q \leq 2 \cdot 1 0^{5}$ ;
$MOD = 998244353$ ;
$1 \leq a_{i}, c < MOD$ ;
$0 \leq b_{i}, d, x < MOD$ ;
$0 \leq p, u, v < n$ ;
các cạnh tạo thành một cây.

Scoring

Subtask $1$ ( $50$ điểm): $n, q \leq 40$ ;
Subtask $2$ ( $50$ điểm): không có giới hạn bổ sung.

Example

Test 1

Input

Output

Giải thích: Với truy vấn đầu, đường là $3 - 1 - 0 - 2$ ; giá trị $1$ lần lượt biến thành $4, 12, 25$ , rồi $29$ . Sau khi hàm tại đỉnh $1$ được đổi thành $x + 5$ , cùng đường đó biến $1$ thành $4, 9, 19$ , rồi $23$ .

1. Biểu diễn phép hợp: Một hàm affine được lưu bằng cặp (a,b), nghĩa là f(x)=a·x+b (mod MOD). Gọi concatenate(f,g) là hàm nhận được khi áp dụng f trước rồi áp dụng g:
1. Biểu diễn phép hợp:

text g(f(x)) = (g.a · f.a) x + (g.a · f.b + g.b) (mod MOD). - 1. Biểu diễn phép hợp: Phép hợp hàm có tính kết hợp nhưng không giao hoán, vì vậy thứ tự trên đường phải được giữ nguyên. - 2. Thông tin trong segment tree: Mỗi node lưu hai hàm: - 2. Thông tin trong segment tree: forward: hợp các hàm từ trái sang phải trong đoạn; - 2. Thông tin trong segment tree: backward: hợp các hàm từ phải sang trái. - 2. Thông tin trong segment tree: Khi ghép đoạn trái L với đoạn phải R: - 2. Thông tin trong segment tree:

text forward = concatenate(L.forward, R.forward) backward = concatenate(R.backward, L.backward) - 2. Thông tin trong segment tree: Đảo hướng một đoạn chỉ cần đổi chỗ forward và backward. Cập nhật loại 0 là point set tại vị trí HLD của đỉnh. - 3. Truy vấn đường có hướng: Heavy-Light Decomposition tách đường u→v thành O(log n) đoạn. Ta dùng hai biến tích lũy: một biến nối các đoạn lấy từ phía u, một biến chèn các đoạn lấy từ phía v về đúng đầu. Những đoạn đi từ dưới lên được đảo bằng trường backward. - 3. Truy vấn đường có hướng: Sau khi nối toàn bộ, forward chính là hàm tổng hợp theo thứ tự từ u đến v. Với cặp (A,B), đáp án là (A·x+B) mod MOD. - 4. Đúng đắn và độ phức tạp: Mỗi node segment tree mô tả đúng phép hợp theo cả hai hướng nhờ tính kết hợp của hợp hàm. Quy trình HLD ghép đúng thứ tự từng đỉnh trên đường nên hàm cuối trùng với việc áp dụng tuần tự theo đề. Point set mất O(log n); path query mất O(log² n); bộ nhớ O(n).