Изменения рейтингов за последние раунды временно удалены. Скоро они будут возвращены. ×

A. Игра Нины
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Нина придумала новую игру, основанную на возрастающей последовательности целых чисел $$$a_1, a_2, \ldots, a_k$$$.

В этой игре, изначально $$$n$$$ игроков встают в ряд. В каждом раунде происходит следующее:

  • Нина находит $$$a_1$$$-го, $$$a_2$$$-го, $$$\ldots$$$, $$$a_k$$$-го игроков в ряду. Они покидают игру одновременно. Если игру должен покинуть $$$i$$$-й игрок в ряду, но в ряду меньше $$$i$$$ игроков, этот игрок пропускается.

Как только в некотором раунде никто не покинул игру, все игроки, находящиеся в игре в данный момент, объявляются победителями.

Например, рассмотрим игру с $$$a=[3, 5]$$$ и $$$n=5$$$ игроками. Пусть игроков зовут игрок A, игрок B, $$$\ldots$$$, игрок E в том порядке, в котором они выстроились изначально. Тогда,

  • Перед первым раундом, порядок игроков в ряду ABCDE. Нина находит $$$3$$$-го и $$$5$$$-го игроков в ряду. Это игроки C и E. Они покидают игру в первом раунде.
  • Теперь порядок игроков ABD. Нина находит $$$3$$$-го и $$$5$$$-го игроков в ряду. $$$3$$$-й игрок это игрок D и в ряду нет $$$5$$$-го игрока. Поэтому только игрок D покидает игру во втором раунде.
  • В третьем раунде никто не покидает игру, поэтому после этого раунда игра заканчивается.
  • Игроки A и B объявляются победителями.

Нина пока не решила, сколько игроков будут принимать участие в игре. Она даст вам $$$q$$$ целых чисел $$$n_1, n_2, \ldots, n_q$$$, а вы должны ответить на следующий вопрос для всех $$$1 \le i \le q$$$ независимо:

  • Сколько игроков будут объявлены победителями, если изначально в игре будут принимать участие $$$n_i$$$ игроков?
Входные данные

В первой строке дано одно целое число $$$t$$$ ($$$1 \le t \le 250$$$) — количество наборов входных данных.

В первой строке даны два целых числа $$$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$$$ целых чисел: $$$i$$$-е ($$$1\le i \le q$$$) из них должно быть равно количеству игроков, которые будут объявлены победителями, если изначально в игре будет принимать участие $$$n_i$$$ игроков.

Пример
Входные данные
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
Выходные данные
2 
1 1 1 
1 2 2 2 
1 10 68 
50 
1 9 9
Примечание

Первый набор входных данных разобран в условии.

Во втором наборе входных данных при $$$n=1$$$, единственный игрок остаётся в игре после первого раунда. После этого, игра заканчивается и он объявляется победителем.