F. Квесты
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

У вас есть возможность выполнять $$$n$$$ квестов. Если вы выполняете $$$i$$$-й квест, вы получаете $$$a_i$$$ монет. Вы можете выполнить не больше одного квеста в день.

Однако, после того как вы выполнили квест, вы не можете выполнить его снова в течение следующих $$$k$$$ дней. (Например, если $$$k=2$$$ и вы выполняете $$$1$$$-й квест в $$$1$$$-й день, тогда вы не сможете выполнить этот квест снова во $$$2$$$-й или в $$$3$$$-й день, но сможете его выполнить в $$$4$$$-й день.)

Заданы два целых числа $$$c$$$ и $$$d$$$. Найдите максимальный $$$k$$$ такой, что возможно получить как минимум $$$c$$$ монет за $$$d$$$ дней. Если таких $$$k$$$ не существует, выведите Impossible. Если $$$k$$$ может быть бесконечно большим, выведите Infinity.

Входные данные

Первая строка содержит одно число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных.

Первая строка каждого набора содержит три целых числа $$$n,c,d$$$ ($$$2 \leq n \leq 2\cdot10^5$$$; $$$1 \leq c \leq 10^{16}$$$; $$$1 \leq d \leq 2\cdot10^5$$$) — количество квестов, количество необходимых монет и количество дней.

Вторая строка каждого набора содержит $$$n$$$ целых чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \leq a_i \leq 10^9$$$) — награды за квесты.

Гарантируется что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$, а сумма $$$d$$$ по всем наборам входных данных не превосходит $$$2\cdot10^5$$$.

Выходные данные

Для каждого набора входных данных выведите:

  • если таких $$$k$$$ не существует, выведите Impossible;
  • если $$$k$$$ может быть бесконечно большим, выведите Infinity;
  • иначе, выведите одно целое число — максимальный $$$k$$$ такой что возможно получить как минимум $$$c$$$ монет в течение $$$d$$$ дней.
Пример
Входные данные
6
2 5 4
1 2
2 20 10
100 10
3 100 3
7 2 6
4 20 3
4 5 6 7
4 100000000000 2022
8217734 927368 26389746 627896974
2 20 4
5 1
Выходные данные
2
Infinity
Impossible
1
12
0
Примечание

В первом тесте, один из способов получить $$$5$$$ монет за $$$4$$$ дня с $$$k=2$$$ состоит в следующем:

  • день 1: выполнить квест 2, и получить $$$2$$$ монеты;
  • день 2: выполнить квест 1, и получить $$$1$$$ монету;
  • день 3: ничего не делать;
  • день 4: выполнить квест 2, и получить $$$2$$$ монеты.

Суммарно мы получили $$$2+1+2=5$$$ монет.

Во втором тесте, мы можем получить более $$$20$$$ монет в первый день, выполнив лишь только первый квест. Выполнив первый квест, мы сразу получим $$$100$$$ монет, значит значение $$$k$$$ может быть бесконечно большим, так как нам никогда не понадобится выполнить ещё один квест.

В третьем тесте, что бы мы не делали, мы не можем получить $$$100$$$ монет за $$$3$$$ дня.