球包树
时间限制：C/C++/Rust/Pascal 4秒，其他语言8秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

球包？邱宝！
给定一棵有  个节点的树（根节点为  ），树上每个节点都有一个权值，现在有  个操作，每个操作是以下之一：

    1 \ \ u \ \ v \ \ x \：将节点  与节点  路径上点的权值全部加上  。

    2 \ \ u \ \ x \ ：将节点  的子树（包含节点  ）上点的权值全部加上  。

    3 \：输出 \sum_{i=1}^{n}{\sum_{j=i}^{n}{f(i,j)}} 的值，  定义为节点  到节点  最短路径上节点的权值和。


输入描述:

第一行输入两个整数 分别表示树中节点数量和进行的操作数量。
第二行输入  个整数 a_{1} \ a_{2} \ a_{3} \ ... \ a_{n} \ (1\leq a_{i} \leq 10^{6})，分别表示节点 1, \ 2, \ 3 \ ... \ n 的权值。
下面  行，每行输入两个数u, \ v \ (1\leq u \leq n, \ 1\leq v \leq n)，表示 u, \ v之间存在一条边。
下面  行，每行首先输入一个操作数 op \ (1\leq op \leq 3):
若 ， 则接着输入u, \ v, \ x \ (1\leq u \leq n, \ 1\leq v \leq n, \ 1\leq x\leq 10^{6})。
若 ， 则接着输入 。
若 ， 则输出答案。

输出描述:

对于每一个操作  ，请在每行输出答案，由于答案可能很大，请对  取模。
示例1

输入

复制 
5 5
2 5 4 1 6
1 2
1 3
2 4
2 5
3
1 3 4 5
3
2 2 4
3

输出

复制 
121
261
341

说明

首先计算初始答案：




所以初始答案  。
接着将节点  路径上的权值都加  ，即将节点  的权值加 ，然后重新计算公式，输出答案
最后将节点  的子树上的点的权值全部加  ，即将节点  的权值加  ，然后重新计算公式，输出答案

示例2

输入

复制 
5 5
2 6 7 4 10
3 1
5 3
2 5
1 4
2 5 3
2 1 8
3
1 3 5 3
1 4 3 6

输出

复制 
528

备注:

每次操作都是在上一次操作的基础上进行操作。