A国有N座城市，它们用正整数1…N进行编号。这些城市之间通过N-1条双向道路连接，使得任意两座城市间都有且仅有一条路径相连。定义两个城市间的距离为连接这两个城市路径上的边数。
陶陶要在A国进行若干趟旅行，每次他会选择一个起点城市s和终点城市t，他从城市s开始，沿着s到亡的路径旅行，当他到达第i个城市时，可以选择坐火车到达与城市i距离不超过Ai的另一座城市，但这座城市必须要在S到t的路径上，你的任务是求出陶陶每趟旅
行最少需要坐多少次火车。
除此之外，某些城市的火车车次中途会有改变，也就是说陶陶的每趟旅行之间可能夹杂了一些城市Ai值的改变。
共N+M+2行。
第一行包含一个正整数Ⅳ，表示A国城市的数目。
第二行包含N个正整数，第i个正整数表示Ai (Ai≤20)。
接下来有N-1行，每行包含两个正整数U，V(U,V≤N），表示城市u和V之间有一条双向道路相连。
第N+2行包含一个正整数M，表示操作次数。
下面M行，每行先给出一个字符，Q表示询问操作、C表禾修改操作。假如是询问操作，后面会有两个正整数s，t(s，t≤N，s≠t)，分别表示起点城市和终点城市。假如是修改操作，后面会有两个正整数i，x(i≤N，x≤20)，表示将Ai修改为x。
包含若干行，对于每次询问输出对应的答案。
8
2 1 1 2 2 1 1 1
1 2
1 3
2 8
3 4
3 5
4 6
4 7
5
Q 5 8
Q 6 7
C 6 2
Q 6 7
Q 8 5
2
2
1
3
【样例说明】
第一次询问的路线为5-->1-->8；
第二次询问的路线为6-->4-->7；
第三次询问的路线为6 -->7；
第四次询问的路线为8-->2-->1-->5。
对于100%的数据满足N≤100，000，M≤100，000。对于包含修改操作的数据，修改操作约占操作总数的三分之一。