One day, monkey A learned about one of the bit-operations, xor. He was keen of this interesting operation and wanted to practise it at once.

Monkey A gave a value to each node on the tree. And he was curious about a problem.

The problem is how large the xor result of number x and one node value of label y can be, when giving you a non-negative integer x and a node label u indicates that node y is in the subtree whose root is u(y can be equal to u).

Can you help him?

For each test case there are two positive integers n and q, indicate that the tree has n nodes and you need to answer q queries.

Then two lines follow.

The first line contains n non-negative integers V1,V2,⋯,Vn, indicating the value of node i.

The second line contains n-1 non-negative integers F1,F2,⋯Fn−1, Fi means the father of node i+1.

And then q lines follow.

In the i-th line, there are two integers u and x, indicating that the node you pick should be in the subtree of u, and x has been described in the problem.

2≤n,q≤105

0≤Vi≤109

1≤Fi≤n, the root of the tree is node 1.

1≤u≤n,0≤x≤109

#include <stdio.h>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cstring>

#include <bitset>

#include <string>

#include <stack>

#include <cmath>

#include <queue>

#include <set>

#include <climits>

#include <map>

using namespace std;

#define INF 0x3f3f3f3f

#define LC(x) (x<<1)

#define RC(x) ((x<<1)+1)

#define MID(x,y) ((x+y)>>1)

#define fin(name) freopen(name,"r",stdin)

#define fout(name) freopen(name,"w",stdout)

#define CLR(arr,val) memset(arr,val,sizeof(arr))

#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);

typedef pair<int, int> pii;

typedef long long LL;

const double PI = acos(-1.0);

const int N = 100010;

struct edge

{

    int to, nxt;

    edge() {}

    edge(int _to, int _nxt): to(_to), nxt(_nxt) {}

} E[N];

struct Trie

{

    int nxt[2];

    int cnt;

    void init()

    {

        nxt[0] = nxt[1] = 0;

        cnt = 0;

    }

} L[N * 31];

int tot, root[N];

int head[N], etot;

int ll[N], rr[N], idx;

int arr[N];

void init()

{

    L[0].init();

    tot = 0;

    CLR(head, -1);

    etot = 0;

    idx = 0;

}

inline void add(int s, int t)

{

    E[etot] = edge(t, head[s]);

    head[s] = etot++;

}

void update(int &cur, int ori, int step, LL n, int v)

{

    cur = ++tot;

    L[cur] = L[ori];

    L[cur].cnt += v;

    if (step < 0)

        return ;

    int t = (n >> step) & 1;

    update(L[cur].nxt[t], L[ori].nxt[t], step - 1, n, v);

}

int Find(int S, int E, int step, LL n)

{

    if (step < 0)

        return 0;

    int t = (n >> step) & 1;

    if (L[L[E].nxt[t ^ 1]].cnt - L[L[S].nxt[t ^ 1]].cnt > 0)

        return (1LL << step) + Find(L[S].nxt[t ^ 1], L[E].nxt[t ^ 1], step - 1, n);

    else

        return Find(L[S].nxt[t], L[E].nxt[t], step - 1, n);

}

void dfs_build(int u)

{

    ll[u] = ++idx;

    update(root[ll[u]], root[ll[u] - 1], 29, arr[u], 1);

    for (int i = head[u]; ~i; i = E[i].nxt)

    {

        int v = E[i].to;

        dfs_build(v);

    }

    rr[u] = idx;

}

int main(void)

{

    int n, q, i;

    while (~scanf("%d%d", &n, &q))

    {

        init();

        for (i = 1; i <= n; ++i)

            scanf("%d", &arr[i]);

        for (i = 2; i <= n; ++i)

        {

            int f;

            scanf("%d", &f);

            add(f, i);

        }

        dfs_build(1);

        while (q--)

        {

            int u, x;

            scanf("%d%d", &u, &x);

            int l = ll[u], r = rr[u];

            printf("%d\n", Find(root[l - 1], root[r], 29, x));

        }

    }

    return 0;

}