U87575 魔法森林

我们沉痛地得知，$Seaway$的女朋友患了一种极其古怪的腰痛病...只有魔法国度中的一个女巫有这种病的解药。为了给女朋友治病，$Seaway$毅然决定跋艰涉险，去找女巫求取解药......

女巫是一个很傲娇的人，为了不让闲杂人等打扰到她，她在自己住所的门口设置了一个魔法森林作为屏障。只有通过这个森林的人才能获得求见女巫的资格。魔法森林有$N$棵魔法树，这些魔法树被女巫用一个强大的阵法联通成一个阵图，每棵魔法树是一个节点，被附上了一个魔法值$K$。对于求见者，阵法会进行$M$次操作，操作分为$4$种： 操作$1$：魔法森林将以某一节点为根的子树内所有节点的魔法值增加$V$。 操作$2$：魔法森林将从$x$节点到$y$节点的最短路径上的所有节点的魔法值增加$V$。 操作$3$：魔法森林将询问求见者以某一节点为根的子树内所有节点的魔法值之和。 操作$4$：魔法森林将询问求见者从$x$节点到$y$节点的最短路径上的所有节点的魔法值之和。 如果求见者回答不出问题或者回答错误，会被魔法树一口吃掉！已经有很多很多人被魔法树吃掉了，但是$Seaway$为了求取解药下定决心要攻破魔法森林得见女巫！当然，为了不白白送死，他当然要先找到你为他编写一个正确的程序......

输入的第一行包括$3$个整数$N,M,P$，其中$P$表示所有输出结果均对$P$取模。 接下来的一行包括$N$个用空格隔开的非负整数，表示各个节点上的初始魔法值。 接下来的$N-1$行，每行包含两个整数$X,Y$，表示点$x$与点$y$之间连有一条边。 接下来的$M$行，每行包括一个字母和若干个正整数，表示魔法树的每个操作，每种操作的格式如下： 操作$1$：1 x z 操作$2$：2 x y z 操作$3$：3 x 操作$4$：4 x y

输出包括若干行，依次表示每个操作$3$或操作$4$的结果。

数据范围与约定： 对于$20\%$的数据，$1\le N,M\le 10$。 对于$50\%$的数据，$1\le N,M\le 1000$。 对于$100\%$的数据，$1\le N,M\le 10^5$。 女巫向你保证：这个阵图是联通且无环的。