北投以其壮丽的景色和丰富的温泉而闻名，吸引了无数寻求放松和恢复活力的游客。该地区拥有极其密集的温泉和水疗中心，使其成为全球此类休闲活动的中心。北投谷曾经是一个古朴的地方，当地人在这里的天然温泉中寻求慰藉，如今已发展成为一片广阔的区域，拥有三十多家豪华度假村。

传统上，温泉会让人联想到火山活动和明显的硫磺味。然而，对一些人来说，后者相当令人不快。你发现自己属于那些对硫磺味敏感的人，这引出了你目前的困境。

目前正在北投游览的你，获得了一张这个迷人地方的地图，它以有根树的形式呈现。值得注意的是，北投的神秘光环允许进行非常规的测量，甚至允许节点之间存在负距离。此外，地图上的每个节点都有一个相关的硫磺含量值。

一个意想不到的发现让你质疑分配给每个地点的硫磺含量的准确性。为了纠正这一点，你的任务是根据新获得的信息调整硫磺含量。此外，你还发现了附近最大火山位置的情报。为了优先考虑你的安全和福祉，你的最终目标是找到距离这座著名火山最远且硫磺含量最低的地点。你为每个节点的生存能力选择的评估指标由公式 $d_i - a_i$ 给出，其中 $d_i$ 表示节点 $i$ 与最大火山之间的距离，$a_i$ 是相应的硫磺含量值。

我们可以用三个整数 $x_i, y_i$ 和 $v_i$ 来描述你获得的每一条新信息。这意味着 $y_i$ 的整个子树现在增加了 $v_i$ 的硫磺含量（如果 $v_i$ 为负，则硫磺含量值减少）。此外，你还了解到最大火山实际上位于 $x_i$。

注意，硫磺含量的修改是持久的：当你获得另一条新信息时，之前的硫磺修改仍然适用。

输入格式

第一行包含两个整数 $n$ 和 $q$ ($2 \le n \le 2 \cdot 10^5$ 和 $0 \le q \le 2 \cdot 10^5$)：树的大小和查询的数量。

第二行包含 $n$ 个整数 $a_1, a_2, \dots, a_n$ ($|a_i| \le 10^9$)：每个节点的硫磺含量值。

接下来给出 $n - 1$ 行。其中第 $i$ 行包含两个整数 $p_{i+1}$ 和 $w_{i+1}$ ($1 \le p_{i+1} \le i$ 且 $|w_{i+1}| \le 10^9$)：顶点 $i + 1$ 的父节点以及 $p_{i+1}$ 与 $i + 1$ 之间的距离。

最后给出 $q$ 行。每行包含三个整数 $x_i, y_i$ 和 $v_i$ ($1 \le x_i, y_i \le n$ 且 $|v_i| \le 10^9$)：你获得的新信息。

输出格式

对于每一条新信息，打印一行，包含两个整数 $s_i$ 和 $d_i$：具有最大生存能力的节点的索引以及该生存能力的值。

如果有多个答案，请输出节点索引最小的那一个。

样例

输入 1

6 6
1 1 4 5 1 4
1 5
2 0
3 2
4 1
5 6
3 2 -100000
1 2 100000
1 1 0
2 2 66
3 1 5
4 4 -3

输出 1

6 100005
6 10
6 10
1 4
1 -1
1 1

输入 2

5 6
-10 0 2 -4 8
1 7
1 1
2 2
2 -2
1 1 100
2 1 -100
1 1 0
4 3 10
2 5 3
5 2 2

输出 2

4 -87
1 17
4 13
1 19
1 17
1 15

输入 3

6 3
0 0 0 0 0 0
1 10
1 10
1 -100
4 10
4 11
1 1 0
4 1 0
1 4 1000

输出 3

2 10
6 11
2 10