C. 特工潜行

题目描述

某秘密基地有 $n$ 间连通的密室排成竖列：

• 密室编号从 $1$ 到 $n$（$1$ 号在最上层，$n$ 号在最底层）。
• 一名特工（代号“夜影”）初始位于第 $m$ 号密室。

基地会依次执行 $q$ 次安防调整：

1. 第 $i$ 次调整时：
   • 系统会强制迁移第 $a_i$ 号密室（含其中人员）。
   • 迁移方向有两种可能：
     • 迁至 顶层通道口（成为新的 $1$ 号密室）。
     • 迁至 底层通道口（成为新的 $n$ 号密室）。
2. 原密室序列将按照相应顺序重组。

对于初始密室序列：$[2, 1, 3, 5, 4]$，$a_i = 2$ 进行迁移：

• 迁至顶层：序列变为 $[1, 2, 3, 5, 4]$。
• 迁至底层：序列变为 $[2, 3, 5, 4, 1]$。

每次安防调整后，需要计算：

• “夜影”特工可能藏身的 不同密室编号总数。
• 注意：由于系统迁移方向未知，需考虑所有可能路径。

输入格式

第一行包含一个整数 $t$，表示测试样例数量。

对于每一组测试样例，第一行包含三个整数 $n$，$m$，$q$。第二行包含 $q$ 个整数 $a_1$，$a_2$，$\ldots$，$a_q$。

输出格式

对于每一组测试样例，输出 $q$ 个整数，表示对应操作后，“夜影”特工可能藏身的不同密室编号总数。

样例输入1

5
6 5 3
1 2 3
2 1 4
2 1 1 2
5 3 1
3
3 2 4
2 1 1 1
18 15 4
13 15 1 16

样例输出1

5
6 5 3
1 2 3
2 1 4
2 1 1 2
5 3 1
3
3 2 4
2 1 1 1
18 15 4
13 15 1 16

样例解释

对于第三组测试样例，“夜影”特工初始位于第 $3$ 号密室，在第一次操作后，“夜影”特工可能位于 $1$ 号密室上方或 $5$ 密室下方，总共两个可能的位置

数据范围

• 对于 $10\%$ 的数据，$2 \le n \le 10$，$1 \le m \le n$，$1 \le \sum q \le 10$，$1 \le a_i \le n$。
• 对于 $70\%$ 的数据，$2 \le n \le 10^3$，$1 \le m \le n$，$1 \le \sum q \le 10^3$，$1 \le a_i \le n$。
• 对于 $100\%$ 的数据，$2 \le n \le 10^9$，$1 \le m \le n$，$1 \le \sum q \le 2 \times 10^5$, $1 \le a_i \le n$。