3980: 【NOIP2022赛前集训】矩形(rec)
内存限制：512 MB
时间限制：2.000 S
评测方式：文本比较
命题人：
提交：17
解决：2
题目描述
rec.in/out/cpp
## 题目描述
2s，512M。
小 L 现在位于一个 $N\times M$ 的矩形中，他想要逃离但是找不到出路。
我们用 $(i,j)$ 表示第 $i$ 行第 $j$ 列的位置。
小 L 最初可能位于某些位置上，接下来他会移动 $T$ 次，每一次他会在上、下、左、右中选择一个方向，并移动**若干格**。注意，不能停留在原地。
现在小 $L$ 想要知道所有可能的移动 $T$ 次后停留在第 $i$ 行的方案数，和停留在第 $i$ 列的方案数。
两个方案不同，起点不同，或者存在某次移动不相同。
方案数可能很大，小 L 只想知道方案数对 $998244353$ 取模后的结果。
由于矩阵可能非常巨大，所以采用特殊的输入输出方式。
## 输入格式
第一行四个用空格隔开的正整数，表示 $T,N,M,K$。
接下来 $K$ 行，每行两个正整数 $i,j$ ，表示小 $L$ 可能从 $(i,j)$ 开始移动。
数据保证输入的任意两个格子不相同，且按 $i$ 为第一关键字，$j$ 为第二关键字排序。
## 输出格式
为减小输出量，答案按以下方法输出。
我们记 $f_i$ 表示最后停留在第 $i$ 行的方案，记 $g_i$ 表示最后停留在第 $i$ 列的答案。你只需要输出两个数分别表示 $\bigoplus\limits_{i=1}^n(i\times f_i)$ 和 $\bigoplus\limits_{i=1}^m(i\times g_i)$。用一个空格隔开。
**注意**：$\bigoplus$ 表示异或。$f_i,g_i$ 需要对 $998244353$ 取模，但是 $i\times f_i$ 或 $i\times g_i$ **不需要**。
## 样例 #1
### 样例输入 #1
```
2 2 2 2
1 1
1 2
```
### 样例输出 #1
```
12 12
```
## 提示
### 样例解释：
有 $8$ 种可能的方案。
从 $(1,1)$ 出发：
- $(1,1)\to (1,2)\to (2,2)$
- $(1,1)\to (1,2)\to (1,1)$
- $(1,1)\to (2,1)\to (2,2)$
- $(1,1)\to (2,1)\to (1,1)$
从 $(1,2)$ 出发
- $(1,2)\to (1,1)\to (1,2)$
- $(1,2)\to (1,1)\to (2,1)$
- $(1,2)\to (2,2)\to (2,1)$
- $(1,2)\to (2,2)\to (1,2)$
因此 $f_1=f_2=g_1=g_2 = 4$。
样例输入 复制
样例输出 复制