题目背景

Heart beat to death.

题目描述

给定一个正整数 $n$。将 $[0,2^n)$ 中每个整数的二进制最低 $n$ 位从低到高依次写在一个 $2^n\times n$ 的矩阵上。矩阵两维的下标都从 $0$ 开始。 如，当 $n=3$ 时，矩阵是这样的：

给定 $q$ 次询问，每次询问这个矩阵下标为 $(x,y)$ 的格子所在的四连通块大小对 $998244353$ 取模的值。

输入格式

第一行两个正整数 $n,q$。

接下来 $q$ 行，每行两个非负整数 $x,y$，表示一次询问。

输出格式

输出 $q$ 行，每行一个正整数，表示每次询问答案对 $998244353$ 取模的值。

2 2
1 1
2 0

3
1

提示

【样例 #1 解释】

图为 $n=2$ 时的矩阵，其中同一个颜色的为一个四连通块。

【数据范围】

本题开启捆绑测试。

对于 $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$。

请选用较快的输入输出方式。