During university, there is a frequent need to rent classrooms. Whether it is for large-scale departmental events or small study group discussions, one must apply to the school to borrow a classroom. Classrooms vary in size and functionality, the status of the applicants differs, and the procedures for borrowing classrooms also vary.

Faced with a massive amount of classroom rental information, we naturally hope to solve this problem through programming.

We need to process classroom rental information for the next $n$ days, where on day $i$, the school has $r_i$ classrooms available for rent. There are a total of $m$ orders, each described by three positive integers $d_j, s_j, t_j$, indicating that a renter needs to borrow $d_j$ classrooms every day from day $s_j$ to day $t_j$ (inclusive of both day $s_j$ and day $t_j$).

We assume that the renters have no requirements regarding the size or location of the classrooms. That is, for each order, we only need to provide $d_j$ classrooms each day; we do not need to consider which specific classrooms they are, or whether they are the same classrooms each day.

The principle for borrowing classrooms is first-come, first-served, meaning we must allocate classrooms for each order in the order they were received. If we encounter an order that cannot be fully satisfied during the allocation process, we must stop the allocation and notify the current applicant to modify their order. "Cannot be satisfied" means that there is at least one day between day $s_j$ and day $t_j$ where the number of remaining classrooms is less than $d_j$.

Now we need to determine if there are any orders that cannot be fully satisfied. If so, we need to identify which applicant must be notified to modify their order.

Input

The first line contains two positive integers $n$ and $m$, representing the number of days and the number of orders.

The second line contains $n$ positive integers, where the $i$-th number is $r_i$, representing the number of classrooms available for rent on day $i$.

The next $m$ lines each contain three positive integers $d_j, s_j, t_j$, representing the number of classrooms to rent, and the start and end days of the rental period.

Adjacent numbers on each line are separated by a single space. Days and orders are numbered starting from $1$.

Output

If all orders can be satisfied, output a single line containing the integer $0$. Otherwise (if the orders cannot be fully satisfied), output two lines: the first line contains the negative integer $-1$, and the second line contains the index of the applicant who needs to modify their order.

Examples

Input 1

4 3
2 5 4 3
2 1 3
3 2 4
4 2 4

Output 1

-1
2

Note 1

After the first order is satisfied, the number of remaining classrooms for the $4$ days are $0, 3, 2, 3$. The second order requires $3$ classrooms per day from day $2$ to day $4$, but the number of remaining classrooms on day $3$ is $2$, so it cannot be satisfied. The allocation stops, and the second applicant is notified to modify their order.

Subtasks

For $10\%$ of the data, $1 \le n, m \le 10$;

For $30\%$ of the data, $1 \le n, m \le 1000$;

For $70\%$ of the data, $1 \le n, m \le 10^5$;

For $100\%$ of the data, $1 \le n, m \le 10^6$, $0 \le r_i, d_j \le 10^9$, $1 \le s_j \le t_j \le n$.