So Close Yet So Far

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian 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 A_{z} 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(A_{p}  A_{q}) 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(A_{p}  A_{q}) 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 ith integer denotes A_{i}.
The next N1 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 ≤ A_{i} ≤ 10^{9}
 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
 Only Type F queries are present.
 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.
Author:  animesh_f 
Tester:  pushkarmishra 
Editorial  http://discuss.codechef.com/problems/CLOSEFAR 
Tags  animesh_f, datastructure, ltime38, lunchtime, moalgorithm, optimization 
Date Added:  29072016 
Time Limit:  3.5 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions