Problem: Recently Duff has been a soldier in the army. Malek is her commander.

Their country, Andarz Gu has n cities (numbered from 1 to n) and n - 1 bidirectional roads. Each road connects two different cities. There exist a unique path between any two cities.

There are also m people living in Andarz Gu (numbered from 1 to m). Each person has and ID number. ID number of i - th person is i and he/she lives in city number ci. Note that there may be more than one person in a city, also there may be no people living in the city.

<image>

Malek loves to order. That's why he asks Duff to answer to q queries. In each query, he gives her numbers v, u and a.

To answer a query:

Assume there are x people living in the cities lying on the path from city v to city u. Assume these people's IDs are p1, p2, ..., px in increasing order. 

If k = min(x, a), then Duff should tell Malek numbers k, p1, p2, ..., pk in this order. In the other words, Malek wants to know a minimums on that path (or less, if there are less than a people).

Duff is very busy at the moment, so she asked you to help her and answer the queries.

Input

The first line of input contains three integers, n, m and q (1 ≤ n, m, q ≤ 105).

The next n - 1 lines contain the roads. Each line contains two integers v and u, endpoints of a road (1 ≤ v, u ≤ n, v ≠ u).

Next line contains m integers c1, c2, ..., cm separated by spaces (1 ≤ ci ≤ n for each 1 ≤ i ≤ m).

Next q lines contain the queries. Each of them contains three integers, v, u and a (1 ≤ v, u ≤ n and 1 ≤ a ≤ 10).

Output

For each query, print numbers k, p1, p2, ..., pk separated by spaces in one line.

Examples

Input

5 4 5
1 3
1 2
1 4
4 5
2 1 4 3
4 5 6
1 5 2
5 5 10
2 3 3
5 3 1


Output

1 3
2 2 3
0
3 1 2 4
1 2

Note

Graph of Andarz Gu in the sample case is as follows (ID of people in each city are written next to them):

<image>

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream;
        if (args.length > 0 && args[0].equals("devTesting")) {
            try {
                inputStream = new FileInputStream(args[1]);
            } catch (FileNotFoundException e) {
                throw new RuntimeException(e);
            }
        } else {
            inputStream = System.in;
        }
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        int n, m, q, logn;
        List<Integer>[] graph, ids;
        int[] persons, parents, heights;
        BitSet vis;

        void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            m = in.nextInt();
            q = in.nextInt();
            logn = (int) Math.ceil(Math.log(n) / Math.log(2));
            graph = (ArrayList<Integer>[]) new ArrayList[n + 1];
            ids = (ArrayList<Integer>[]) new ArrayList[n + 1];
            for (int i = 0; i <= n; ++i) {
                graph[i] = new ArrayList<>();
                ids[i] = new ArrayList<>();
            }
            for (int i = 0; i < n - 1; ++i) {
                int v = in.nextInt();
                int u = in.nextInt();
                graph[v].add(u);
                graph[u].add(v);
            }
            persons = new int[m + 1];
            for (int i = 1; i <= m; ++i) {
                persons[i] = in.nextInt();
                ids[persons[i]].add(i);
            }
            for (int i = 1; i <= n; ++i) {
                Collections.sort(ids[i]);
            }
            parents = new int[n + 1];
            heights = new int[n + 1];
            vis = new BitSet();
            dfs(1);
            int[][][] table = new int[logn + 1][n + 1][11];
            pre(table, parents);
            for (int i = 0; i < q; ++i) {
                int v = in.nextInt();
                int u = in.nextInt();
                int a = in.nextInt();
                int[] get = Arrays.copyOfRange(query(table, v, u), 1, a + 1);
                int k = 0;
                for (int x : get) {
                    if (k < a && x < Integer.MAX_VALUE / 2) {
                        ++k;
                    }
                }
                out.print(k);
                for (int j = 0; j < k; ++j) {
                    out.print(" " + get[j]);
                }
                out.println();
            }
        }
        
        void pre(int[][][] table, int[] parents) {
            Arrays.fill(table[0][0], Integer.MAX_VALUE / 2);
            table[0][0][0] = 0;
            for (int v = 1; v <= n; ++v) {
                Arrays.fill(table[0][v], Integer.MAX_VALUE / 2);
                table[0][v][0] = parents[v];
                for (int i = 1; i <= Math.min(ids[v].size(), 10); ++i) {
                    table[0][v][i] = ids[v].get(i - 1);
                }
            }
            for (int i = 1; 1 << i < n; ++i) {
                for (int v = 0; v <= n; ++v) {
                    table[i][v][0] = table[i - 1][table[i - 1][v][0]][0];                        
                    int[] ptr = {1, 1};
                    if (table[i - 1][v][0] == 0 && table[i - 1][v][1] >= Integer.MAX_VALUE / 2 && table[i - 1][table[i - 1][v][0]][1] >= Integer.MAX_VALUE / 2) {
                        continue;
                    }
                    for (int j = 1; j <= 10; ++j) {
                        if (ptr[0] <= 10 && table[i - 1][v][ptr[0]] < table[i - 1][table[i - 1][v][0]][ptr[1]]) {
                            table[i][v][j] = table[i - 1][v][ptr[0]++];
                        } else {
                            table[i][v][j] = table[i - 1][table[i - 1][v][0]][ptr[1]++];
                        }
                    }
                }
                
            }
        }
        
        int[] query(int[][][] table, int u, int v) {
            if (u == v) {
                return table[0][u];
            }
            if (heights[u] < heights[v]) {
                int temp = u;
                u = v;
                v = temp;
            }
            int[] uaux = Arrays.copyOf(table[0][u], 11);
            for (int i = logn; i >= 0; --i) {
                if (heights[u] - (1 << i) >= heights[v]) {
                    uaux = merge(table[i][u], uaux, 10);
                    uaux[0] = table[i][u][0];
                    u = uaux[0];
                }
            }
            int[] vaux = Arrays.copyOf(table[0][v], 11);
            if (uaux[0] == v) {
                int[] ret = merge(uaux, vaux, 10);
                return ret;
            }
            for (int i = logn; i >= 0; --i) {
                if (table[i][u][0] != 0 && table[i][u][0] != table[i][v][0]) {
                    uaux = merge(uaux, table[i][u], 10);
                    uaux[0] = table[i][u][0];
                    u = uaux[0];
                    vaux = merge(vaux, table[i][v], 10);
                    vaux[0] = table[i][v][0];
                    v = vaux[0];                        
                }
            }
            uaux = merge(uaux, table[0][u], 10);
            uaux[0] = table[0][u][0];
            u = uaux[0];
            vaux = merge(vaux, table[0][v], 10);
            vaux[0] = table[0][v][0];
            v = vaux[0];
                        
            if (uaux[0] != 0) {
                uaux = merge(uaux, table[0][u], 10);
                uaux[0] = table[0][u][0];
                u = uaux[0];
            }
            int[] ret = merge(uaux, vaux, 10);
            return ret;
        }
        
        int[] merge(int[] a, int[] b, int cnt) {
            int[] ptr = {1, 1}, ret = new int[cnt + 1];
            Arrays.fill(ret, Integer.MAX_VALUE / 2);
            ret[0] = a[0];
            int i = 1;
            while (i <= cnt && ptr[0] <= 10 && ptr[1] <= 10) {
                if (ptr[0] <= cnt && a[ptr[0]] < b[ptr[1]]) {
                    ret[i++] = a[ptr[0]++];
                } else {
                    if (a[ptr[0]] > b[ptr[1]]) {
                        ret[i++] = b[ptr[1]];                       
                    }
                    ++ptr[1];
                }
            }
            return ret;
        }
        
        void dfs(int v) {
            vis.set(v);
            for (int w : graph[v]) {
                if (!vis.get(w)) {
                    parents[w] = v;
                    heights[w] = heights[v] + 1;
                    dfs(w);
                }
            }
        }

        int i(long x) {
            return (int) x;
        }

        <T> void heapsort(T[] a, int s, int e) {
            Queue<T> queue = new PriorityQueue<>();
            for (int i = s; i <= e; ++i) {
                queue.add(a[i]);
            }
            for (int i = s; i <= e; ++i) {
                a[i] = queue.poll();
            }
        }

    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public boolean hasInput() {
            try {
                if (tokenizer != null && tokenizer.hasMoreTokens()) {
                    return true;
                }
                reader.mark(1);
                int ch = reader.read();
                if (ch != -1) {
                    reader.reset();
                    return true;
                }
                return false;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }
}
/*
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Set;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream;
        if (args.length > 0 && args[0].equals("devTesting")) {
            try {
                inputStream = new FileInputStream(args[1]);
            } catch (FileNotFoundException e) {
                throw new RuntimeException(e);
            }
        } else {
            inputStream = System.in;
        }
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        Task solver = new Task();
        int n = 2;
        int K = 8;
        int[] query = {1, 2, 4};
        System.err.println(Arrays.toString(solver.solve(n, K, query)));
        out.close();
    }

    static class Task {
        
        static final int ANSWER_MODULO = (int) (1e9 + 7);

        public int[] solve(int n, int K, int[] query) {
            int[] res = new int[query.length];
            Arrays.fill(res, 1);
            for (int p = 2; p * p <= K; ++p)
                if (K % p == 0) {
                    int pw = 0;
                    while (K % p == 0) {
                        K /= p;
                        ++pw;
                    }
                    int[] cur = solveOne(query, n, p, pw);
                    multiplyBy(res, cur);
                }
            if (K > 1) {
                int[] cur = solveOne(query, n, K, 1);
                multiplyBy(res, cur);
            }
            return res;
        }

        private void multiplyBy(int[] res, int[] cur) {
            for (int i = 0; i < res.length; ++i) {
                res[i] = (int) ((res[i] * (long) cur[i]) % ANSWER_MODULO);
            }
        }

        private int[] solveOne(int[] query, int n, int p, int pw) {
            int prod = 1;
            for (int i = 0; i < pw; ++i) prod *= p;
            int[] ways = new int[pw + 1];
            ways[0] = 1;
            for (int i = 0; i < n; ++i) {
                int[] nways = new int[pw + 1];
                int already = 0;
                int got = 1;
                for (int cur = pw; cur >= 0; --cur) {
                    if (cur < pw) {
                        got *= p;
                    }
                    long here = got - already;
                    already = got;
                    for (int old = 0; old <= pw; ++old) {
                        int dst = Math.min(pw, old + cur);
                        nways[dst] = (int) ((nways[dst] + ways[old] * here) % ANSWER_MODULO);
                    System.err.println(Arrays.toString(nways));
                    }
                    System.err.println();
                }
                ways = nways;
            }
            int[] res = new int[query.length];
            long inv = BigInteger.valueOf(p - 1).modInverse(BigInteger.valueOf(ANSWER_MODULO)).longValue();
            long invp = BigInteger.valueOf(p).modInverse(BigInteger.valueOf(ANSWER_MODULO)).longValue();
            long pr = 1;
                    System.err.println(Arrays.toString(ways));
            for (int i = pw - 1; i >= 0; --i) {
                ways[i] = (int) ((ways[i] * inv) % ANSWER_MODULO);
                inv = inv * invp % ANSWER_MODULO;
            }
                    System.err.println(Arrays.toString(ways));
            for (int qi = 0; qi < query.length; ++qi) {
                int q = query[qi];
                q %= prod;
                if (q == 0) {
                    res[qi] = ways[pw];
                } else {
                    int need = 0;
                    while (q % p == 0) {
                        q /= p;
                        ++need;
                    }
                    res[qi] = ways[need];
                }
            }
            return res;
        }

    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public boolean hasInput() {
            try {
                if (tokenizer != null && tokenizer.hasMoreTokens()) {
                    return true;
                }
                reader.mark(1);
                int ch = reader.read();
                if (ch != -1) {
                    reader.reset();
                    return true;
                }
                return false;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }
}
*/

/*
import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.Map;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;
import java.util.TreeMap;
import java.util.TreeSet;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream;
        if (args.length > 0 && args[0].equals("devTesting")) {
            try {
                inputStream = new FileInputStream(args[1]);
            } catch (FileNotFoundException e) {
                throw new RuntimeException(e);
            }
        } else {
            inputStream = System.in;
        }
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskF solver = new TaskF();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskF {

        int sz;
        int n;
        Map<Integer, Integer> tree;

        void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            sz = (int) 1e9 + 1;
            BitSet vis = new BitSet();
            tree = new TreeMap<>();
            int last = -1;
            boolean okay = true;
            List<Integer> seq = new ArrayList<>();
            List<Integer> col = new ArrayList<>();
            for (int i = 0; i < n; ++i) {
                int a = in.nextInt();
                int c = in.nextInt();
                if (!vis.get(c)) {
                    add(tree, a, 1);
                    vis.set(c);
                } else {
                    if (last != -1 && c != last) {
                        okay = false;
                    }
                }
                seq.add(a);
                col.add(c);
                last = c;
            }
//            System.err.println(sum(tree, 1999));
//            System.err.println(sum(tree, 2998) - sum(tree, 1999));
//            System.err.println();
            for (int i = 1; i <= 3000; ++i) {
//                System.err.println("i: " + i + " " + sum(tree, i));
            }
            int ans = 0;
            for (int m = 1; m <= 2 * seq.get(seq.size() - 1); ++m) {
                last = -1;
                int ptr = 0;
                okay = true;
                while (true) {
                    int idx = Collections.binarySearch(seq, ptr);
                    if (idx < 0) {
                        idx = ~idx;
                    }
                    if (idx < seq.size()) {
                        if (idx > 0 && col.get(idx - 1) == col.get(idx) && seq.get(idx) - seq.get(idx - 1) <= m|| idx < n - 1 && col.get(idx + 1) == col.get(idx) && seq.get(idx + 1) - seq.get(idx) <= m) {
                            okay = false;
                            break;
                        }
                       if (sum(tree, ptr + m) - sum(tree, ptr) > 1) {
                            okay = false;
                        break;
                        }
                        if (sum(tree, ptr + 2 * m) - sum(tree, ptr + m) > 1) {
                            okay = false;
                            break;
                        }
                    } else {
                        if (sum(tree, ptr + m) - sum(tree, ptr) > 1) {
                            okay = false;
                        }
                        if (sum(tree, ptr + 2 * m) - sum(tree, ptr + m) > 1) {
//                            okay = false;
                        }
                        break;
                    }
//                    if (m > 3000)
//                        System.err.println("** " + (sum(tree, ptr - 1) - sum(tree, ptr - m)));
                    if (sum(tree, ptr + m) - sum(tree, ptr) > 1) {
                        okay = false;
                        break;
                    }
                        if (sum(tree, ptr + 2 * m) - sum(tree, ptr + m) > 1) {
//                            okay = false;
//                            break;
                        }
                    ptr += m;
//                    last = col.get(idx);
                }
                if (okay) {
                    System.err.println(">> " + m);
                    ++ans;
                }
            }
            System.err.println(ans);
        }

        void add(Map<Integer, Integer> tree, int x, int v) {
            while (x <= sz) {
                if (!tree.containsKey(x)) {
                    tree.put(x, v);
                } else {
                    tree.put(x, tree.get(x) + v);
                }
                x += (x & -x);
            }
        }

        int sum(Map<Integer, Integer> tree, int x) {
            int ret = 0;
            while (x != 0) {
                if (tree.containsKey(x)) {
                    ret += tree.get(x);                  
                }
                x -= (x & -x);
            }
            return ret;
        }

        int i(long x) {
            return (int) x;
        }

        <T> void heapsort(T[] a, int s, int e) {
            Queue<T> queue = new PriorityQueue<>();
            for (int i = s; i <= e; ++i) {
                queue.add(a[i]);
            }
            for (int i = s; i <= e; ++i) {
                a[i] = queue.poll();
            }
        }

    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public boolean hasInput() {
            try {
                if (tokenizer != null && tokenizer.hasMoreTokens()) {
                    return true;
                }
                reader.mark(1);
                int ch = reader.read();
                if (ch != -1) {
                    reader.reset();
                    return true;
                }
                return false;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }
}
*/

// /*




// */


/*

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.FileNotFoundException;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.BitSet;
import java.util.Collections;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) {
        InputStream inputStream;
        if (args.length > 0 && args[0].equals("devTesting")) {
            try {
                inputStream = new FileInputStream(args[1]);
            } catch (FileNotFoundException e) {
                throw new RuntimeException(e);
            }
        } else {
            inputStream = System.in;
        }
        OutputStream outputStream = System.out;
        InputReader in = new InputReader(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        TaskC solver = new TaskC();
        solver.solve(1, in, out);
        out.close();
    }

    static class TaskC {
        int n, m, q, logn;
        List<Integer>[] graph, ids;
        int[] persons, parents, heights;
        BitSet vis;

        void solve(int testNumber, InputReader in, PrintWriter out) {
            n = in.nextInt();
            m = in.nextInt();
            q = in.nextInt();
            logn = (int) Math.ceil(Math.log(n) / Math.log(2));
            graph = (ArrayList<Integer>[]) new ArrayList[n + 1];
            ids = (ArrayList<Integer>[]) new ArrayList[n + 1];
            for (int i = 0; i <= n; ++i) {
                graph[i] = new ArrayList<>();
                ids[i] = new ArrayList<>();
            }
            for (int i = 0; i < n - 1; ++i) {
                int v = in.nextInt();
                int u = in.nextInt();
                graph[v].add(u);
                graph[u].add(v);
            }
            persons = new int[m + 1];
            for (int i = 1; i <= m; ++i) {
                persons[i] = in.nextInt();
                ids[persons[i]].add(i);
            }
            for (int i = 1; i <= m; ++i) {
                Collections.sort(ids[i]);
            }
            parents = new int[n + 1];
            heights = new int[n + 1];
            vis = new BitSet();
            dfs(1);
//            System.err.println("> " + Arrays.toString(heights));
            int[][][] table = new int[logn + 1][n + 1][11];
            pre(table, parents);
//            for (int[] i : table[1]) {
//                System.err.println(Arrays.toString(i));
//            }
            for (int i = 0; i < q; ++i) {
                int v = in.nextInt();
                int u = in.nextInt();
                int a = in.nextInt();
                int[] get = Arrays.copyOfRange(query(table, v, u), 1, a + 1);
                System.err.println(">> " + Arrays.toString(get));
                int k = 0;
                for (int x : get) {
                    if (k < a && x < Integer.MAX_VALUE / 2) {
                        ++k;
                    }
                }
                System.out.print(k);
                for (int j = 0; j < k; ++j) {
                    System.out.print(" " + get[j]);
                }
                System.out.println();
            }
        }
        
        void pre(int[][][] table, int[] parents) {
            Arrays.fill(table[0][0], Integer.MAX_VALUE / 2);
            table[0][0][0] = 0;
            for (int v = 1; v <= n; ++v) {
                Arrays.fill(table[0][v], Integer.MAX_VALUE / 2);
                table[0][v][0] = parents[v];
                for (int i = 1; i <= Math.min(ids[v].size(), 10); ++i) {
                    table[0][v][i] = ids[v].get(i - 1);
                }
            }
            for (int i = 1; 1 << i < n; ++i) {
                for (int v = 0; v <= n; ++v) {
                    table[i][v][0] = table[i - 1][table[i - 1][v][0]][0];                        
                    int[] ptr = {1, 1};
                    if (table[i - 1][v][0] == 0 && table[i - 1][v][1] >= Integer.MAX_VALUE / 2 && table[i - 1][table[i - 1][v][0]][1] >= Integer.MAX_VALUE / 2) {
                        continue;
                    }
                    for (int j = 1; j <= 10; ++j) {
                        if (ptr[0] <= 10 && table[i - 1][v][ptr[0]] < table[i - 1][table[i - 1][v][0]][ptr[1]]) {
                            table[i][v][j] = table[i - 1][v][ptr[0]++];
                        } else {
                            table[i][v][j] = table[i - 1][table[i - 1][v][0]][ptr[1]++];
                        }
                    }
                }
                
            }
        }
        
        int[] query(int[][][] table, int u, int v) {
            if (u == v) {
                return table[0][u];
            }
            if (heights[u] < heights[v]) {
                int temp = u;
                u = v;
                v = temp;
            }
            int[] uaux = Arrays.copyOf(table[0][u], 11);
            System.err.println("10 *** " + u);
            System.err.println("20 *** " + v);
            for (int i = logn; i >= 0; --i) {
                if (heights[u] - (1 << i) >= heights[v]) {
                    uaux = merge(table[i][u], uaux, 10);
                    uaux[0] = table[i][u][0];
                    u = uaux[0];
//                System.err.println("100 >>> exec " + u);
                }
            }
            int[] vaux = Arrays.copyOf(table[0][v], 11);
                System.err.println("???? " + Arrays.toString(uaux) + " " + Arrays.toString(vaux));
            if (uaux[0] == v) {
                int[] ret = merge(uaux, vaux, 10);
//                System.err.println(">>> by this");
                return ret;
            }
            System.err.println("50 *** " + u);
            System.err.println("60 *** " + v);
            for (int i = logn; i >= 0; --i) {
                if (table[i][u][0] != 0 && table[i][u][0] != table[i][v][0]) {
                System.err.println("200 >>> exec");
//            System.err.println("10 *** " + uaux[0]);
//            System.err.println("20 *** " + vaux[0]);
                    uaux = merge(uaux, table[i][u], 10);
                    uaux[0] = table[i][u][0];
                    u = uaux[0];
                    vaux = merge(vaux, table[i][v], 10);
                    vaux[0] = table[i][v][0];
                    v = vaux[0];                        
                System.err.println("???? " + Arrays.toString(uaux) + " " + Arrays.toString(vaux));
                }
            }
            System.err.println("70 *** " + u);
            System.err.println("80 *** " + v);
                System.err.println("???? " + Arrays.toString(uaux) + " " + Arrays.toString(vaux));
                System.err.println("???? " + table[0][u][0]);
                System.err.println("???? " + table[0][v][0]);
                    if (table[0][u][0] != 0) {
                        uaux = merge(uaux, table[0][u], 10);
                        uaux[0] = table[0][u][0];
                        u = uaux[0];
                    }
                    if (table[0][v][0] != 0) {
                        vaux = merge(vaux, table[0][v], 10);
                        vaux[0] = table[0][v][0];
                        v = vaux[0];
                    }
                        
            System.err.println("100 *** " + u);
            System.err.println("110 *** " + v);
                System.err.println("???? " + Arrays.toString(uaux) + " " + Arrays.toString(vaux));
//            System.err.println();
//            System.err.println("1 *** " + uaux[0]);
//            System.err.println("2 *** " + vaux[0]);
//            if (uaux[0] != 0) {
                uaux = merge(uaux, table[0][u], 10);
                uaux[0] = table[0][u][0];
                u = uaux[0];
//            }
            System.err.println("140 *** " + u);
            System.err.println("150 *** " + v);
                System.err.println("???? " + Arrays.toString(uaux) + " " + Arrays.toString(vaux));
//            if (vaux[0] != 0) {
//                vaux = merge(vaux, table[0][vaux[0]], 10);
//                vaux[0] = table[0][vaux[0]][0];                
//            }
//            System.err.println("3 *** " + uaux[0]);
//            System.err.println("4 *** " + vaux[0]);
            int[] ret = merge(uaux, vaux, 10);
//                System.err.println("!!!!! " + Arrays.toString(ret));
//            if (uaux[0] != 0) {
//                System.err.println(">>> pre");
//                System.err.println(u);
//                System.err.println(ids[u]);
//                System.err.println(Arrays.toString(ret));
//                int[] aux = new int[11];
//                Arrays.fill(aux, Integer.MAX_VALUE / 2);
//                for (int i = 0; i < ids[uaux[0]].size(); ++i) {
//                    aux[i + 1] = ids[uaux[0]].get(i);
//                }
//                ret = merge(ret, aux, 10);
//                aux[0] = ret[0];
//            } 
                System.err.println(">>> by that");
            return ret;
        }
        
        int[] merge(int[] a, int[] b, int cnt) {
            int[] ptr = {1, 1}, ret = new int[cnt + 1];
            Arrays.fill(ret, Integer.MAX_VALUE / 2);
            ret[0] = a[0];
            int i = 1;
            while (i <= cnt && ptr[0] <= 10 && ptr[1] <= 10) {
                if (ptr[0] <= cnt && a[ptr[0]] < b[ptr[1]]) {
                    ret[i++] = a[ptr[0]++];
                } else {
                    if (a[ptr[0]] > b[ptr[1]]) {
                        ret[i++] = b[ptr[1]];                       
                    }
                    ++ptr[1];
                }
            }
            return ret;
        }
        
        void dfs(int v) {
            vis.set(v);
            for (int w : graph[v]) {
                if (!vis.get(w)) {
                    parents[w] = v;
                    heights[w] = heights[v] + 1;
                    dfs(w);
                }
            }
        }

        int i(long x) {
            return (int) x;
        }

        <T> void heapsort(T[] a, int s, int e) {
            Queue<T> queue = new PriorityQueue<>();
            for (int i = s; i <= e; ++i) {
                queue.add(a[i]);
            }
            for (int i = s; i <= e; ++i) {
                a[i] = queue.poll();
            }
        }

    }

    static class InputReader {

        public BufferedReader reader;
        public StringTokenizer tokenizer;

        public InputReader(InputStream stream) {
            reader = new BufferedReader(new InputStreamReader(stream));
            tokenizer = null;
        }

        public String next() {
            while (tokenizer == null || !tokenizer.hasMoreTokens()) {
                try {
                    tokenizer = new StringTokenizer(reader.readLine());
                } catch (IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return tokenizer.nextToken();
        }

        public String nextLine() {
            try {
                return reader.readLine();
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

        public int nextInt() {
            return Integer.parseInt(next());
        }

        public long nextLong() {
            return Long.parseLong(next());
        }

        public double nextDouble() {
            return Double.parseDouble(next());
        }

        public boolean hasInput() {
            try {
                if (tokenizer != null && tokenizer.hasMoreTokens()) {
                    return true;
                }
                reader.mark(1);
                int ch = reader.read();
                if (ch != -1) {
                    reader.reset();
                    return true;
                }
                return false;
            } catch (IOException e) {
                throw new RuntimeException(e);
            }
        }

    }
}


*/