시간 제한메모리 제한제출정답맞힌 사람정답 비율
3 초 1024 MB157660.000%

문제

크기 $N$의 정사각행렬 $A$가 아래 식을 만족한다.

$1\lt i \le N$일 때 $A_{i,j} = \begin{cases} \max(A_{i-1,j},A_{i-1,j-1}) & \text{if }j>1 \\ \max(A_{i-1,1}, A_{i-1,N}) & \text{if }j=1 \end{cases}$

$A_{1,1}, A_{1,2}, \cdots, A_{1,N}$이 주어질 때, 다음 쿼리를 수행하라.

  • $a$ $b$ $c$ $d$: $\sum_{i=a}^b \sum_{j=c}^d A_{i,j}$를 $998\,244\,353$으로 나눈 나머지를 출력한다.

입력

첫째 줄에 $N$, $Q$가 공백으로 구분되어 주어진다. $(1 \le N, Q \le 200 \, 000)$

둘째 줄에 $A_{1,1}, A_{1,2}, \cdots, A_{1,N}$이 공백으로 구분되어 주어진다. $(1 \le j \le N;$ $0 \le A_{1,j} \lt 998 \, 244 \, 353)$

셋째 줄부터 $Q$개의 줄에 걸쳐 쿼리가 한 줄에 하나씩 주어진다. $(1 \le a \le b \le N;$ $1 \le c \le d \le N)$

입력으로 주어지는 모든 수는 정수이다.

출력

각 줄에 쿼리의 답을 한 줄에 하나씩 순서대로 출력한다.

예제 입력 1

2 5
100 200
1 1 1 1
1 1 2 2
2 2 1 1
2 2 2 2
1 2 1 2

예제 출력 1

100
200
200
200
700

예제 입력 2

5 5
100 200 300 150 300
1 1 1 5
1 5 2 4
1 5 1 5
4 5 4 5
2 4 4 4

예제 출력 2

1050
4150
6950
1200
900