PT07J - Query on a tree III

You are given a node-labeled rooted tree with n nodes.

Define the query (x, k): Find the node whose label is k-th largest in the subtree of the node x. Assume no two nodes have the same labels.

Input

The first line contains one integer n (1 ≤ n ≤ 105). The next line contains n integers li (0 ≤ li ≤ 109) which denotes the label of the i-th node.

Each line of the following n - 1 lines contains two integers u, v. They denote there is an edge between node u and node v. Node 1 is the root of the tree.

The next line contains one integer m (1 ≤ m ≤ 104) which denotes the number of the queries. Each line of the next m contains two integers x, k. (k ≤ the total node number in the subtree of x.)

Output

For each query (x, k), output the index of the node whose label is the k-th largest in the subtree of the node x.

Example

Input:
5
1 3 5 2 7
1 2
2 3
1 4
3 5
4
2 3
4 1
3 2
3 2

Output:
5
4
5
5

Added by:Thanh-Vy Hua
Date:2007-04-07
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS LISP sbcl LISP clisp D FORTRAN HASK ICON ICK JAVA LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PHP PIKE PRLG-swi PYTHON RUBY SCM guile SCM qobi ST TEXT WHITESPACE
Resource:Co-author Amber

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.