ADAPEAR  Ada and Pear
Ada the Ladybug is succesful farmer. She already has monopoly of vegetable. She wants to expand her business circle  more precisely, she wants to start business with fruits so she started to grow pears.
She grows N pears on a tree. She wants to sell them to buyers.
But it is not as easy as it might look like. None wants to buy a pig in a poke. They have very annoying quesions:
What is the price of pears?
What is the taste of pears?
What is the average size of pears?
First two questions can be solved easily, but what about the third? Ada can't do this for herself (since her trees are big and there are many such questions). Basically, you will have to help her to answer following kind of questions: What is the median size of pear on a path from peartopear? [Median is such value that there is no more than 50% lesser values and no more than 50% greater values. Also note that if this is true for multiple values, then output the biggest.]
Input
The first line of input will consists of 1 ≤ T ≤ 1000 number of testcases [trees in Ada's garden].
Each test case begins with two integers 1 ≤ N,Q ≤ 5*10^{4}, number of pears and number of queries.
Afterward, a line with N integers 1 ≤ A_{i} ≤ 10^{9}  the sizes of pears.
Next N1 lines consists of description of branches. The branch is descibed by two numbers 0 ≤ I, J < N, the pears it connects (I ≠ J).
Next Q lines are composed of two integers 0 ≤ I, J < N, the beginning and end of path on tree, for which buyers want to know the median size of pear.
Sum of N and and sum of Q over all testcases won't exceed 10^{5}
Output
For each peartopear path on tree, output the median size (as stated above) of tree.
Example Input
2 10 5 1 2 3 4 5 6 7 8 9 10 4 0 0 1 0 5 1 3 1 2 3 6 2 8 2 9 6 7 4 7 7 9 1 7 5 6 9 8 5 3 100 20 666 1024 1 1 2 2 3 4 2 2 0 1 2 2 3 1 4
Example Output
5 7 7 4 9 666 1024 20
hide comments
morass:
20170223 10:16:12
@[Rampage] Blue.Mary: Oh it is true it can be solved in similar manner  sure, moved! Thanx 

[Rampage] Blue.Mary:
20170223 03:29:12
This problem is coincident with this one:

Added by:  Morass 
Date:  20170212 
Time limit:  2s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All 