P3770 [CTSC2017] 密钥
题目描述
一个密钥是一个长度为 n = 2k + 1 的字符串，它包含 1 个字母 X、k 个字母 A 和k 个字母 B。例如 k = 3 时，BAXABAB 就是一个密钥。
如下图所示，可以按顺时针顺序把这 2k+1 个字母排成一个圈：
在 k 个字母 A 中，有一部分可以定义为 “强的’’。具体来说，从 X 出发顺时针走到某个 A 时，如果途中 A 的数目**严格多于**B的数目，则称此字母 A 为强的。
对于上面的例子来说，顺时针方向从字母 X 数起第 1 个和第 2 个字母 A 是强的，而第 3 个字母 A 不是强的。
一个密钥的**特征值**就是其中包含的强的字母 A 的个数。
天才小朋友 KT 给出了一个结论：
假设 k 个字母 A 所在的位置已经固定，但是剩下的 k 个 B 和 1 个 X 的位置是未知的。（注意，满足这样要求的密钥一共有 k + 1 个，因为字母 X 还剩下 k + 1 个可能的位置。）
可以证明：所有这 k + 1 个可能的密钥的特征值是各不相同的，它们恰好为0, 1, 2, …, k。
下面的图是一个具体的示例，从左到右的四个子图中分别有 3 个，2 个，1 个，0个字母 A 是强的。
类似地，如果固定 k 个字母 B 的位置，那满足条件的所有 k + 1 个密钥的特征值也各不相同，恰好为 0, 1, …, k。
现在你需要解决以下三个问题：
1. 给定密钥中所有 A 的位置，当密钥的特征值为 0 时，请问 X 在哪个位置。
2. 给定密钥中所有 A 的位置，当密钥的特征值为 S 时，请问 X 在哪个位置。
3. 给定密钥中所有 B 的位置，当密钥的特征值为 S 时，请问 X 在哪个位置。
注意：字符串的 2k + 1 个字母的位置由 1 到 2k + 1 编号。
【例子 1】
假定 k = 3, S = 2。那么：
当 A 的位置是 {2,4,6} 且特征值为 0 时，X 的位置在 7；
当 A 的位置是 {2,4,6} 且特征值为 2 时，X 的位置在 3；
当 B 的位置是 {2,4,6} 且特征值为 2 时，X 的位置在 5。
【例子 2】
假定 k=9。S=7。那么：
当 A 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 0 时，X 的位置在 14；
当 A 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 7 时，X 的位置在 18；
当 B 的位置是 {3,4,5,9,10,12,13,16,19} 且特征值为 7 时，X 的位置在 17。
输入格式
无
输出格式
无
说明/提示
【样例解释】
第一个样例中, P 数组为 1 的元素的下标分别为 5, 6, 7, 8, 9。
【数据范围与约定】
对于 30% 的数据，k ≤ 10^3。
对于 50% 的数据，k ≤ 10^5。
对于 100% 的数据，k ≤ 10^7。
对于每个测试点, 得分为以下三部分得分之和：
1. 如果第一问回答正确，你将获得 3 分。
2. 如果第二问回答正确，你将获得 4 分。
3. 如果第三问回答正确，你将获得 3 分。
**如果你仅仅知道部分答案，请也务必按此格式要求输出三个数。否则你可能会因格式错误无法得分。**