P9915 "RiOI-03" 3-2
Background
> Heart beat to death[.](https://www.luogu.com.cn/problem/P9304)
Description
Given a positive integer $n$. Write the lowest $n$ bits of every integer in $[0,2^n)$ in binary, from low to high, into a $2^n \times n$ matrix in order. Both dimensions of the matrix are indexed starting from $0$. For example, when $n=3$, the matrix looks like this:
Given $q$ queries. For each query, ask for the size of the 4-connected component containing the cell at index $(x,y)$ in this matrix, modulo $998244353$.
Input Format
The first line contains two positive integers $n, q$.
The next $q$ lines each contain two non-negative integers $x, y$, representing one query.
Output Format
Output $q$ lines, each containing one positive integer, which is the answer for each query modulo $998244353$.
Explanation/Hint
#### Sample #1 Explanation
The figure shows the matrix when $n=2$, where cells with the same color form a 4-connected component.
***
#### Constraints
**This problem uses bundled testdata.**
| $\text{SubTask}$ | Score | $n\le$ | $q\le$ |
| :----------: | :----------: | :----------: | :----------: |
| $0$ | $5$ | $15$ | $15$ |
| $1$ | $20$ | $15$ | $5\times 10^5$ |
| $2$ | $25$ | $5\times 10^3$ | $5\times 10^3$ |
| $3$ | $50$ | $10^{18}$ | $5\times 10^5$ |
For $100\%$ of the testdata, $0\le y\lt n\le 10^{18}$, $0\le x\lt \min(2^n, 10^{18})$, $1\le q\le 5\times 10^5$.
**Please use fast input/output methods.**
Translated by ChatGPT 5