题目描述

2s，512M，rec.in，rec.out。

小 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)$ 开始移动。

数据保证输入的任意两个格子不相同。

输出格式

为减小输出量，答案按以下方法输出。

我们记 $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

样例输入 #2

3 4 5 2
1 2
4 3

样例输出 #2

699 182

提示

样例1解释：

有 $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$。

数据范围与约定

对于 $100\%$ 的数据，保证 $T\le 10^{18}$，$N,M\le 10^6$，$1\le K\le \min\{10^6,N\times M\}$。