B - L Partition Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 800 点

問題文

N\times N のマス目があります．上から i 行目，左から j 列目のマスを (i,j) で表します．

K=1,2,\ldots,N に対して，レベル K の L 型とは，2K-1 個からなるマスの集合であって次の 4 つのうち 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 に対して，マス目全体をレベル 1, \ldots, N それぞれひとつずつの L 型に分割する方法であって，マス (a,b) がレベル k_i の L 型に含まれるようなものの個数を 998244353 で割った余りを答えてください．

制約

  • 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 行目にはマス目全体をレベル 1, \ldots, N それぞれひとつずつの L 型に分割する方法であって，マス (a,b) がレベル k_i の L 型に含まれるようなものの個数を 998244353 で割った余りを出力してください．

入力例 1

3 1 2
1
2

出力例 1

6

以下の図で表される 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

Score : 800 points

Problem Statement

There is an N \times N grid. Let (i,j) denote the cell at the i-th row from the top and the j-th column from the left.

For K = 1, 2, \ldots, N, a level K L-shape is a set of 2K - 1 cells that satisfies at least one of the following four conditions:

  • All cells reachable from a certain cell (i,j) by moving down or right between 0 and K-1 cells, inclusive (where 1 \leq i \leq N-K+1, 1 \leq j \leq N-K+1).
  • All cells reachable from a certain cell (i,j) by moving down or left between 0 and K-1 cells, inclusive (where 1 \leq i \leq N-K+1, K \leq j \leq N).
  • All cells reachable from a certain cell (i,j) by moving up or right between 0 and K-1 cells, inclusive (where K \leq i \leq N, 1 \leq j \leq N-K+1).
  • All cells reachable from a certain cell (i,j) by moving up or left between 0 and K-1 cells, inclusive (where K \leq i \leq N, K \leq j \leq N).

You are given a cell (a,b) and Q queries k_1, \ldots, k_Q.

For each i, print the number, modulo 998244353, of ways to partition the entire grid into exactly one level 1 L-shape, one level 2 L-shape, \ldots, and one level N L-shape so that cell (a,b) is contained in the level k_i L-shape.

Constraints

  • 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
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N a b
Q
k_1 \cdots k_Q

Output

Print Q lines.

The i-th line should contain the number, modulo 998244353, of ways to partition the grid into exactly one level 1 L-shape, one level 2 L-shape, \ldots, and one level N L-shape so that cell (a,b) is contained in the level k_i L-shape.

Sample Input 1

3 1 2
1
2

Sample Output 1

6

The six ways shown in the following figure are the solutions. In the figure, an integer k in a cell means that the cell belongs to the level k L-shape.

Sample Input 2

5 2 5
3
1 3 5

Sample Output 2

4
32
128

Sample Input 3

100 50 50
4
1 10 50 100

Sample Output 3

934228871
758172260
444239843
0