Our social:

Code chef Lunch Time : Problem :- So Close Yet So Far Answer (solution)

Read problems statements in Mandarin ChineseRussian and Vietnamese as well.


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 pand 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 pand 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 vare 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 ≤ 1000
Subtask #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.


If you want answer then follow below link :

                                                       ANSWER HERE