给定一棵N个节点的树，每个点有一个权值，对于M个询问(u,v,k)，你需要回答u xor lastans和v这两个节点间第K小的点权。其中lastans是上一个询问的答案，初始为0，即第一个询问的u是明文。

第一行两个整数N,M。

第二行有N个整数，其中第i个整数表示点i的权值。

后面N-1行每行两个整数(x,y)，表示点x到点y有一条边。

最后M行每行两个整数(u,v,k)，表示一组询问。

M行，表示每个询问的答案。

N,M<=100000

暴力自重。。。

#include<map>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

#define N 100010

#define buf 1<<21

using namespace std;

char B[buf],*p=B;

inline int Rin(){

    int x=,f=;

    for(;*p<''||*p>'';p++)

        if(*p=='-')f=-;

    for(;*p>=''&&*p<='';p++)

        x=(x<<)+(x<<)+*p-'';

    return x*f;

}

bool vis[N];

vector<int>d;

map<int,int>h;

int ind,n,q,ans,val[N],sz[N],rk[N],id[N],mx[N],fa[N],dep[N],top[N];

struct pt{

    int v;pt *nt;

}*fst[N],mem[N<<],*e=mem;

inline void link(int x,int y){

    *++e=(pt){y,fst[x]},fst[x]=e;

    *++e=(pt){x,fst[y]},fst[y]=e;

}

void dfs1(int x){

    rk[++ind]=x,

    id[x]=ind,

    vis[x]=sz[x]=;

    for(pt *j=fst[x];j;j=j->nt)

        if(!vis[j->v])

            fa[j->v]=x,

            dep[j->v]=dep[x]+,

            dfs1(j->v),sz[x]+=sz[j->v],

            mx[x]=sz[mx[x]]<sz[j->v]?j->v:mx[x];

}

void dfs2(int x){

    vis[x]=;

    top[x]=x^mx[fa[x]]?x:top[fa[x]];

    if(mx[x]){

        dfs2(mx[x]);

        for(pt *j=fst[x];j;j=j->nt)

            if(vis[j->v])dfs2(j->v);

    }

}

inline int lca(int x,int y){

    while(top[x]^top[y])

        dep[top[x]]>dep[top[y]]?

        x=fa[top[x]]:

        y=fa[top[y]];

    return dep[x]<dep[y]?x:y;

}

struct Seg{

    Seg *l,*r;int s;

    Seg(){}

    Seg(Seg *_l,Seg *_r,int _s)

    :l(_l),r(_r),s(_s){}

}*rt[N],*nil=new Seg(0x0,0x0,);

Seg *build(Seg *p,int s,int t,int k){

    if(!(s^t))return new Seg(rt[],rt[],p->s+);

    int mid=s+t>>;

    return k<=mid?

           new Seg(build(p->l,s,mid,k),p->r,p->s+):

           new Seg(p->l,build(p->r,mid+,t,k),p->s+);

}

int secret(Seg *p1,Seg *p2,Seg *p3,Seg *p4,int s,int t,int k){

    while(s<t){

        int mid=s+t>>;

        int c=p1->l->s+p2->l->s-p3->l->s-p4->l->s;

        if(k<=c)

            t=mid,

            p1=p1->l,

            p2=p2->l,

            p3=p3->l,

            p4=p4->l;

        else

            k-=c,

            s=mid+,

            p1=p1->r,

            p2=p2->r,

            p3=p3->r,

            p4=p4->r;

    }

    return d[s-];

}

inline int feel(int x,int y,int k){

    int t=lca(x,y);

    return secret(rt[id[x]],rt[id[y]],rt[id[t]],rt[id[fa[t]]],,d.size(),k);

}

int main(){

    fread(B,,buf,stdin);

    n=Rin(),q=Rin();

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

        val[i]=Rin(),d.push_back(val[i]);

    sort(d.begin(),d.end());

    d.erase(unique(d.begin(),d.end()),d.end());

    for(int i=;i<d.size();i++)

        h[d[i]]=i+;

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

        val[i]=h[val[i]];

    for(int i=;i<n;i++){

        int x=Rin(),y=Rin();

        link(x,y);

    }

    dfs1();dfs2();

    rt[]=nil;

    rt[]->l=rt[]->r=rt[];

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

        rt[i]=build(rt[id[fa[rk[i]]]],,d.size(),val[rk[i]]);

    while(q--){

        int x=Rin(),y=Rin(),k=Rin();

        printf("%d\n",ans=feel(x^ans,y,k));

    }

    return ;

}

#include<map>

#include<vector>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<iostream>

#include<algorithm>

using namespace std;

const int N=;

inline int Rin(){

    int x=,c=getchar(),f=;

    for(;c<||c>;c=getchar())

        if(!(c^))

            f=-;

    for(;c>&&c<;c=getchar())

        x=(x<<)+(x<<)+c-;

    return x*f;

}

bool vis[N];

pair<int,int>v[N];

int n,m,ecnt,ans,fst[N],q[N],a[N*],dep[N],fa[N][],bin[],rt[N],tot,sum[N*],ls[N*],rs[N*];

void build(int &pr,int pl,int s,int t,int k){

    pr=++tot;

    sum[pr]=sum[pl]+;

    if(!(s^t))return;

    ls[pr]=ls[pl];

    rs[pr]=rs[pl];

    int mid=s+t>>;

    if(k<=mid)build(ls[pr],ls[pl],s,mid,k);

    else build(rs[pr],rs[pl],mid+,t,k);

}

struct edge{

    int v,nxt;

}e[N<<];

inline void link(int x,int y){

    e[++ecnt].v=y;

    e[ecnt].nxt=fst[x];

    fst[x]=ecnt;

}

void bfs(){

    int hd=,tl=;

    vis[]=;q[]=;

    while(hd^tl){

        int now=q[hd++];

        build(rt[now],rt[fa[now][]],,n,a[now]);

        for(int j=;j<=;j++)

            if(bin[j]<=dep[now])

                fa[now][j]=fa[fa[now][j-]][j-];

            else

                break;

        for(int j=fst[now];j;j=e[j].nxt)

            if(!vis[e[j].v])

                vis[e[j].v]=,

                fa[e[j].v][]=now,

                dep[e[j].v]=dep[now]+,

                q[tl++]=e[j].v;

    }

}

int lca(int x,int y){

    if(dep[x]<dep[y])swap(x,y);

    for(int j=;~j;j--)

        if(dep[fa[x][j]]>=dep[y])

            x=fa[x][j];

    if(!(x^y))return x;

    for(int j=;~j;j--)

        if(fa[x][j]^fa[y][j])

            x=fa[x][j],y=fa[y][j];

    return fa[x][];

}

int query(int p1,int p2,int p3,int p4,int s,int t,int k){

    if(!(s^t))return v[t].first;

    int mid=s+t>>,c=sum[ls[p1]]+sum[ls[p2]]-sum[ls[p3]]-sum[ls[p4]];

    if(k<=c)return query(ls[p1],ls[p2],ls[p3],ls[p4],s,mid,k);

    return query(rs[p1],rs[p2],rs[p3],rs[p4],mid+,t,k-c);

}

int req(int x,int y,int k){

    int t=lca(x,y);

    return query(rt[x],rt[y],rt[t],rt[fa[t][]],,n,k);

}

int main(){

    for(int i=;i<=;i++)

        bin[i]=<<i;

    n=Rin(),m=Rin();

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

        v[i].first=Rin(),v[i].second=i;

    sort(v+,v++n);

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

        a[v[i].second]=i;

    for(int i=;i<n;i++){

        int x=Rin(),y=Rin();

        link(x,y);link(y,x);

    }

    dep[]=;bfs();

    for(int i=;i<=m;i++)

    {

        int x,y,k;

        scanf("%d%d%d",&x,&y,&k);

        printf("%d",ans=req(x^ans,y,k));

        if(i!=m)puts("");

    }

    return ;

}