题目描述

有 $n$ 个连续时刻的温度记录，第 $i$ 个时刻的初始温度值为 $a_i$。

现在进行 $m$ 次批量修正。每次给出 $l,r,x$，表示把区间 $[l,r]$ 内的所有温度值都增加 $x$，其中 $x$ 可能为负数。

所有修正结束后，请找出最终温度的最大值以及这个最大值第一次出现的位置。

输入格式

第一行输入两个整数 $n,m$。

第二行输入 $n$ 个整数 $a_1,a_2,\ldots,a_n$。

接下来 $m$ 行，每行输入三个整数 $l,r,x$。

输出格式

输出两个整数：最终最大值和它第一次出现的位置。

样例

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

8 5

数据规模与约定

• $1\le n,m\le 2\times 10^5$；
• $|a_i|,|x|\le 10^9$；
• $1\le l\le r\le n$。

最终结果可能超过 int 范围。