Point Set Range Composite

Source: Library Checker

Version: Phuoc Hung OJ Extended

You are given $N$ affine functions $f_0,f_1,\ldots,f_{N-1}$ in order:

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

Process $Q$ queries:

• 0 p c d: replace $f_p$ by $f_p(x)=cx+d$.
• 1 l r x: compute

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

Indices are zero-based and the query range is half-open: $[l,r)$.

Input

The first line contains $N,Q$.

The next $N$ lines contain $a_i,b_i$.

The next $Q$ lines describe the queries.

Output

For every type 1 query, print the composed function evaluated at $x$ modulo $998244353$.

Subtasks

• 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$.

Every coefficient and query value $x$ is in $[0,998244353)$.

Examples

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

Explanation

The sample follows the operations exactly; each printed line corresponds to a query that requires output.