Two Sequence Queries

Source: AtCoder

Version: Phuoc Hung OJ Extended

Problem Statement

Range-add either sequence $A$ or $B$, and query $\sum A_iB_i$ on a range modulo $998244353$.

Input

The first line contains $N,Q$. The next two lines contain sequences $A$ and $B$. Each of the next $Q$ lines is one of 1 l r x, 2 l r x, or 3 l r.

Output

For each type-3 query print the answer 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\le2\cdot10^5$

• $0\le A_i,B_i\le10^9$

• $1\le x\le10^9$

Examples

Input

3 5
1 2 3
4 5 6
3 1 3
1 1 2 10
3 1 2
2 2 3 2
3 1 3

Output

32
104
152

Explanation

Initially $\sum A_iB_i=32$. After adding 10 to $A_1,A_2$, query [1,2] gives 104. After adding 2 to $B_2,B_3$, the full-range sum is 152.