{"raw_statement":[{"iden":"background","content":"> Heart beat to death[.](https://www.luogu.com.cn/problem/P9304)"},{"iden":"statement","content":"给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位**从低到高**依次写在一个 $2^n\\times n$ 的矩阵上。**矩阵两维的下标都从 $0$ 开始。** 如，当 $n=3$ 时，矩阵是这样的：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/5f6v9pru.png?x-oss-process=image/resize,m_lfit,h_200,w_265)\n\n给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。\n"},{"iden":"input","content":"第一行两个正整数 $n,q$。\n\n接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。"},{"iden":"output","content":"输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。"},{"iden":"note","content":"#### 【样例 #1 解释】\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/4mglp4cn.png?x-oss-process=image/resize,m_lfit,h_200)\n\n图为 $n=2$ 时的矩阵，其中同一个颜色的为一个四连通块。\n\n***\n\n#### 【数据范围】\n\n**本题开启捆绑测试。**\n\n| $\\text{SubTask}$ | 分值 | $n\\le$ | $q\\le$ |\n| :----------: | :----------: | :----------: | :----------: |\n| $0$ | $5$ | $15$ | $15$ |\n| $1$ | $20$ | $15$ | $5\\times 10^5$ |\n| $2$ | $25$ | $5\\times 10^3$ | $5\\times 10^3$ |\n| $3$ | $50$ | $10^{18}$ | $5\\times 10^5$ |\n\n对于 $100\\%$ 的数据，$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$。\n\n**请选用较快的输入输出方式。**"}],"translated_statement":null,"sample_group":[["2 2\n1 1\n2 0","3\n1"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}