"You need me or you're nothing. Because we're just alike, you and I. Except you're boring. You're on the side of the angels". -Moriarty

Problem 7

On the auspicious occasion of New Year, a marathon tournament is being organised in your society.

There are a total of N participants registered for the marathon. There are Q time breaks available for the whole marathon.

In order to make the marathon unique and successful, the organizers have come up with a new format this year. Apart from the usual winner of the marathon, the organizers have decided to award the participant that is currently last in the marathon with a special prize. They have also imposed this absurd rule that the participants can never increase their speed in the whole marathon.

All the participants start at the same point and move in the same direction. Some participants may speed down for the special prize. The change of speed takes place immediately. The rest of the time, they move with a constant speed.

More formally, for each query, you need to do 2 things :-

• Output the participant which is last in the marathon at time t along with the total distance covered by him.
• Reduce the speed of the $pth$ participant by v at time t.

In case of multiple participants occupying the last position, answer the one having larger index.

Input:

First line of input contains 2 integer N and Q, denoting the number of participants and the queries. Next lines contains N integers where $V_i$ denotes the initial speed of the $ith$ participant. Next Q lines contain 3 integers $p_i$, $t_i$ and $v_i$ denoting that the speed of $p_i th$ participant is decreased by $v_i$ at the time $t_i$.

Output:

Each of the Q lines should contain 2 integers, the currently winning participant and its position from the starting point.

Constraints:

$1 \le N \le 50000$

$1 \le Q \le 10^5$

$1 \le t_i \le 10^9$

$t_i < t_{i + 1}$

$1 \le v_i \le 10^6$

$1 \le p_i \le N$

$1 \le V_i \le 10^{10}$

Note:

The speed of any participant will never be $\lt 0$ at any point of time.

This problem has binary scoring. You will get $100$ points if you pass all test cases.