给定一个正方形网格，其格点坐标从 $(0, 0)$ 到 $(n, n)$，以及一个数字 $t$。

你需要回答 $q$ 个查询，格式如下：给定 $A = (x_0, y_0)$ 和 $B = (x_1, y_1)$，求从 $A$ 移动到 $B$ 恰好走 $t$ 步的方法数，使得每一步都从一个格点移动到其相邻格点（上、下、左、右）。计算结果对 $998\,244\,353$ 取模。

输入格式

第一行包含三个整数 $n$ ($1 \le n \le 10^5$)，$t$ ($1 \le t \le 10^9$) 和 $q$ ($1 \le q \le 3 \times 10^5$)。

接下来的 $q$ 行，每行包含四个整数 $x_0, y_0, x_1$ 和 $y_1$ ($0 \le x_0, y_0, x_1, y_1 \le n$)，表示一个查询。

输出格式

对于每个查询，输出一行，包含一个整数，表示该查询的答案对 $998\,244\,353$ 取模的结果。

样例

样例输入 1

2 5 3
0 0 1 2
1 1 2 1
0 0 2 2

样例输出 1

30
64
0

样例输入 2

5 20 5
0 0 5 5
1 1 4 4
2 2 3 3
2 3 2 3
1 2 5 2

样例输出 2

615136704
443203969
899931333
464755094
679729107