Thanks to Max's invaluable leadership, a sizable portion of the ex-convicts are still alive and mentally stable! But before they can return home to their families, Joey orders them to exterminate the bebiliths, even if it costs them their lives!

The bebiliths pour out of the cave, aligned in ~N~ ~(1 \le N \le 1\,000\,000)~ columns. The columns are aligned such that one bebilith from each column is visible to the ex-convicts. There are ~R_i~ ~(0 \le R_i \le 10^9)~ bebiliths in the ~i^{th}~ column. Joey commands ~Q~ ~(1 \le Q \le 100\,000)~ strategic offenses, during which the ex-convicts eliminate ~c~ ~(1 \le c \le 10^9)~ bebiliths from each column for all the columns in ~[a, b]~ ~(1 \le a \le b \le N)~.

After every strategic offense from the ex-convicts, Joey wants to evaluate the enemy's condition by finding the strength of the weakest column of bebiliths for all the columns in ~[a, b]~, and then the same for all the columns in ~[1, N]~. Help Joey lead the ex-convicts to victory!

Input Specification

The first line will contain ~N~ and ~Q~, separated by a single space.
The second line will contain ~N~ integers, with each containing the value ~R_i~.
The next ~Q~ lines will each contain three space-separated integers ~a~ ~b~ ~c~.

Output Specification

For every strategic offense, print out the number of bebiliths in the weakest column in the range of columns ~[a, b]~, and the same for the range of columns ~[1, N]~, separated by a single space.

Sample Input

3 3
4 4 4
1 1 3
2 3 2
1 3 7

Sample Output

1 1
2 1
0 0

Visual Aid