Takaki Tono is a Computer Programmer in Tokyo. His boss at work shows him an online puzzle, which if solved would earn the solver a full expense paid trip to Los Angeles, California. Takaki really wants to solve this, as the love of his life, Akari, lives in Los Angeles and he hasn't met her since four years. Upon reading the puzzle he realizes that it is a query based problem. The problem is as follows :-

You are given a Tree T with N nodes numbered from 1 to N, with each node numbered z having a positive integer Az written on it. This integer denotes the value of the node. You have to process Q queries, of the following forms :- 
1) C x y : Report the closest two values in the unique path from x to y i.e compute min(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y. 

2) F x y : Report the farthest two values in the unique path from x to y i.e. compute max(|Ap - Aq|) where p and q are two distinct nodes on the unique path from x to y.

It is also mentioned that x is not equal to y in any query and that no two nodes have the same value printed on them. Also, |x| denotes the absolute value of x. 

Takaki is perplexed and requires your help to solve this task? Can you help him out?

-----Input-----
The first line of the input contains an integer N denoting the number of nodes in tree T. 
The second line comprises N space separated integers denoting A, where the i-th integer denotes Ai. 
The next N-1 lines each comprise two space separated integers u and v, denoting that node u and node v
are connected by an edge. It is guaranteed that the final graph will be a connected tree.
The next line contains a single integer Q, denoting number of queries. 
The next Q lines comprise the queries. Each such line is of the format C x y or F x y. 

-----Output-----
For each query, print the required output as mentioned above. 

-----Constraints-----
- 2 ≤ N ≤ 35000
- 1 ≤ Ai ≤ 109
- 1 ≤ Q ≤ 35000
- 1 ≤ u, v ≤ N
- No two nodes have the same value printed on them.
- x is not equal to y in any query.

-----Subtasks-----

-----Subtasks-----Subtask #1 (15 points)
- N, Q ≤ 1000Subtask #2 (20 points)
- Only Type F queries are present.Subtask #3 (65 points)
- Original constraints

-----Example-----
Input:5
1 2 7 4 5
1 2
2 3
2 4
2 5
7
C 1 5
F 1 5
C 2 4
C 1 2
F 1 3
F 3 4
F 2 4

Output:1
4
2
1
6
5
2

-----Explanation-----
Given below is the tree corresponding to the sample input. Each node has two numbers written in it. 
The first number represents the node index and the second number indicates node value.

```python

USER_FILENAME = "<user_code>"
import sys, json, builtins
import math, heapq, bisect, itertools, functools, collections, statistics, fractions, decimal, operator, array, random, re, string, os, pathlib
try:
    import resource as _res
except Exception:
    _res = None
from collections import Counter, defaultdict, deque, OrderedDict
from functools import lru_cache, reduce
from itertools import accumulate, permutations, combinations, product
from math import gcd, ceil, floor, sqrt
from decimal import Decimal
try:
    from typing import *
except Exception:
    pass
try:
    sys.setrecursionlimit(1_000_000)
except Exception:
    pass
try:
    import site as _site
    try:
        _sys_sites = _site.getsitepackages() if hasattr(_site, "getsitepackages") else []
        for _p in _sys_sites:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
    try:
        _usp = _site.getusersitepackages()
        if isinstance(_usp, str):
            _usp = [_usp]
        for _p in _usp:
            if _p and _p not in sys.path:
                sys.path.append(_p)
    except Exception:
        pass
except Exception:
    pass

ns = {"__name__": "__main__"}
for _k, _v in list(globals().items()):
    if not _k.startswith("_"):
        ns[_k] = _v
_CODE = 'MAXX = 10**9+1\nN = eval(input())\nnodes = list(map(int, input().split(" ")))\nedges = [set() for _ in range(N)]\nfor _ in range(N-1):\n    a, b = list(map(int, input().split(" ")))\n    edges[a-1].add(b-1)\n    edges[b-1].add(a-1)\npath = [[] for _ in range(N)]\nvisited, tovisit = set(), [(0, 0)]\nwhile tovisit:\n    p, v = tovisit.pop()\n    if v not in visited:\n        path[v] = path[p] + [v]\n        visited.add(v)\n        news = edges[v] - visited\n        tovisit.extend([(v, x) for x in news])\n# print path\n\nQ = eval(input())\nfor _ in range(Q):\n    q, a, b = input().split(" ")\n    a, b = int(a)-1, int(b)-1\n    i = 1\n    while i < min(len(path[a]), len(path[b])):\n        if path[a][i] != path[b][i]: break\n        i += 1\n    s = path[a][i-1:] + path[b][i:]\n\n    # print s\n    if q == "C":\n        s = sorted([nodes[i] for i in s])\n        d = s[-1] - s[0]\n        for i in range(len(s)-1):\n            d = min(d, s[i+1]-s[i])\n        print(d)\n    else:\n        M = 0\n        m = MAXX\n        for i in range(len(s)):\n            M = max(M, nodes[s[i]])\n            m = min(m, nodes[s[i]])\n        print(M - m)\n    # print M[(s, l)] - m[(s, l)]'
_co = compile(_CODE, USER_FILENAME, "exec")
exec(_co, ns, ns)

```

Measured memory_bytes: 21467