测试数据来自 system/1985

背景

小h经过仔细的筛选，终于选出了最好的妹子树种子。他种下了这颗种子，长出了一颗茁壮的妹子树，终于到了收获的季节。

描述

由于某些奇怪的原因，小h每次需要同时找到两个妹子（QAQ），但是由于妹子是一种很奇怪的生物，小h想要泡两个妹子，就要把连接她们的路径上的所有妹子全部泡到，当然泡妹子是需要软妹币的啦，小h可是很穷的（雾）。
由于小h疏于管理他的妹子树，这个妹子树长成了一片妹子森林（QAQ），但妹子们是会感到孤独的，有时候两个妹子会成为新的朋友啦。

小h很苦恼，他不知道他应该泡哪对妹子，他需要提前知道泡她们的代价。于是他请小y帮忙，小y当然会辣，他想考考你。

支持两种操作：
Q u v：询问泡u和v的最小代价，保证u和v联通
L u v：连接u和v，保证u和v之前不联通。

我会使用一些方法强制在线。
每次你读入的一对u和v，实际应当是u^lastans,v^lastans,lastans是上一次的答案，默认一开始lastans为0,其中L u v操作不会修改lastans的值。

格式

输入格式

第一行是一个正整数n，表示一共有n个妹子，从1开始编号。
下面一行n个正整数Vi，Vi表示泡第i个妹子的代价。
然后是n行，每行给出两个1到n的数u和v，表示u和v之间有一条边，若u为0，则代表v是根节点。
接下来一个正整数m，表示共m次操作。
以下m行每行一个操作，格式见上。

输出格式

对于每一个询问操作输出一个数，表示同时泡的最小代价，每行一个数。

样例1

样例输入1

8
406 706 450 451 715 126 120 530 
0 1
0 2
6 3
1 4
8 5
4 6
0 7
1 8
8
Q 4 1
L 861 859
Q 859 860
L 2812 2815
Q 2813 2809
Q 1652 1653
Q 698 696
Q 1436 1435

样例输出1

857
2808
1651
697
1433
2808

限制

对于30%的数据，保证1<=n<=3000,1<=m<=5000

对于70%的数据，保证1<=n<=30000,1<=m<=50000

对于90%的数据，保证1<=n<=100000,1<=m<=100000

对于100%的数据，保证:1<=n<=100000,1<=m<=200000,1<=Vi<=1000

来源

感谢 yql 提供。