Problem: The company X has n employees numbered from 1 through n. Each employee u has a direct boss p_u (1 ≤ p_u ≤ n), except for the employee 1 who has no boss. It is guaranteed, that values p_i form a tree. Employee u is said to be in charge of employee v if u is the direct boss of v or there is an employee w such that w is in charge of v and u is the direct boss of w. Also, any employee is considered to be in charge of himself.

In addition, for each employee u we define it's level lv(u) as follow: 

  * lv(1)=0 
  * lv(u)=lv(p_u)+1 for u ≠ 1 



In the near future, there are q possible plans for the company to operate. The i-th plan consists of two integers l_i and r_i, meaning that all the employees in the range [l_i, r_i], and only they, are involved in this plan. To operate the plan smoothly, there must be a project manager who is an employee in charge of all the involved employees. To be precise, if an employee u is chosen as the project manager for the i-th plan then for every employee v ∈ [l_i, r_i], u must be in charge of v. Note, that u is not necessary in the range [l_i, r_i]. Also, u is always chosen in such a way that lv(u) is as large as possible (the higher the level is, the lower the salary that the company has to pay the employee).

Before any plan is operated, the company has JATC take a look at their plans. After a glance, he tells the company that for every plan, it's possible to reduce the number of the involved employees exactly by one without affecting the plan. Being greedy, the company asks JATC which employee they should kick out of the plan so that the level of the project manager required is as large as possible. JATC has already figured out the answer and challenges you to do the same.

Input

The first line contains two integers n and q (2 ≤ n ≤ 100 000, 1 ≤ q ≤ 100 000) — the number of employees and the number of plans, respectively.

The second line contains n-1 integers p_2, p_3, ..., p_n (1 ≤ p_i ≤ n) meaning p_i is the direct boss of employee i.

It is guaranteed, that values p_i form a directed tree with the root of 1.

Each of the following q lines contains two integers l_i and r_i (1 ≤ l_i<r_i ≤ n) — the range of the employees, involved in the corresponding plan.

Output

Print q lines, each containing two integers — the number of the employee which should be kicked from the corresponding plan and the maximum possible level of the project manager in that case.

If there are more than one way to choose that employee, print any of them.

Example

Input

11 5
1 1 3 3 3 4 2 7 7 6
4 6
4 8
1 11
9 11
8 11


Output

4 1
8 1
1 0
11 3
8 1

Note

In the example: 

<image> In the first query, we can choose whether 4 or 5 or 6 and the project manager will be 3.

In the second query, if we choose any employee other than the employee 8, the project manager will be 1. If we choose 8, the project manager will be 3. Since lv(3)=1 > lv(1)=0, choosing 8 is the best strategy.

In the third query, no matter how we choose the employee, the project manager will always be 1.

In the fourth query, if we choose 9 or 10 then the project manager will be 3. If we choose 11 then the project manager will be 7. Since lv(7)=3>lv(3)=1, we choose 11 as the answer.

Solution (in JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.util.Arrays;
import java.lang.reflect.Array;
import java.util.function.BiFunction;
import java.util.function.Supplier;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.Map;
import java.util.function.IntFunction;
import java.io.PrintWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.stream.Collectors;
import java.util.stream.Stream;
import java.io.BufferedReader;
import java.util.Comparator;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Nikita Mikhailov
 */
public class Main {
    public static void main(String[] args) {
        InputStream inputStream = System.in;
        OutputStream outputStream = System.out;
        FastScanner in = new FastScanner(inputStream);
        PrintWriter out = new PrintWriter(outputStream);
        EKompaniya solver = new EKompaniya();
        solver.solve(1, in, out);
        out.close();
    }

    static class EKompaniya {
        public void solve(int testNumber, FastScanner in, PrintWriter out) {
            int n = in.readInt();
            int q = in.readInt();

            TreeGraph tree = new TreeGraph(n);
            for (int i = 1; i < n; i++) {
                tree.addEdgeBi(i, in.readInt() - 1);
            }

            GraphDfs dfs = new GraphDfs(tree, 0, new GraphDfs.DepthMetric(), new GraphDfs.OrderMetric());
            int[] firstInOrder = new int[n];
            Arrays.fill(firstInOrder, -1);

            ArrayList<Integer> order = dfs.order();
            for (int i = 0; i < order.size(); i++) {
                if (firstInOrder[order.get(i)] == -1) {
                    firstInOrder[order.get(i)] = i;
                }
            }

            TreeLcm lcm = new TreeLcm(tree, 0);

            KthStatisticFactory<IntPair> statFac = new KthStatisticFactory<>(2, IntPair[]::new, IntPair::compareTo);
            KthStatisticFactory<IntPair> statFacRev = new KthStatisticFactory<>(2, IntPair[]::new, Comparator.<IntPair>reverseOrder());

            SegmentTree<KthStatisticFastTwo<IntPair>> segForFirst = new SegmentTree<>(n, KthStatisticFastTwo::merge);
            SegmentTree<KthStatisticFastTwo<IntPair>> segForLast = new SegmentTree<>(n, KthStatisticFastTwo::merge);

            // SegmentTree<Integer> segForLcm = new SegmentTree<>(n, lcm::getLcm);

            int[] depth = dfs.depth();


            for (int i = 0; i < n; i++) {
                segForFirst.set(i, statFac.getStat(new IntPair(firstInOrder[i], i)));
                segForLast.set(i, statFacRev.getStat(new IntPair(firstInOrder[i], i)));
                // segForLcm.set(i, i);
            }

            for (int i = 0; i < q; i++) {
                int from = in.readInt() - 1;
                int to = in.readInt() - 1;

                if (to - from == 1) {
                    if (depth[from] >= depth[to]) {
                        out.println((to + 1) + " " + depth[from]);
                    } else {
                        out.println((from + 1) + " " + depth[to]);
                    }

                    continue;
                }

                IntPair[] first = segForFirst.getSum(from, to).get();
                IntPair[] last = segForLast.getSum(from, to).get();

                int lcm1 = lcm.getLcm(first[1].y(), last[0].y());
                int lcm2 = lcm.getLcm(first[0].y(), last[1].y());

                if (depth[lcm1] >= depth[lcm2]) {
                    out.println((first[0].y() + 1) + " " + depth[lcm1]);
                } else {
                    out.println((last[0].y() + 1) + " " + depth[lcm2]);
                }


            }

//        for (int i = 0; i < q; i++) {
//            int from = in.readInt() - 1;
//            int to = in.readInt() - 1;
//
//            Function<Integer, Integer> calc = (remId) -> {
//                int lcm1 = remId > from ? segForLcm.getSum(from, remId - 1) : -1;
//                int lcm2 = remId < to ? segForLcm.getSum(remId + 1, to) : -1;
//                int lcm0;
//                if (lcm1 >= 0 && lcm2 >= 0) {
//                    lcm0 = lcm.getLcm(lcm1, lcm2);
//                } else if (lcm1 >= 0) {
//                    lcm0 = lcm1;
//                } else {
//                    lcm0 = lcm2;
//                }
//                return lcm0;
//            };
//
//            int rem1 = segForFirst.getSum(from, to).y();
//            int rem2 = segForLast.getSum(from, to).y();
//            int lcm1 = calc.apply(rem1);
//            int lcm2 = calc.apply(rem2);
//
//            int remId = depth[lcm1] <= depth[lcm2] ? rem2 : rem1;
//            int lcm0 = depth[lcm1] <= depth[lcm2] ? lcm2 : lcm1;
//
//
//            out.println((remId + 1) + " " + depth[lcm0]);
//        }
        }

    }

    static final class Utils {
        private Utils() {
        }

        public static <T extends Comparable<T>> T minBinFn(T a, T b) {
            return minBinFn(T::compareTo).apply(a, b);
        }

        public static <T> BiFunction<T, T, T> minBinFn(Comparator<T> comparator) {
            return (a, b) -> comparator.compare(a, b) <= 0 ? a : b;
        }

        public static <T> T[] makeArrayInd(int n, IntFunction<T> creator) {
            if (n > 0) {
                T first = creator.apply(0);
                T[] res = (T[]) Array.newInstance(first.getClass(), n);
                res[0] = first;

                for (int i = 1; i < n; i++) {
                    res[i] = creator.apply(i);
                }

                return res;
            } else {
                return (T[]) new Object[0];
            }
        }

        public static <T> T[] makeArray(int n, Supplier<T> creator) {
            return makeArrayInd(n, value -> creator.get());
        }

    }

    static class KthStatisticFastTwo<T> {
        private T[] stats;
        private KthStatisticFactory<T> factory;

        protected KthStatisticFastTwo(KthStatisticFactory<T> factory, T[] vals) {
            this.factory = factory;

            stats = factory.supplier.apply(2);

            stats[0] = vals[0];
            if (vals.length > 1) {
                stats[1] = vals[1];
            }
        }

        public void addValue(T a) {
            if (a == null) return;

            if (stats[0] == null || factory.comparator.compare(a, stats[0]) <= 0) {
                stats[1] = stats[0];
                stats[0] = a;
            } else if (stats[1] == null || factory.comparator.compare(a, stats[1]) <= 0) {
                stats[1] = a;
            }
        }

        public T[] get() {
            return stats;
        }

        static public <U> KthStatisticFastTwo<U> merge(KthStatisticFastTwo<U> a, KthStatisticFastTwo<U> b) {
            if (a.factory != b.factory) {
                throw new RuntimeException();
            }

            KthStatisticFastTwo<U> res = new KthStatisticFastTwo<>(a.factory, a.stats);
            for (U stat : b.stats) {
                res.addValue(stat);
            }

            return res;
        }

    }

    static class SegmentTree<T> {
        private ArrayList<T> arr;
        private int n;
        private BiFunction<T, T, T> ops;
        private boolean hadQueries = false;

        public SegmentTree(int size, BiFunction<T, T, T> ops) {
            this.ops = ops;
            int len = 1;
            while (len < size) {
                len *= 2;
            }
            this.n = len;

            arr = new ArrayList<>(2 * n + 1);
            for (int i = 0; i < 2 * n + 1; i++) {
                arr.add(null);
            }
        }

        private T refreshTree(int pos) {
            if (pos >= n) {
                return arr.get(pos);
            }

            T sum = doSum(refreshTree(pos * 2), refreshTree(pos * 2 + 1));
            arr.set(pos, sum);
            return sum;
        }

        public void set(int pos, T value) {
            pos += n;
            arr.set(pos, value);

            // Don't refresh tree yet
            if (!hadQueries) {
                return;
            }

            pos /= 2;

            while (pos >= 1) {
                arr.set(pos, doSum(arr.get(2 * pos), arr.get(2 * pos + 1)));
                pos /= 2;
            }
        }

        public T getSum(int from, int to) {
            if (!hadQueries) {
                hadQueries = true;
                refreshTree(1);
            }
            return getSum(1, 0, n - 1, from, to);
        }

        private T doSum(T a, T b) {
            if (a == null) {
                return b;
            }
            if (b == null) {
                return a;
            }
            return ops.apply(a, b);
        }

        private T getSum(int subTreeRoot, int subTreeFrom, int subTreeTo, int from, int to) {
            if (from == subTreeFrom && to == subTreeTo)
                return arr.get(subTreeRoot);

            int middle = (subTreeFrom + subTreeTo) / 2;

            if (to <= middle) {
                return getSum(subTreeRoot * 2, subTreeFrom, middle, from, to);
            }

            if (from > middle) {
                return getSum(subTreeRoot * 2 + 1, middle + 1, subTreeTo, from, to);
            }

            T leftSum = getSum(subTreeRoot * 2, subTreeFrom, middle, from, middle);
            T rightSum = getSum(subTreeRoot * 2 + 1, middle + 1, subTreeTo, middle + 1, to);

            return ops.apply(leftSum, rightSum);
        }

    }

    static class KthStatisticFactory<T> {
        protected Comparator<T> comparator;
        protected int size;
        protected IntFunction<T[]> supplier;

        public KthStatisticFactory(int size, IntFunction<T[]> supplier, Comparator<T> comparator) {
            this.comparator = Comparator.nullsLast(comparator);
            this.size = size;
            this.supplier = supplier;
        }

        public KthStatisticFastTwo<T> getStat(T... vals) {
            return new KthStatisticFastTwo<T>(this, vals);
        }

    }

    static class TreeGraph {
        protected int n;
        protected ArrayList<Integer>[] edges;

        public TreeGraph(int n) {
            this.n = n;
            this.edges = Utils.makeArray(n, ArrayList::new);
        }

        public void addEdge(int from, int to) {
            edges[from].add(to);
        }

        public void addEdgeBi(int a, int b) {
            addEdge(a, b);
            addEdge(b, a);
        }

    }

    static class TreeLcm {
        private TreeGraph graph;
        private int root;
        private SegmentTree<IntPair> seg;
        private int[] first;

        public TreeLcm(TreeGraph graph, int root) {
            this.graph = graph;
            this.root = root;

            this.lcm();
        }

        private void lcm() {
            GraphDfs dfs = new GraphDfs(graph, root, new GraphDfs.OrderMetric(), new GraphDfs.DepthMetric());

            int[] depth = dfs.depth();
            ArrayList<Integer> order = dfs.order();

            first = new int[graph.n];
            Arrays.fill(first, -1);

            for (int i = 0; i < order.size(); i++) {
                int node = order.get(i);

                if (first[node] == -1) {
                    first[node] = i;
                }
            }

            seg = new SegmentTree<>(order.size(), Utils::minBinFn);

            for (int i = 0; i < order.size(); i++) {
                seg.set(i, new IntPair(depth[order.get(i)], order.get(i)));
            }
        }

        public int getLcm(int a, int b) {
            int from = Math.min(first[a], first[b]);
            int to = Math.max(first[a], first[b]);

            return seg.getSum(from, to).y();
        }

    }

    static class Pair<K, V> {
        private final K key;
        private final V value;

        public Pair(K k, V v) {
            key = k;
            value = v;
        }

        public Pair(Pair<? extends K, ? extends V> entry) {
            this(entry.getKey(), entry.getValue());
        }

        public K getKey() {
            return key;
        }

        public V getValue() {
            return value;
        }

        public K getFirst() {
            return key;
        }

        public V getSecond() {
            return value;
        }

        public boolean equals(Object o) {
            if (this == o) {
                return true;
            }
            if (!(o instanceof Pair)) {
                return false;
            } else {
                Pair<?, ?> oP = (Pair<?, ?>) o;
                return (key == null ?
                        oP.key == null :
                        key.equals(oP.key)) &&
                        (value == null ?
                                oP.value == null :
                                value.equals(oP.value));
            }
        }

        public int hashCode() {
            int result = key == null ? 0 : key.hashCode();

            final int h = value == null ? 0 : value.hashCode();
            result = 37 * result + h ^ (h >>> 16);

            return result;
        }

        public String toString() {
            return "[" + getKey() + ", " + getValue() + "]";
        }

    }

    static class GraphDfs {
        private TreeGraph graph;
        private Map<Class, GraphDfs.DfsMetric> metrics;

        public GraphDfs(TreeGraph graph, int startNode, GraphDfs.DfsMetric... requiredMetrics) {

            this.metrics = Stream.of(requiredMetrics).collect(Collectors.toMap(Object::getClass, o -> o));

            this.graph = graph;

            metrics.values().forEach(dfsMetric -> dfsMetric.init(graph.n));

            this.dfs(startNode, -1);
        }

        private void dfs(int node, int from) {
            metrics.values().forEach(dfsMetric -> dfsMetric.onEnter(node, from, true));


            for (int target : graph.edges[node]) {
                if (target != from) {
                    dfs(target, node);
                    metrics.values().forEach(dfsMetric -> dfsMetric.onEnter(node, target, false));
                }
            }

            metrics.values().forEach(dfsMetric -> dfsMetric.onLeave(node, from));
        }

        public <T extends GraphDfs.DfsMetric> T metric(Class<T> c) {
            return (T) metrics.get(c);
        }

        public ArrayList<Integer> order() {
            return metric(GraphDfs.OrderMetric.class).order;
        }

        public int[] depth() {
            return metric(GraphDfs.DepthMetric.class).depth;
        }

        public interface DfsMetric {
            void init(int size);

            void onEnter(int node, int from, boolean firstTime);

            void onLeave(int node, int to);

        }

        public static class DepthMetric implements GraphDfs.DfsMetric {
            public int[] depth;

            public void init(int size) {
                depth = new int[size];
                Arrays.fill(depth, -1);
            }

            public void onEnter(int node, int from, boolean firstTime) {
                if (firstTime) {
                    depth[node] = from == -1 ? 0 : depth[from] + 1;
                }
            }

            public void onLeave(int node, int to) {
            }

        }

        public static class OrderMetric implements GraphDfs.DfsMetric {
            public ArrayList<Integer> order;

            public void init(int size) {
                order = new ArrayList<>(size * 2);
            }

            public void onEnter(int node, int from, boolean firstTime) {
                order.add(node);
            }

            public void onLeave(int node, int to) {
            }

        }

    }

    static class FastScanner {
        private StringTokenizer st;
        private BufferedReader in;

        public FastScanner(final InputStream in) {
            this.in = new BufferedReader(new InputStreamReader(in));
        }

        public String readToken() {
            while (st == null || !st.hasMoreTokens()) {
                try {
                    st = new StringTokenizer(in.readLine());
                } catch (final IOException e) {
                    throw new RuntimeException(e);
                }
            }
            return st.nextToken();
        }

        public int readInt() {
            return Integer.parseInt(readToken());
        }

    }

    static class IntPair extends Pair<Integer, Integer> implements Comparable<IntPair> {
        public IntPair(Integer integer, Integer integer2) {
            super(integer, integer2);
        }

        public IntPair(Pair<? extends Integer, ? extends Integer> entry) {
            super(entry);
        }

        public Integer x() {
            return getFirst();
        }

        public Integer y() {
            return getSecond();
        }

        public int compareTo(IntPair o) {
            if (x().equals(o.x())) {
                return y().compareTo(o.y());
            }
            return x().compareTo(o.x());
        }

    }
}