Gán điểm và hợp thành hàm trên đoạn (Point Set Range Composite)

Nguồn: Library Checker

Phiên bản: Phước Hưng OJ Extended

Cho $N$ hàm bậc nhất theo thứ tự $f_0,f_1,\ldots,f_{N-1}$, trong đó:

$$f_i(x)=a_i x+b_i \pmod{998244353}.$$

Có $Q$ truy vấn:

• 0 p c d: thay $f_p$ bằng hàm $f_p(x)=cx+d$.
• 1 l r x: tính

$$f_{r-1}(f_{r-2}(\cdots f_l(x)\cdots))\pmod{998244353}.$$

Chỉ số dùng hệ $0$ và đoạn truy vấn là nửa mở $[l,r)$.

Input

Dòng đầu chứa $N,Q$.

$N$ dòng tiếp theo chứa $a_i,b_i$.

$Q$ dòng tiếp theo mô tả truy vấn.

Output

Với mỗi truy vấn loại 1, in giá trị hàm hợp tại $x$ theo modulo $998244353$.

Subtask

• Subtask 1 — 20%: $1\le N,Q\le 50$.
• Subtask 2 — 30%: $1\le N,Q\le 5000$.
• Subtask 3 — 50%: $1\le N,Q\le 5\cdot10^5$.

Mọi hệ số và $x$ nằm trong $[0,998244353)$.

Ví dụ

Input

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

Output

18
8
7

Giải thích

Ban đầu hợp thành ba hàm tại $x=1$ cho $18$. Sau khi thay hàm thứ $1$ bằng hàm đồng nhất $f(x)=x$, hai truy vấn tiếp theo lần lượt cho $8$ và $7$.