Range Set Range Composite

Source: Library Checker

Version: Phuoc Hung OJ Extended

Problem Statement

Maintain affine functions modulo $998244353$. Type 0 sets every function in half-open range $[l,r)$ to the same affine function. Type 1 evaluates their ordered composition at $x$.

Input

The first line contains $n,q$. The next $n$ lines contain $a_i,b_i$ for $f_i(x)=a_ix+b_i$. Each query is 0 l r c d (assign the same function to all indices in half-open range $[l,r)$) or 1 l r x (evaluate the ordered composition on $x$). Indices are 0-based.

Output

For each type-1 query print the composed value modulo $998244353$.

Subtasks

• Subtask 1 (20%): size and operation count at most 30; all other validity conditions are unchanged.

• Subtask 2 (30%): size and operation count at most 3000; all other validity conditions are unchanged.

• Subtask 3 (50%): full constraints:

• $1\le n,q\le5\cdot10^5$

• $0\le a_i,b_i,c,d,x<998244353$

• $0\le l<r\le n$

Examples

Input

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

Output

7
6
7

Explanation

Composing the three initial functions at $x=1$ gives 7. After assigning the last two functions, the next two queries give 6 and 7.