← 返回题目列表

AtCoder · arc190_b

B. L 分区

中文机器翻译题面 查看原题

分数: 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