CF1650F.Vitaly and Advanced Useless Algorithms

Vitaly enrolled in the course Advanced Useless Algorithms. The course consists of $n$ tasks. Vitaly calculated that he has $a_i$ hours to do the task $i$ from the day he enrolled in the course. That is, the deadline before the $i$-th task is $a_i$ hours. The array $a$ is sorted in ascending order, in other words, the job numbers correspond to the order in which the assignments are turned in.

Vitaly does everything conscientiously, so he wants to complete each task by $100$ percent, or more. Initially, his completion rate for each task is $0$ percent.

Vitaly has $m$ training options, each option can be used not more than once. The $i$th option is characterized by three integers: $e_i, t_i$ and $p_i$. If Vitaly uses the $i$th option, then after $t_i$ hours (from the current moment) he will increase the progress of the task $e_i$ by $p_i$ percent.

For example, let Vitaly have $3$ of tasks to complete. Let the array $a$ have the form: $a = [5, 7, 8]$. Suppose Vitaly has $5$ of options: $[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]$.

Then, if Vitaly prepares in the following way, he will be able to complete everything in time:

• Vitaly chooses the $4$-th option. Then in $1$ hour, he will complete the $1$-st task at $80$ percent. He still has $4$ hours left before the deadline for the $1$-st task.
• Vitaly chooses the $3$-rd option. Then in $3$ hours, he will complete the $2$-nd task in its entirety. He has another $1$ hour left before the deadline for the $1$-st task and $4$ hours left before the deadline for the $3$-rd task.
• Vitaly chooses the $1$-st option. Then after $1$ hour, he will complete the $1$-st task for $110$ percent, which means that he will complete the $1$-st task just in time for the deadline.
• Vitaly chooses the $5$-th option. He will complete the $3$-rd task for $2$ hours, and after another $1$ hour, Vitaly will complete the $3$-rd task in its entirety.

Thus, Vitaly has managed to complete the course completely and on time, using the $4$ options.

Help Vitaly — print the options for Vitaly to complete the tasks in the correct order. Please note: each option can be used not more than once. If there are several possible answers, it is allowed to output any of them.

维塔利报名了《高级无用算法》这门课程。该课程共有 $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 = [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$ 个任务完全完成（100%）。此时距第 $1$ 个任务截止时间还剩 1 小时，距第 $3$ 个任务截止时间还剩 4 小时。
• 维塔利选择第 $1$ 种方案。再过 1 小时，他将第 $1$ 个任务的完成度提升至 110%，即恰好在截止时间前完成第 $1$ 个任务。
• 维塔利选择第 $5$ 种方案。他花费 2 小时进行训练，再过 1 小时后，第 $3$ 个任务完成度达到 100%。

因此，维塔利成功地在截止时间前完整完成了全部课程，共使用了 4 种方案。

请帮助维塔利——输出他完成所有任务所需使用的方案编号（按执行顺序）。注意：每种方案最多只能使用一次。若存在多种可行解，输出任意一种即可。

The first line of input data contains an integer $T$ ($1 \le T \le 10^4$) —the number of input test cases in the test.

The descriptions of the input test case follow.

The first line of each test case description contains two integers $n$ and $m$ ($1 \le n,m \le 10^5$) —the number of jobs and the number of training options, respectively.

The next line contains $n$ numbers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$) — the time before the deadline of job $i$. The array values — are non-decreasing, that is $a_1 \le a_2 \le \dots \le a_n$.

The following $m$ lines contain triples of numbers $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$) — if Vitaly chooses this option, then after $t_i$ hours he will increase the progress of the task $e_i$ by $p_i$ percent. The options are numbered from $1$ to $m$ in order in the input data.

It is guaranteed that the sum of $n+m$ on all test cases does not exceed $2 \cdot 10^5$.

输入数据的第一行包含一个整数 $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$）——若 Vitaly 选择该选项，则经过 $t_i$ 小时后，任务 $e_i$ 的完成进度将提升 $p_i$ 个百分点。这些选项按输入顺序编号为 $1$ 至 $m$。

保证所有测试用例中 $n+m$ 的总和不超过 $2 \cdot 10^5$。

For each test case, print on the first line the number $k$, meaning that for $k$ of options, Vitaly will be able to complete each task by $100$ percent or more on time. The options should not be repeated. Or print -1 if Vitaly is unable to complete all tasks in time.

If there is an answer, on the next line print $k$ of different integers from $1$ to $m$ — the numbers of the options in the order you want. If there is more than one answer, it is allowed to print any of them.

对于每个测试用例，在第一行输出一个整数 $k$，表示在 $k$ 个选项中，Vitaly 能够以 $100\%$ 或更高的完成率按时完成所有任务。这些选项不能重复。如果 Vitaly 无法在规定时间内完成所有任务，则输出 $-1$。

如果存在解，则在下一行输出 $k$ 个互不相同的、取值范围为 $1$ 到 $m$ 的整数——即所选选项的编号（按你指定的顺序）。若存在多个可行解，输出任意一个即可。