Vitaly 参加了高级无用算法课程。该课程由 $$$n$$$ 任务组成。 Vitaly 计算出,从他报名课程之日起,他有 $$$a_i$$$ 小时来完成 $$$i$$$ 任务。也就是说,第 $$$i$$$ 个任务之前的截止日期是 $$$a_i$$$ 小时。数组 $$$a$$$ 按升序排序,换句话说,作业编号对应于作业提交的顺序。
Vitaly 做每件事都很认真,所以他希望以 $$$100$$$% 或更多的速度完成每项任务。最初,他每项任务的完成率为 $$$0$$$%。
Vitaly 有 $$$m$$$ 训练选项,每个选项只能使用一次。 $$$i$$$th 选项由三个整数表示:$$$e_i、t_i$$$ 和 $$$p_i$$$。如果 Vitaly 使用第 $$$i$$$ 选项,那么在 $$$t_i$$$ 小时后(从当前时刻开始),他会将任务 $$$e_i$$$ 的进度增加 $$$p_i$$$%。
例如,让 Vitaly 有 $$$3$$$ 的任务需要完成。令数组 $$$a$$$ 具有以下形式:$$$a = [5, 7, 8]$$$。假设 Vitaly 有 $$$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]$$$。
那么,如果维塔利按照以下方式做好准备,他就能及时完成一切:
- Vitaly 选择了第 $$$4$$$ 个选项。然后在 $$$1$$$ 小时内,他将以 $$$80$$$% 的速度完成 $$$1$$$-st 任务。距离第 $$$1$$$ 任务的截止日期还有 $$$4$$$ 小时。
- Vitaly 选择了 $$$3$$$-rd 选项。然后在 $$$3$$$ 小时内,他将完整完成第 $$$2$$$-nd 任务。距离第 $$$1$$$-st 任务的截止日期还有 $$$1$$$ 小时,距离第 $$$3$$$-rd 任务的截止日期还剩 $$$4$$$ 小时。
- Vitaly 选择了 $$$1$$$-st 选项。然后,在 $$$1$$$ 小时后,他将完成 $$$1$$$-st 任务,并获得 $$$110$$$%,这意味着他将在截止日期前及时完成 $$$1$$$-st 任务。
- Vitaly 选择了第 $$$5$$$ 个选项。他将在 $$$2$$$ 小时内完成 $$$3$$$-rd 任务,再过 $$$1$$$ 小时后,Vitaly 将完整完成 $$$3$$$-rd 任务。
因此,Vitaly 使用 $$$4$$$ 选项成功按时完整地完成了课程。
帮助 Vitaly — 打印 Vitaly 的选项,以按照正确的顺序完成任务。请注意:每个选项只能使用一次。如果有多个可能的答案,则允许输出其中任何一个。
输入
输入数据的第一行包含一个整数 $$$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$$$。
输出
对于每个测试用例,在第一行打印数字 $$$k$$$,这意味着对于 $$$k$$$ 选项,Vitaly 将能够按 $$$100$$$ 或更多百分比按时完成每项任务。选项不应重复。或者如果 Vitaly 无法及时完成所有任务,则打印 -1。
如果有答案,请在下一行打印从 $$$1$$$ 到 $$$m$$$ 的不同整数 $$$k$$$ — 按您想要的顺序排列的选项编号。如果有多个答案,则允许打印其中任何一个。
示例
输入 #1
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
输出 #1
4 1 4 3 5 3 2 4 5 4 6 7 1 2 -1 4 2 4 3 5
输入 #2
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
输出 #2
-1 4 3 4 1 5 1 1