Вася играет в одну очень известную и крайне популярную ММОРПГ-игру. У игрового персонажа (героя) Васи имеется k характеристик; на текущий момент i-я из них равна ai. Также в этой игре имеется общая рейтинговая таблица, в которой участники ранжируются согласно произведению всех характеристик героя, по убыванию величины.
Вася собирается "прокачать" своего персонажа, воспользовавшись услугами игрового магазина. Магазин предлагает n возможных способов улучшить характеристики героя; каждый из этих способов принадлежит одному из следующих трех типов:
- сделать i-ю характеристику равной b;
- прибавить к i-ой характеристике b;
- увеличить i-ю характеристику в b раз.
К сожалению, а) каждым улучшением можно воспользоваться только один раз; б) денег на карточке у Васи хватит только на покупку не более чем m из этих n улучшений. Помогите Васе достичь наибольшего рейтинга в игре. Для этого подскажите Васе, какие из улучшений надо приобрести и в каком порядке их использовать, чтобы рейтинг стал как можно больше. Если имеется несколько вариантов решения, выведите любой.
Выходные данные
Первая строка должна содержать число l (0 ≤ l ≤ m) — число улучшений.
Вторая строка должна содержать через пробел l различных чисел vi (1 ≤ vi ≤ n) — номера улучшений в том порядке, в котором их нужно совершать. Улучшения нумеруются начиная с 1, в том порядке, в котором они следуют во вводе.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2
|
3
2 3 4
|