F. Виталий и Advanced Useless Algorithms
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Виталий записался на курс Advanced Useless Algorithms. Курс состоит из $$$n$$$ заданий. Виталий подсчитал, что до задания $$$i$$$ у него есть $$$a_i$$$ часов на выполнение, начиная с дня записи на курс. То есть, дедлайн до задания $$$i$$$ составляет $$$a_i$$$ часов. Массив $$$a$$$ отсортирован по возрастанию, другими словами, номера заданий соответствуют порядку сдачи заданий.

Виталий все делает добросовестно, поэтому он хочет выполнить каждое задание на $$$100$$$ процентов, или больше. Изначально его уровень выполнения по каждому заданию равен $$$0$$$ процентов.

У Виталия есть $$$m$$$ опций подготовки, каждая опция может быть использована не более одного раза. Опция $$$i$$$ характеризуется тремя целыми числами: $$$e_i, t_i$$$ и $$$p_i$$$. Если Виталий использует $$$i$$$-ю опцию, то через $$$t_i$$$ часов (с текущего момента) он улучшит выполнение задания $$$e_i$$$ на $$$p_i$$$ процентов.

Например, пусть Виталию предстоит выполнить $$$3$$$ задания. Пусть массив $$$a$$$ имеет вид: $$$a = [5, 7, 8]$$$. Допустим, Виталию доступны $$$5$$$ опций: $$$[e_1=1, t_1=1, p_1=30]$$$, $$$[e_2=2, t_2=3, p_2=50]$$$, $$$[e_3=2, t_3=3, p_3=100]$$$, $$$[e_4=1, t_4=1, p_4=80]$$$, $$$[e_5=3, t_5=3, p_5=100]$$$.

Тогда если Виталий будет готовиться следующим образом, он сможет выполнить все вовремя:

  • Виталий выбирает опцию $$$4$$$. Тогда через $$$1$$$ час он выполнит задание $$$1$$$ на $$$80$$$ процентов. До дедлайна задания $$$1$$$ ему остается ещё $$$4$$$ часа.
  • Виталий выбирает опцию $$$3$$$. Тогда через $$$3$$$ часа он полностью выполнит задание $$$2$$$. До дедлайна задания $$$1$$$ у него остается ещё $$$1$$$ час, а до дедлайна задания $$$3$$$ ему остаётся $$$4$$$ часа.
  • Виталий выбирает опцию $$$1$$$. Тогда через $$$1$$$ час он выполнит задание $$$1$$$ на $$$110$$$ процентов, то есть успеет выполнить задание $$$1$$$ как раз к дедлайну.
  • Виталий выбирает опцию $$$5$$$. Тогда $$$2$$$ часа он будет выполнять задание $$$3$$$, и через еще $$$1$$$ час Виталий полностью выполнит задание $$$3$$$.

Таким образом, Виталий полностью и вовремя сумел пройти курс, использовав $$$4$$$ опции.

Помогите Виталию — выведите опции, по которым Виталию следует выполнить задания в нужном порядке. Обратите внимание: каждая опция может быть использована не более одного раза. Если существует несколько возможных ответов, разрешается вывести любой.

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

В первой строке входных данных записано целое число $$$T$$$ ($$$1 \le T \le 10^4$$$) — количество наборов входных данных в тесте.

Далее следуют описания наборов входных данных.

Первая строка описания каждого набора содержит два целых числа $$$n$$$ и $$$m$$$ ($$$1 \le n,m \le 10^5$$$) — количество заданий и количество опций подготовки соответственно.

В следующей строке заданы $$$n$$$ чисел $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^9$$$) — время до дедлайна задания $$$i$$$. Заданные значения — не убывают, то есть $$$a_1 \le a_2 \le \dots \le a_n$$$.

Следующие $$$m$$$ строк содержат тройки чисел $$$e_i, t_i, p_i$$$ ($$$1 \le e_i \le n$$$, $$$1 \le t_i \le 10^9$$$, $$$1 \le p_i \le 100$$$) — если Виталий выберет эту опцию, то через $$$t_i$$$ часов он улучшит выполнение задания с номером $$$e_i$$$ на $$$p_i$$$ процентов. Опции пронумерованы от $$$1$$$ до $$$m$$$ в порядке следования во входных данных.

Гарантируется, что сумма $$$n+m$$$ по всем наборам входных данных не превышает $$$2 \cdot 10^5$$$.

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

Для каждого набора входных данных выведите в первой строке число $$$k$$$, означающие что за $$$k$$$ опций Виталий сможет выполнить каждое задание на $$$100$$$ процентов или больше вовремя. Опции не должны повторяться. Либо выведите -1, если Виталий не имеет возможности выполнить все задания вовремя.

Если ответ существует, то в следующей строке выведите $$$k$$$ различных целых чисел от $$$1$$$ до $$$m$$$ — номера опций в нужном порядке. Если существует несколько ответов, разрешается вывести любой из них.

Примеры
Входные данные
5
3 5
5 7 8
1 1 30
2 3 50
2 3 100
1 1 80
3 3 100
1 5
51
1 36 91
1 8 40
1 42 83
1 3 45
1 13 40
2 9
9 20
2 8 64
2 7 64
1 20 56
2 8 76
2 20 48
1 2 89
1 3 38
2 18 66
1 7 51
3 2
7 18 33
1 5 80
3 4 37
2 5
569452312 703565975
1 928391659 66
1 915310 82
2 87017081 92
1 415310 54
2 567745964 82
Выходные данные
4
1 4 3 5 
3
2 4 5 
4
6 7 1 2 
-1
4
2 4 3 5
Входные данные
3
3 9
20 31 40
1 9 64
3 17 100
3 9 59
3 18 57
3 20 49
2 20 82
2 14 95
1 8 75
2 16 67
2 6
20 36
2 2 66
2 20 93
1 3 46
1 10 64
2 8 49
2 18 40
1 1
1000000000
1 1000000000 100
Выходные данные
-1
4
3 4 1 5 
1
1