Недавно Миша увлекся разработкой игр и уже выпустил свою первую игру в жанре RPG «Надземелья и Дарконы». Вы играете за рыцаря, который побеждает дарконов в надземельях. Все надземелья сгенерированы процедурно, драки с дарконами детально проработаны, а умопомрачительной 3D-графике позавидует даже «Суперпанк»!
Даня уже давно занимается прохождением игр на скорость, за что он и получил свою известность в сети Интернет. Миша обратился к Дане за помощью: он хочет, чтобы Даня во время прямой трансляции прошел игру «Надземелья и Дарконы» как можно быстрее, так как думает, что это привлечет новых игроков. Даня не смог отказаться от очередного испытания, однако быстрое прохождение требует глубоких знаний об игре, а времени на изучение у него нет, так что Миша вкратце объяснил, в чем заключается суть игры.
Ваш персонаж начинает свой путь с уровнем силы $$$x$$$. Он может пойти в любое из $$$n$$$ надземелий, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, и попытаться победить там даркона, за счет чего повысить свой уровень. А именно, в надземелье с номером $$$i$$$ живет даркон с уровнем силы $$$a_i$$$, и его можно победить только в том случае, если уровень силы вашего персонажа больше уровня силы даркона. В противном случае вы гарантировано проиграете. После победы над дарконом уровень персонажа повысится на $$$a_i$$$, а само надземелье станет зачищенным, то есть там больше не будут появляться дарконы. Целью игры является победить самого большого и страшного даркона, живущего в надземелье под номером $$$n$$$, поэтому вы должны сражаться с дарконами, пока не получите достаточный уровень силы и не победите финального босса.
Зная все это, Дане осталось только выбрать стратегию прохождения, то есть какие надземелья и в каком порядке ему нужно зачищать, чтобы пройти игру. Естественно, ему в первую очередь важна скорость, так что стратегия должна быть выбрана таким образом, чтобы в каждом сражении Даня гарантировано выходил победителем, а сражений было как можно меньше.
Найдите оптимальную стратегию или скажите, что игру пройти невозможно.
Первая строка содержит два целых числа $$$n$$$ и $$$x$$$ ($$$1 \le n \le 100\,000$$$, $$$1 \le x \le 10^9$$$) — количество надземелий и изначальный уровень силы персонажа, соответственно.
Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^9$$$), где $$$a_i$$$ — уровень силы даркона, живущего в надземелье с номером $$$i$$$.
Если игру пройти невозможно, выведите в единственной строке число $$$0$$$.
В противном случае в первой строке выведите целое число $$$m$$$ ($$$1 \le m \le n$$$) — количество зачищенных надземелий в оптимальной стратегии.
Во второй строке выведите $$$m$$$ различных целых чисел $$$b_1, \ldots, b_m$$$ ($$$1 \le b_i \le n$$$) — порядок, в котором Даня должен посещать надземелья в оптимальной стратегии. Обратите внимание, что последним надземельем должно быть надземелье с номером $$$n$$$, в которой обитает босс (иными словами, $$$b_m = n$$$).
В случае, если существует несколько оптимальных ответов, выведите любой из них.
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Дополнительные ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | 0 | Тесты из условия | полная | |
| 1 | 6 | $$$n \le 8$$$ | первая ошибка | |
| 2 | 10 | $$$n \le 20$$$ | 1 | первая ошибка |
| 3 | 15 | $$$x \le 200$$$ $$$a_i \le 200$$$ для всех $$$1 \le i \le n$$$ | первая ошибка | |
| 4 | 69 | нет | 1, 2, 3 | первая ошибка |
10 24 1 5 6 8 3 2 7 9 10
5 2 7 6 1 10
5 11 1 1 1 1
0
В первом примере оптимальная стратегия выглядит следующим образом.
- Победить даркона в надземелье с номером $$$2$$$, после этого сила героя будет равна $$$2 + 1 = 3$$$.
- Победить даркона в надземелье с номером $$$7$$$, после этого сила героя будет равна $$$3 + 2 = 5$$$.
- Победить даркона в надземелье с номером $$$6$$$, после этого сила героя будет равна $$$5 + 3 = 8$$$.
- Победить даркона в надземелье с номером $$$1$$$, после этого сила героя будет равна $$$8 + 4 = 12$$$.
- Наконец, победить босса в надземелье с номером $$$10$$$, так как его сила равна $$$10$$$, а сила героя равна $$$12$$$.
Во втором примере сила всех дарконов равна исходной силе героя, поэтому победить их невозможно.
| Name |
|---|