Migrated from Lutece 2379 红魔族首屈一指の族长之女

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description

吾名悠悠，操纵高级魔法的大魔法师！红魔族首屈一指的魔法师，乃终将成为族长之人！ 来到红魔之里的第二天，惠惠带着和真和阿库娅参观红魔之里的各个景点。

这些景点诸如掌管暴戾与怠惰的邪神沃芭克、掌管暴戾的漆黑魔兽，掌管傀儡与复仇的连名字都被遗忘的女神曾经的封印处，“搞不好会毁灭世界的武器”的存放处，装备着强力的魔道具、可以偷窥到魔王女儿房间的展望台，村口一只被石化了的狮鹫，混浴温泉，拔不出来的石中剑，咖啡店“致命毒药”，许愿池，猫耳神社等等。红魔之里的 $n$ 个景点非常特别地由 $n-1$ 条双向小路连接着，并且所有景点都是联通的。

为了吸引更多的人来红魔之里游玩，红魔族族长希罗彭决定在 $N$ 个景点处发放红魔之里限定纪念品。但正巧希罗彭引以为傲的女儿悠悠回到了红魔之里，于是发放红魔之里限定纪念品吸引游客的工作就交给了悠悠。红魔之里限定纪念品共 $m$ 种，第 $i$ 个景点发放的是第 $p_i$ 种红魔之里限定纪念品，根据调查，悠悠已经知道游客对第 $i$ 种纪念品的喜爱程度为 $f_i$。鬼畜和真告诉悠悠：同样的红魔之里限定纪念品收集越多，获得得乐趣也会随之降低，第 $j$ 次收到某种红魔之里限定纪念品的新奇程度为 $c_j$。如果一个游客第 $j$ 次收到第 $i$ 种红魔之里限定纪念品，则他的满意程度会增加 $f_ic_j$。

当然，红魔之里的每个景点所发放的红魔之里限定纪念品不一定是一成不变的。有时，一些景点所发放的红魔之里限定纪念品可能会更换，以此让游客们感受到更多惊喜。

游客们如鬼畜和真一样，秉着多一事不如少一事的原则，他们拒绝走回头路：一个游客会选择一个景点作为起点，另一个景点作为终点，同时按顺序游玩路径上的所有景点，很显然这条路径是唯一的。而悠悠现在的工作是统计来红魔之里游玩的每个游客的满意程度。

惠惠看见了在红魔之里景点附近一个人孤独地做统计的悠悠，回头对和真和阿库娅说：“她这样是不是太可怜了啊？” “确实呢，果然她就算是回到红魔之里也找不到伙伴呢。” “和真和真，你快看那个纪念品像不像平胸的厄里斯啊！” “你给我适可而止啊kora！！！” （拍头）

最终惠惠和和真还是被阿库娅拖到景点去了，拿到了许许多多的有意思的红魔之里限定纪念品。

而你，一个一般通过红魔族，看见了继续一个人可怜又孤独地做着统计工作的悠悠，心血来潮决定帮她一把。

悠悠可能会给你几个红魔之里限定纪念品作为感谢。

Input

第一行包含三个正整数 $n,m,q$，分别表示红魔之里的景点个数、红魔之里限定纪念品种类数和事件数。

第二行包含 $m$ 个正整数 $f_1,f_2,…,f_m$。

第三行包含 $n$ 个正整数 $c_1,c_2,…,c_n$。

第四行到第 $n+2$ 行，每行包含两个正整数 $x,y$，表示 $x$ 和 $y$ 两个景点之间有一条双向小路可以直接到达。

第 $n+3$ 行包含 $n$ 个正整数 $p_1,p_2,…,p_n$。

接下来 $q$ 行，每行包含三个整数 $t,a,b$，表示一次操作：

• 若 $t$ 为 $0$，则 $1\le a\le n,1\le b\le m$，表示编号为 $a$ 的景点发放的红魔之里限定纪念品改为第 $b$ 种；
• 若 $t$ 为 $1$，则 $1\le a,b\le n$，表示一位游客选择起点为 $a$，终点为 $b$ 的游览路径，计算其满意程度。

Output

按照输入的先后顺序，对于每个 $t$ 为 $1$ 的事件输出一行一个正整数表示答案。

Samples

4 4 7
1 9 2 6
7 5 5 1
2 3
3 1
4 3
1 2 3 4
1 1 2
1 4 2
0 3 4
1 1 2
0 2 1
1 4 2
1 2 1

84
119
112
79
54

Constraints

$1\le n,m,q\le 10^5,1≤c_i,f_i\le 10^6$，$1\le p_i\le m$，$c_1,c_2,…,c_n$ 是非递增序列，即对任意 $1<i\le n$，满足 $c_i\le c_{i−1}$。

Resources

2020 UESTC ICPC Training for Data Structures