Background

Father, your kingdom is collapsing.

Father, your people are leaving.

Father, but you said I should not have a voice to cry for suffering.

So I can do nothing, so I fall apart alone.

Problem Description

There are $n$ infected people in front of the container. These $n$ infected people stand in a line, numbered from $1$ to $n$ in order. The infection depth of the $i$-th infected person is $a_i$.

The container starts from the $x$-th infected person and walks towards the $n$-th infected person, passing through the infected people from $x$ to $n$ in order. The container will kill all infected people it passes. However, if it kills two infected people whose indices are consecutive and whose infection depths are strictly increasing, then it will skip the next infected person (if the next one exists).

Let $f_x$ denote the number of infected people killed when the container starts from position $x$ (all $f$ are pairwise independent). For example, if there are five infected people with infection depths:

2 6 4 5 1

then the corresponding $f$ sequence is $\{4,3,2,2,1\}$.

You do not know the infection depth of each infected person. You only know the values of $f_i-f_{i+1}$ for $m$ pairs. Please output, modulo $998244353$, the number of different $f$ sequences that satisfy the conditions.

Two sequences $f,g$ are different if and only if there exists $1 \le i \le n$ such that $f_i \not= g_i$.

Input Format

The first line contains two integers $n,m$.

In the next $m$ lines, each line contains a pair $(x,y)$, meaning $f_x-f_{x+1}=y$.

Note that the input may contain incorrect pairs, and you need to ignore them by yourself. Specifically, if a pair $(x_i,y_i)$ makes it impossible to have any valid $f$ sequence after considering all valid pairs among $1 \sim i-1$ and this pair, then this pair is invalid, and you should not consider it when computing the answer.

Output Format

Output $(m+1)$ lines, one number per line.

The first line is the answer modulo $998244353$ when no pairs are considered.

The $i$-th line ($2 \le i \le m+1$) is the answer modulo $998244353$ after considering all valid pairs among $1 \sim i-1$.

3 3
1 5
1 1
1 0

2
2
1
1

5 2
2 1
4 5

4
3
3

Hint

Explanation for Sample 1

Initially, the valid $f$ sequences are $\{3,2,1\}$ and $\{2,2,1\}$.

Constraint 1: None of the initial $f$ sequences satisfies constraint 1, so ignore this constraint.

Constraint 2: Only $\{3,2,1\}$ satisfies the constraint.

Constraint 3: Only $\{2,2,1\}$ satisfies the constraint. Together with constraint 2, there is no valid $f$ sequence, so ignore this constraint.

Constraints and Notes

For $20\%$ of the testdata, $n,m \le 5$.

For $60\%$ of the testdata, $n \le 10^6$.

For another $10\%$ of the testdata, $m=0$.

For $100\%$ of the testdata, $1 \leq n \leq 10^{11}, 0 \leq m \leq 5\times 10^4, 0 \leq |y| \leq n, 1 \leq x < n$.

Translated by ChatGPT 5