该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

题目描述

你是银河系“星际农业公司”的智能管理AI，负责照看 $n$ 棵“星光玉米”的生长。 每棵玉米有一个初始的星际能量值（分数），但你作为AI可以给某个区间的玉米施加“光子肥料”，让它们长得更快。 经过一段时间的照料后，你需要知道能量最低的那棵玉米的能量值，以防止它长得太慢影响收成。

输入格式

每个测试包含多个测试用例。第一行包含测试用例的数量 $t$ $(1≤t≤1000)$。

每个测试用例的第一行有两个整数 $n$, $q$，代表玉米的数量和施肥的次数。$(2≤n，q≤2×10^5)$

每个测试用例的第二行有 $n$ 个数，代表每棵玉米的初始星际能量值。（玉米的初始星际能量值≤100）

每个测试用例的接下来 $q$ 行，每行有三个整数 $x$, $y$, $z$，表示给第 $x$ 棵到第 $y$ 棵玉米施加 $z$ 单位的“光子肥料”(1单位的"光子肥料"可使得玉米增加1单位能量)。$（1≤x≤y≤n，-100≤z≤100）$

输出格式

对于每个测试用例，输出一个整数表示施肥后能量最低的玉米的能量值。

样例

1
3 2
1 1 1
1 2 1
2 3 1

2