Сакурако вскоре будет сдавать тест. Тест можно описать как массив целых чисел \(n\) и задание на нем:
Задав целое число \(x\), Сакурако может выполнить следующую операцию любое количество раз:
- Выбрать целое число \(i\) (\(1\le i\le n\)) такое, что \(a_i\ge x\);
- Изменить значение \(a_i\) на \(a_i-x\).
Применяя эту операцию произвольное количество раз, она хочет найти минимальную возможную медиану\(^{\text{∗}}\) массива \(a\).
Сакурако знает массив, но не знает целое число \(x\). Кто-то проболтался, что одно из \(q\) значений \(x\) будет в следующем тесте, поэтому Сакурако спрашивает вас, каков ответ для каждого такого \(x\).
Выходные данные
Для каждого набора входных данных выведите \(q\) целых чисел — ответ для каждого запроса.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2
5 5
1 2 3 4 5
1
2
3
4
5
6 3
1 2 6 4 1 3
2
1
5
|
0 1 1 1 2
1 0 2
|