B'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: 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. The first line of input data contains an integer T ( 1 <= T <= 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 <= n,m <= 10^5 ) --the number of jobs and the number of training'...