分数: 800 点
问题陈述
有一个 N \times N 网格。让 (i,j) 表示位于 i从顶部开始的第行和 j左起第 列。
对于 K = 1, 2, \ldots, N,一个 级别 K L 形 是一组 2K - 1 细胞至少满足以下四个条件之一:
- 从某个单元格可到达的所有单元格 (i,j) 通过向下或向右移动 0 和 K-1 单元格,包括在内(其中 1 \leq i \leq N-K+1, 1 \leq j \leq N-K+1).
- 从某个单元格可到达的所有单元格 (i,j) 通过向下或向左移动 0 和 K-1 单元格,包括在内(其中 1 \leq i \leq N-K+1, K \leq j \leq N).
- 从某个单元格可到达的所有单元格 (i,j) 通过在之间向上或向右移动 0 和 K-1 单元格,包括在内(其中 K \leq i \leq N, 1 \leq j \leq N-K+1).
- 从某个单元格可到达的所有单元格 (i,j) 通过向上或向左移动 0 和 K-1 单元格,包括在内(其中 K \leq i \leq N, K \leq j \leq N).
给你一个单元格 (a,b) 和 Q 查询 k_1, \ldots, k_Q.
对于每个 i,打印数字,取模 998244353,将整个网格划分为一层的方法 1 L 形,一层 2 L 形, \ldots,以及一级 N L形使细胞 (a,b) 包含在关卡中 k_i L 形。
约束
- 1 \leq N \leq 10^7
- 1 \leq a \leq N
- 1 \leq b \leq N
- 1 \leq Q \leq \min\lbrace N, 200000 \rbrace
- 1 \leq k_1 < \cdots < k_Q \leq N
- 所有输入值均为整数。
输入
输入由标准输入按以下格式给出:
N a b Q k_1 \cdots k_Q
输出
打印 Q 行。
的 i- 第行应包含数字,模数 998244353,将网格划分为一层的方法 1 L 形,一层 2 L 形, \ldots,以及一级 N L形使细胞 (a,b) 包含在关卡中 k_i L 形。
示例输入 1
3 1 2 1 2
示例输出 1
6
下图所示的六种方式就是解决方案。图中,一个整数 单元格中的 k 表示该单元格属于该级别 k L 形。

示例输入 2
5 2 5 3 1 3 5
示例输出 2
4 32 128
示例输入 3
100 50 50 4 1 10 50 100
示例输出 3
934228871 758172260 444239843 0