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

D. Магазин
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вася играет в одну очень известную и крайне популярную ММОРПГ-игру. У игрового персонажа (героя) Васи имеется k характеристик; на текущий момент i-я из них равна ai. Также в этой игре имеется общая рейтинговая таблица, в которой участники ранжируются согласно произведению всех характеристик героя, по убыванию величины.

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

  1. сделать i-ю характеристику равной b;
  2. прибавить к i-ой характеристике b;
  3. увеличить i-ю характеристику в b раз.

К сожалению, а) каждым улучшением можно воспользоваться только один раз; б) денег на карточке у Васи хватит только на покупку не более чем m из этих n улучшений. Помогите Васе достичь наибольшего рейтинга в игре. Для этого подскажите Васе, какие из улучшений надо приобрести и в каком порядке их использовать, чтобы рейтинг стал как можно больше. Если имеется несколько вариантов решения, выведите любой.

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

Первая строка содержит три числа — k, n, m (1 ≤ k ≤ 105, 0 ≤ m ≤ n ≤ 105) — количество характеристик, число продающихся улучшений и количество улучшений, которое может позволить себе Вася.

Во второй строке через пробел указаны k чисел ai (1 ≤ ai ≤ 106), начальные значения характеристик.

Далее в n строках через пробел указаны по 3 числа tj, ij, bj (1 ≤ tj ≤ 3, 1 ≤ ij ≤ k, 1 ≤ bj ≤ 106) — тип j-го улучшения (1 для присваивания, 2 для прибавления, 3 для умножения), номер характеристики, к которой его можно применить, и коэффициент b, с которым он действует.

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

Первая строка должна содержать число l (0 ≤ l ≤ m) — число улучшений.

Вторая строка должна содержать через пробел l различных чисел vi (1 ≤ vi ≤ n) — номера улучшений в том порядке, в котором их нужно совершать. Улучшения нумеруются начиная с 1, в том порядке, в котором они следуют во вводе.

Примеры
Входные данные
2 4 3
13 20
1 1 14
1 2 30
2 1 6
3 2 2
Выходные данные
3
2 3 4