You are given a rooted tree consisting of n vertices. Each vertex has a number written on it; number ai is written on vertex i.

Let's denote d(i, j) as the distance between vertices i and j in the tree (that is, the number of edges in the shortest path from i to j). Also let's denote the k-blocked subtree of vertex x as the set of vertices y such that both these conditions are met:

  * x is an ancestor of y (every vertex is an ancestor of itself); 
  * d(x, y) ≤ k. 



You are given m queries to the tree. i-th query is represented by two numbers xi and ki, and the answer to this query is the minimum value of aj among such vertices j such that j belongs to ki-blocked subtree of xi.

Write a program that would process these queries quickly!

Note that the queries are given in a modified way.

Input

The first line contains two integers n and r (1 ≤ r ≤ n ≤ 100000) — the number of vertices in the tree and the index of the root, respectively.

The second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 109) — the numbers written on the vertices.

Then n - 1 lines follow, each containing two integers x and y (1 ≤ x, y ≤ n) and representing an edge between vertices x and y. It is guaranteed that these edges form a tree.

Next line contains one integer m (1 ≤ m ≤ 106) — the number of queries to process.

Then m lines follow, i-th line containing two numbers pi and qi, which can be used to restore i-th query (1 ≤ pi, qi ≤ n).

i-th query can be restored as follows:

Let last be the answer for previous query (or 0 if i = 1). Then xi = ((pi + last) mod n) + 1, and ki = (qi + last) mod n.

Output

Print m integers. i-th of them has to be equal to the answer to i-th query.

Example

Input

5 2
1 3 2 3 5
2 3
5 1
3 4
4 1
2
1 2
2 3


Output

2
5
import java.io.*;
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class EduF implements Runnable {

    BufferedReader in;
    PrintWriter out;
    StringTokenizer tok = new StringTokenizer("");

    void init() throws FileNotFoundException {
        try {
            in = new BufferedReader(new FileReader("input.txt"));
            out = new PrintWriter("output.txt");
        } catch (Exception e) {
            String filename = "";
            if (filename.isEmpty()) {
                in = new BufferedReader(new InputStreamReader(System.in));
                out = new PrintWriter(System.out);
            } else {
                in = new BufferedReader(new FileReader(filename + ".in"));
                out = new PrintWriter(filename + ".out");
            }
        }
    }

    String readString() throws IOException {
        while (!tok.hasMoreTokens()) {
            try {
                tok = new StringTokenizer(in.readLine(), " :");
            } catch (Exception e) {
                return null;
            }
        }
        return tok.nextToken();
    }

    int readInt() throws IOException {
        return Integer.parseInt(readString());
    }

    int[] readIntArray(int size) throws IOException {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = readInt();
        }
        return res;
    }

    long readLong() throws IOException {
        return Long.parseLong(readString());
    }

    double readDouble() throws IOException {
        return Double.parseDouble(readString());
    }

    <T> List<T>[] createGraphList(int size) {
        List<T>[] list = new List[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayList<>();
        }
        return list;
    }

    <T> ArrayDeque<T>[] createGraphDeque(int size) {
        ArrayDeque<T>[] list = new ArrayDeque[size];
        for (int i = 0; i < size; i++) {
            list[i] = new ArrayDeque<>();
        }
        return list;
    }

    public static void main(String[] args) {
        new EduF().run();
//        new Thread(null, new Template(), "", 1l * 200 * 1024 * 1024).start();
    }

    long timeBegin, timeEnd;

    void time() {
        timeEnd = System.currentTimeMillis();
        System.err.println("Time = " + (timeEnd - timeBegin));
    }

    long memoryTotal, memoryFree;

    void memory() {
        memoryFree = Runtime.getRuntime().freeMemory();
        System.err.println("Memory = " + ((memoryTotal - memoryFree) >> 10)
                + " KB");
    }

    public void run() {
        try {
            timeBegin = System.currentTimeMillis();
            memoryTotal = Runtime.getRuntime().freeMemory();
            init();
            solve();
            out.close();
            if (System.getProperty("ONLINE_JUDGE") == null) {
                time();
                memory();
            }
        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }
    }

    int[] log;

    class Sparse {
        int[][] data;

        Sparse(int[] d) {
            int k = 0;
            while ((1 << k) < d.length) {
                k++;
            }
            k++;
            data = new int[k][d.length];
            for (int i = 0; i < d.length; i++) {
                data[0][i] = d[i];
            }
            for (int level = 1; level < k; level++) {
                for (int start = 0; start < d.length; start++) {
                    int next = start + (1 << (level - 1));
                    if (next >= d.length) break;

                    data[level][start] = Math.max(data[level - 1][start], data[level - 1][next]);
                }
            }
        }

        int get(int l, int r) {
            int k = log[r - l];
            int a = data[k][l];
            int b = data[k][r - (1 << k) + 1];
            return Math.max(a, b);
        }
    }

    List<Integer>[] layers;
    List<Integer>[] g;
    int[] a;
    int[] tin;
    int[] tout;
    int[] height;
    int[] indexOnLayer;
    int timer;

    void dfs(int v, int p, int h) {
        tin[v] = timer++;
        height[v] = h;
        layers[h].add(v);
        indexOnLayer[v] = layers[h].size() - 1;
        for (int y : g[v]) {
            if (y == p) continue;
            dfs(y, v, h + 1);
        }
        tout[v] = timer++;
    }

    int findLeftIndex(int v, int k) {
        int targetH = height[v] + k;
        if (targetH >= layers.length) return Integer.MAX_VALUE;
        int l = 0;
        int r = layers[targetH].size() - 1;

        int ans = Integer.MAX_VALUE;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int vert = layers[targetH].get(mid);
            if (tin[vert] >= tin[v] && tout[vert] <= tout[v]) {
                //parent
                ans = mid;
                r = mid - 1;
            } else if (tout[vert] < tin[v]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    int findRightIndex(int v, int k) {
        int targetH = height[v] + k;
        if (targetH >= layers.length) return Integer.MIN_VALUE;
        int l = 0;
        int r = layers[targetH].size() - 1;

        int ans = Integer.MIN_VALUE;
        while (l <= r) {
            int mid = (l + r) >> 1;
            int vert = layers[targetH].get(mid);
            if (tin[vert] >= tin[v] && tout[vert] <= tout[v]) {
                //parent
                ans = mid;
                l = mid + 1;
            } else if (tout[vert] < tin[v]) {
                l = mid + 1;
            } else {
                r = mid - 1;
            }
        }
        return ans;
    }

    void solve() throws IOException {
        int n = readInt();
        int root = readInt() - 1;
        tin = new int[n];
        tout = new int[n];
        indexOnLayer = new int[n];
        height = new int[n];
        layers = createGraphList(2 * n + 2);
        log = new int[2 * n + 2];
        for (int i = 2; i < log.length; i++) {
            log[i] = log[i >> 1] + 1;
        }

        a = readIntArray(n);
        g = createGraphList(n);
        for (int i = 1; i < n; i++) {
            int a = readInt() - 1;
            int b = readInt() - 1;
            g[a].add(b);
            g[b].add(a);
        }

        dfs(root, root, 0);

        Sparse[][] sparseTables = new Sparse[20][layers.length];
        for (int i = 0; i < layers.length; i++) {
            int[] maxes = new int[layers[i].size()];
            for (int j = 0; j < maxes.length; j++) {
                maxes[j] = -a[layers[i].get(j)];
            }
            sparseTables[0][i] = new Sparse(maxes);
        }

        for (int dep = 1; dep < 20; dep++) {
            for (int i = 0; i < layers.length; i++) {
                int[] maxes = new int[layers[i].size()];
                for (int j = 0; j < maxes.length; j++) {
                    int vert = layers[i].get(j);
                    maxes[j] = sparseTables[dep - 1][i].get(j, j);
                    int k = 1 << (dep - 1);
                    int l = findLeftIndex(vert, k);
                    if (l == Integer.MAX_VALUE) continue;
                    int r = findRightIndex(vert, k);

                    int secMax = sparseTables[dep - 1][i + k].get(l, r);
                    maxes[j] = Math.max(maxes[j], secMax);
                }
                sparseTables[dep][i] = new Sparse(maxes);
            }
        }

        int m = readInt();
        int last = 0;

        while (m-- > 0) {
            int p = readInt();
            int q = readInt();

            int x = (p + last) % n;
            int k = (q + last) % n;

            int lg = log[k];

            int iol = indexOnLayer[x];
            int ans = sparseTables[lg][height[x]].get(iol, iol);

            int shift = k + 1 - (1 << lg);

            int l = findLeftIndex(x, shift);
            if (l != Integer.MAX_VALUE) {
                int r = findRightIndex(x, shift);

                int secAns = sparseTables[lg][height[x] + shift].get(l, r);
                ans = Math.max(ans, secAns);
            }
            out.println(-ans);
            last = -ans;
        }
    }


}