#include <bits/stdc++.h>
const int MAXN = 100010, inf = 2147483233;
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  while (!isdigit(ch)) {
    if (ch == '-') f = -1;
    ch = getchar();
  }
  while (isdigit(ch)) {
    x = x * 10 + ch - '0';
    ch = getchar();
  }
  return x * f;
}
int n, q, tot, nxt[MAXN << 1], to[MAXN << 1], fst[MAXN], cnt;
int fa[MAXN], hsh[MAXN], dep[MAXN], f[MAXN][25], HSH[MAXN], size[MAXN];
int mx[MAXN << 2][2], mn[MAXN << 2][2], mx1, mx2, mn1, mn2;
namespace hh {
using namespace std;
inline int read() {
  int x = 0, f = 1;
  char ch = getchar();
  for (; !isdigit(ch); ch = getchar())
    if (ch == '-') f = -f;
  for (; isdigit(ch); ch = getchar()) x = 10 * x + ch - '0';
  return x * f;
}
const int maxn = 500010;
int n, m, lastans;
int first[maxn], to[maxn << 1], nx[maxn << 1], cnt;
inline void add(int u, int v) {
  to[++cnt] = v;
  nx[cnt] = first[u];
  first[u] = cnt;
}
inline void ins(int u, int v) {
  add(u, v);
  add(v, u);
}
namespace LCA {
int dep[maxn], bl[maxn], fa[maxn], size[maxn];
inline void dfs1(int x) {
  size[x] = 1;
  for (int i = first[x]; i; i = nx[i]) {
    if (to[i] == fa[x]) continue;
    fa[to[i]] = x;
    dep[to[i]] = dep[x] + 1;
    dfs1(to[i]);
    size[x] += size[to[i]];
  }
}
inline void dfs2(int x, int col) {
  int k = 0;
  bl[x] = col;
  for (int i = first[x]; i; i = nx[i])
    if (dep[to[i]] > dep[x] && size[to[i]] > size[k]) k = to[i];
  if (!k) return;
  dfs2(k, col);
  for (int i = first[x]; i; i = nx[i])
    if (dep[to[i]] > dep[x] && to[i] != k) dfs2(to[i], to[i]);
}
inline int lca(int x, int y) {
  while (bl[x] != bl[y]) {
    if (dep[bl[x]] < dep[bl[y]]) swap(x, y);
    x = fa[bl[x]];
  }
  return dep[x] > dep[y] ? y : x;
}
}  // namespace LCA
namespace SEG {
int root[maxn][2], ls[maxn << 4], rs[maxn << 4], val[maxn << 4], size;
inline void Insert(int &x, int l, int r, int pos, int va) {
  if (!x) x = ++size;
  val[x] += va;
  if (l == r) return;
  int mid = (l + r) >> 1;
  if (pos <= mid)
    Insert(ls[x], l, mid, pos, va);
  else
    Insert(rs[x], mid + 1, r, pos, va);
}
inline int query(int x, int l, int r, int L, int R) {
  if (!x) return 0;
  if (L <= l && r <= R) return val[x];
  int mid = (l + r) >> 1, ans = 0;
  if (L <= mid) ans += query(ls[x], l, mid, L, R);
  if (R > mid) ans += query(rs[x], mid + 1, r, L, R);
  return ans;
}
}  // namespace SEG
inline int q_dis(int x, int y) {
  return LCA::dep[x] + LCA::dep[y] - (LCA::dep[LCA::lca(x, y)] << 1);
}
int size[maxn], f[maxn], vis[maxn], d[maxn], v[maxn], son, root;
int nfa[maxn];
inline void solve(int rt, int type, int x, int fa) {
  SEG::Insert(SEG::root[rt][type], 0, n, d[x], v[x]);
  for (int i = first[x]; i; i = nx[i]) {
    if (to[i] == fa || vis[to[i]]) continue;
    d[to[i]] = d[x] + 1;
    solve(rt, type, to[i], x);
  }
}
inline void getroot(int x, int fa) {
  size[x] = 1, f[x] = 0;
  for (int i = first[x]; i; i = nx[i]) {
    if (to[i] == fa || vis[to[i]]) continue;
    getroot(to[i], x);
    size[x] += size[to[i]];
    f[x] = max(f[x], size[to[i]]);
  }
  f[x] = max(f[x], son - size[x]);
  if (f[x] < f[root]) root = x;
}
inline void work(int x) {
  vis[x] = 1;
  d[x] = 0;
  solve(x, 0, x, 0);
  for (int i = first[x]; i; i = nx[i]) {
    if (vis[to[i]]) continue;
    son = size[to[i]];
    root = 0;
    d[to[i]] = 1;
    getroot(to[i], 0);
    solve(root, 1, to[i], x);
    nfa[root] = x;
    work(root);
  }
}
inline int query(int x, int k) {
  int ret = SEG::query(SEG::root[x][0], 0, n, 0, k);
  for (int i = x; nfa[i]; i = nfa[i]) {
    int du = q_dis(x, nfa[i]);
    ret += SEG::query(SEG::root[nfa[i]][0], 0, n, 0, k - du);
    ret -= SEG::query(SEG::root[i][1], 0, n, 0, k - du);
  }
  return ret;
}
inline void update(int x, int k) {
  int delt = k - SEG::query(SEG::root[x][0], 0, n, 0, 0);
  SEG::Insert(SEG::root[x][0], 0, n, 0, delt);
  for (int i = x; nfa[i]; i = nfa[i]) {
    int du = q_dis(x, nfa[i]);
    SEG::Insert(SEG::root[nfa[i]][0], 0, n, du, delt);
    SEG::Insert(SEG::root[i][1], 0, n, du, delt);
  }
}
int main() {
  n = read(), m = read();
  for (int i = 1; i <= n; i++) v[i] = read();
  for (int i = 2; i <= n; i++) {
    int u = read(), v = read();
    ins(u, v);
  }
  LCA::dfs1(1);
  LCA::dfs2(1, 1);
  f[0] = son = n;
  getroot(1, 0);
  work(root);
  while (m--) {
    int opt = read(), x = read() ^ lastans, y = read() ^ lastans;
    if (opt)
      update(x, y);
    else
      printf("%d\n", lastans = query(x, y));
  }
}
}  // namespace hh
void dfs(int x) {
  hsh[x] = ++tot, HSH[tot] = x;
  dep[x] = dep[f[x][0]] + 1;
  for (int i = 1; i <= 23; i++) f[x][i] = f[f[x][i - 1]][i - 1];
  for (int i = fst[x]; i; i = nxt[i]) dfs(to[i]);
}
int lca(int u, int v) {
  if (dep[u] < dep[v]) swap(u, v);
  int t = dep[u] - dep[v];
  for (int i = 23; i >= 0; i--)
    if ((1 << i) & t) u = f[u][i];
  if (u == v) return u;
  for (int i = 23; i >= 0; i--)
    if (f[u][i] != f[v][i]) u = f[u][i], v = f[v][i];
  return f[u][0];
}
void pushup(int x) {
  mx[x][0] = max(mx[(x << 1)][0], mx[((x << 1) | 1)][0]);
  mx[x][1] = max(min(mx[(x << 1)][0], mx[((x << 1) | 1)][0]),
                 max(mx[(x << 1)][1], mx[((x << 1) | 1)][1]));
  mn[x][0] = min(mn[(x << 1)][0], mn[((x << 1) | 1)][0]);
  mn[x][1] = min(max(mn[(x << 1)][0], mn[((x << 1) | 1)][0]),
                 min(mn[(x << 1)][1], mn[((x << 1) | 1)][1]));
}
void build(int x, int l, int r) {
  if (l == r) {
    mx[x][1] = 0;
    mn[x][1] = inf;
    mx[x][0] = mn[x][0] = hsh[l];
    return;
  }
  int mid = l + r >> 1;
  build((x << 1), l, mid);
  build(((x << 1) | 1), mid + 1, r);
  pushup(x);
}
void query(int x, int l, int r, int a, int b) {
  if (a <= l && r <= b) {
    if (mx[x][0] > mx1)
      mx2 = mx1, mx1 = mx[x][0];
    else if (mx[x][0] > mx2)
      mx2 = mx[x][0];
    if (mx[x][1] > mx2) mx2 = mx[x][1];
    if (mn[x][0] < mn1)
      mn2 = mn1, mn1 = mn[x][0];
    else if (mn[x][0] < mn2)
      mn2 = mn[x][0];
    if (mn[x][1] < mn2) mn2 = mn[x][1];
    return;
  }
  int mid = l + r >> 1;
  if (a <= mid) query((x << 1), l, mid, a, b);
  if (b > mid) query(((x << 1) | 1), mid + 1, r, a, b);
}
void init() {
  cin >> n >> q;
  for (int i = 2; i <= n; i++) {
    f[i][0] = read();
    to[++cnt] = i, nxt[cnt] = fst[f[i][0]], fst[f[i][0]] = cnt;
  }
}
void work() {
  dfs(1);
  build(1, 1, n);
}
int a, b;
void gogo() {
  mx1 = mx2 = 0;
  mn1 = mn2 = inf;
  query(1, 1, n, a, b);
}
void print() {
  while (q--) {
    int l1, l2;
    cin >> a >> b;
    gogo();
    l1 = lca(HSH[mx1], HSH[mn2]);
    l2 = lca(HSH[mx2], HSH[mn1]);
    if (dep[l1] > dep[l2])
      printf("%d %d\n", HSH[mn1], dep[l1] - 1);
    else
      printf("%d %d\n", HSH[mx1], dep[l2] - 1);
  }
}
int main() {
  init();
  work();
  print();
}
