Problem Description

There are $ N $ squares numbered from $ 1 $ to $ N $ arranged in a straight line. Among these, $ K $ squares, namely $ B_1, ..., B_K $, have obstacles and cannot be entered.

Takahashi is about to start from square $ 1 $ and head towards square $ N $.

However, there are restrictions on the movement method Takahashi can use. In one move, when Takahashi is on square $ x $, he can only move to one of the squares $ x + D_1, x + D_2, ..., x + D_M $.

He cannot jump to squares with obstacles or outside the $ N $ squares.

When Takahashi moves from square $ x $ to square $ y $ in one move, the cost is the smallest non-negative integer $ i $ that satisfies the following condition:

• None of the integers from $ x + 1 $ to $ y $ are divisible by $ 2^i $.

The cost of a path from square $ 1 $ to square $ N $ is the sum of the costs of each move.

Find the sum of the costs of all possible paths from square $ 1 $ to square $ N $, modulo $ 998244353 $.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ M $ $ B_1 $ $ B_2 $ $\cdots$ $ B_K $ $ D_1 $ $ D_2 $ $\cdots$ $ D_M $

Output Format

Output the sum of the costs of all possible paths from square $ 1 $ to square $ N $, modulo $ 998244353 $.

Sample Input and Output

Sample Input #1

3 1 2
2
1 2

Sample Output #1

2

Sample Input #2

4 1 3
3
1 2 3

Sample Output #2

8

Sample Input #3

4 2 2
2 3
1 2

Sample Output #3

0

Sample Input #4

10 2 4
2 7
1 2 3 9

Sample Output #4

301

Notes/Hints

Constraints

• $3 \leq N \leq 2 \times 10^5$
• $1 \leq K \leq N-2$
• $1 \leq M \leq N-1$
• $1 < B_1 < B_2 < \cdots < B_K < N$
• $0 < D_1 < D_2 < \cdots < D_M < N$
• All inputs are integers.

Sample Explanation 1

The only possible path is from square $ 1 $ to square $ 3 $. The smallest non-negative integer $ i $ that satisfies the condition is $ 2 $, as follows:

• $ 2^1 = 2 $ divides $ 2 $, so $ 1 $ does not satisfy the condition.
• $ 2^2 = 4 $ does not divide $ 2 $ or $ 3 $, so $ 2 $ satisfies the condition.

Thus, the cost of this path is $ 2 $.

Sample Explanation 2

There are two possible paths:

• From square $ 1 $ to square $ 4 $. The cost of this path is $ 3 $.
• From square $ 1 $ to square $ 2 $ and then from square $ 2 $ to square $ 4 $. The cost of this path is $ 2 + 3 = 5 $.

Thus, the sum of the costs of all paths is $ 8 $.

Sample Explanation 3

Since it is impossible to reach square $ 4 $, output $ 0 $.

见题面 Input 部分

见题面 Output 部分