← 返回题目列表

Codeforces · 1956/A

A. 内内的游戏

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

Nene 发明了一种基于整数递增序列 $$$a_1, a_2, \ldots, a_k$$$ 的新游戏。

在这个游戏中,最初 $$$n$$$ 玩家排成一排。在本游戏的每一轮中,都会发生以下情况:

- Nene 找到连续第 $$$a_1$$$、第 $$$a_2$$$、$$$\ldots$$$、第 $$$a_k$$$ 玩家。他们同时被踢出游戏。如果一行中的第 $$$i$$$ 玩家应该被踢出,但一行中的玩家少于 $$$i$$$,则他们会被跳过。

一旦在某一轮中没有人被踢出游戏,所有仍在游戏中的玩家将被宣布为获胜者。

例如,考虑有 $$$a=[3, 5]$$$ 和 $$$n=5$$$ 玩家的游戏。让玩家按照最初排列的顺序命名为玩家 A、玩家 B、$$$\ldots$$$、玩家 E。然后,

- 第一轮开始前,玩家按 ABCDE 排列。 Nene 找到连续第 $$$3$$$ 和第 $$$5$$$ 的玩家。他们是选手 C 和 E。他们在第一轮就被淘汰了。
- 现在玩家按 ABD 排列。 Nene 找到连续第 $$$3$$$ 和第 $$$5$$$ 的玩家。第 $$$3$$$ 玩家是玩家 D,并且连续没有第 $$$5$$$ 玩家。因此,第二轮中只有玩家 D 被踢出局。
- 在第三轮中,没有人被踢出游戏,因此游戏在本轮后结束。
- 玩家 A 和 B 被宣布为获胜者。

Nene 尚未决定最初有多少人加入游戏。 Nene 给了你 $$$q$$$ 整数 $$$n_1, n_2, \ldots, n_q$$$,你应该为每个 $$$1 \le i \le q$$$ 独立回答以下问题:

- 如果游戏中最初有 $$$n_i$$$ 玩家,有多少人会被宣布为获胜者?

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 250$$$)。测试用例的描述如下。

第一行 case 包含两个整数 $$$k$$$ 和 $$$q$$$ ($$$1 \le k, q \le 100$$$) - 序列 $$$a$$$ 的长度和值 $$$n_i$$$ 的数量,您应该解决这个问题。

第二行包含 $$$k$$$ 整数 $$$a_1,a_2,\ldots,a_k$$$ ($$$1\leq a_1<a_2<\ldots<a_k\leq 100$$$) — 序列 $$$a$$$。

第三行包含 $$$q$$$ 整数 $$$n_1,n_2,\ldots,n_q$$$ ($$$1\leq n_i \leq 100$$$)。

输出

对于每个测试用例,输出 $$$q$$$ 整数:如果最初 $$$n_i$$$ 玩家加入游戏,则其中的第 $$$i$$$ ($$$1\le i \le q$$$) 应该是宣布为获胜者的玩家数量。

示例

输入 #1

6
2 1
3 5
5
5 3
2 4 6 7 9
1 3 5
5 4
3 4 5 6 7
1 2 3 4
2 3
69 96
1 10 100
1 1
100
50
3 3
10 20 30
1 10 100

输出 #1

2 
1 1 1 
1 2 2 2 
1 10 68 
50 
1 9 9

注意

第一个测试用例在声明中进行了解释。

在第二个测试用例中,当 $$$n=1$$$ 时,唯一的玩家在第一轮中留在游戏中。之后,游戏结束,唯一的玩家被宣布为获胜者。