Description

  A国有N座城市，它们用正整数1…N进行编号。这些城市之间通过N-1条双向道路连接，使得任意两座城市间都有且仅有一条路径相连。定义两个城市间的距离为连接这两个城市路径上的边数。
  陶陶要在A国进行若干趟旅行，每次他会选择一个起点城市s和终点城市t，他从城市s开始，沿着s到亡的路径旅行，当他到达第i个城市时，可以选择坐火车到达与城市i距离不超过Ai的另一座城市，但这座城市必须要在S到t的路径上，你的任务是求出陶陶每趟旅
行最少需要坐多少次火车。
    除此之外，某些城市的火车车次中途会有改变，也就是说陶陶的每趟旅行之间可能夹杂了一些城市Ai值的改变。

Input

共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。

Output

包含若干行，对于每次询问输出对应的答案。

Sample Input

Sample Output

Hint

【样例说明】

  第一次询问的路线为5-->1-->8；

  第二次询问的路线为6-->4-->7；

  第三次询问的路线为6 -->7；

  第四次询问的路线为8-->2-->1-->5。

  对于100%的数据满足N≤100，000，M≤100，000。对于包含修改操作的数据，修改操作约占操作总数的三分之一。

Source