There are $m$ balls, numbered $1$ to $m$, each of which is either black or white. Initially, all balls are white.
You are to perform $n$ operations. Each operation consists of flipping the color of one ball (from black to white, or from white to black).
You must ensure that after the $i$-th operation, only balls with a number $\le a_i$ can be black, while balls with a number $> a_i$ must be white.
Find the number of different valid sequences of operations, modulo $998244353$. Two operation sequences are considered different if and only if the ball chosen in at least one operation is different.
Furthermore, you need to process $q$ modifications. Each modification is given as: change $a_{x_i}$ to $y_i$, and then find the answer for the current array $a$.
Input
The first line contains $n, m, q$.
The second line contains $n$ integers, representing $a_i$.
The next $q$ lines each contain two integers $x_i, y_i$.
Output
Output $q$ lines, each containing the answer for the current state.
Examples
Input 1
3 3 2 1 3 1 3 2 1 3
Output 1
5 14
Input 2
6 8 1 3 8 7 7 1 6 1 4
Output 2
2100
Input 3
12 10 8 1 3 2 6 3 6 7 7 5 5 4 7 12 4 7 10 4 2 9 8 9 9 8 3 4 9 10 2
Output 3
2741280 3007680 1503840 1916160 1972800 728640 1821600 621440
Input 4~6
See the provided files.
Constraints
For all test cases, $n, q \le 3 \times 10^4$, $m \le 15$, $1 \le a_i, y_i \le m$, $1 \le x_i \le n$.
The additional constraints for each subtask are as follows:
| Subtask ID | $n \le$ | $m \le$ | $q \le$ | Score |
|---|---|---|---|---|
| $1$ | $5$ | $5$ | $10$ | $4$ |
| $2$ | $2000$ | $10$ | $1$ | $6$ |
| $3$ | $30000$ | $10$ | $1$ | $8$ |
| $4$ | $30000$ | $15$ | $1$ | $24$ |
| $5$ | $30000$ | $15$ | $10$ | $12$ |
| $6$ | $30000$ | $7$ | $30000$ | $14$ |
| $7$ | $30000$ | $10$ | $30000$ | $16$ |
| $8$ | $30000$ | $15$ | $30000$ | $16$ |