#ifdef __APPLE__
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cctype>
#include <stack>
#include <list>
#include <queue>
#include <map>
#include <sstream>
#include <cmath>
#include <limits>
#include <vector>
#include <algorithm>
#include <iomanip>
#include <bitset>
#include <utility>
#include <set>
#include <numeric>
#else
#include<bits/stdc++.h>
#endif
using namespace std;
typedef vector<int> vi;
typedef pair<int,int> ii;
typedef vector<ii> vii;
typedef vector<vi> vvi;
#define lli long long int
#define ulli unsigned long long int
#define PB push_back
#define MP make_pair
#define F first
#define S second
#define ALL(a) a.begin(),a.end()
#define SZ(a) (int)(a.size())
#define loop(i,a,b) for(int i=a; i<b; i++)
int gcd(int a, int b) {return b==0?a:gcd(b,a%b);}
int lcm(int a, int b) {return a*(b/gcd(a,b));}
#define INF 1000000000 //(10^9)
#define MOD 1000000007 //(10^9+7)
//FILE *fin = freopen("in","r",stdin);
//FILE *fout = freopen("out","w",stdout);
int n, q, maxi=-1, t=0;
vi tree[100010], num(100010), arr[100010], maintain(100010);
vi visited(100010,-1), arrival(100010), vertex(100010);
struct SegmentTreeNode{
int val;
void assignLeaf(int value)
{
val= value;
}
void merge(SegmentTreeNode& left, SegmentTreeNode& right)
{
val= max(left.val,right.val);
}
int getValue()
{
return val;
}
};
SegmentTreeNode nodes[400010];
class SegmentTree{
public:
void build()
{
buildTree(1,0,maxi);
}
int getValue(int lo, int hi)
{
SegmentTreeNode result = getValue(1, 0, maxi, lo, hi);
return result.getValue();
}
void update(int index, int value)
{
update(1, 0, maxi, index, value);
}
private:
void buildTree(int stIndex, int lo, int hi)
{
if (lo == hi)
{
nodes[stIndex].assignLeaf(-1);
return;
}
int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
buildTree(left, lo, mid);
buildTree(right, mid + 1, hi);
nodes[stIndex].merge(nodes[left], nodes[right]);
}
SegmentTreeNode getValue(int stIndex, int left, int right, int lo, int hi)
{
if (left == lo && right == hi)
return nodes[stIndex];
int mid = (left + right) / 2;
if (lo > mid)
return getValue(2*stIndex+1, mid+1, right, lo, hi);
if (hi <= mid)
return getValue(2*stIndex, left, mid, lo, hi);
SegmentTreeNode leftResult = getValue(2*stIndex, left, mid, lo, mid);
SegmentTreeNode rightResult = getValue(2*stIndex+1, mid+1, right, mid+1, hi);
SegmentTreeNode result;
result.merge(leftResult, rightResult);
return result;
}
void update(int stIndex, int lo, int hi, int index, int value)
{
if (lo == hi)
{
nodes[stIndex].assignLeaf(value);
return;
}
int left = 2 * stIndex, right = left + 1, mid = (lo + hi) / 2;
if (index <= mid)
update(left, lo, mid, index, value);
else
update(right, mid+1, hi, index, value);
nodes[stIndex].merge(nodes[left], nodes[right]);
}
};
SegmentTree st;
void dfs(int v)
{
int flag, flag1;
visited[v]= 1;
arrival[v]= t++;
arr[num[v]].PB(arrival[v]);
flag= num[v]-num[0];
maintain[v]= st.getValue(flag,maxi);
st.update(num[v],arrival[v]);
loop(i,0,SZ(tree[v]))
{
if(visited[tree[v][i]]==-1)
dfs(tree[v][i]);
}
arr[num[v]].pop_back();
st.update(num[v],arr[num[v]].back());
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);
cin>> n>> q;
loop(i,0,n)
{
cin>> num[i];
maxi= max(maxi,num[i]);
}
loop(i,0,n-1)
{
int x, y;
cin>> x>> y;
tree[x].PB(y);
tree[y].PB(x);
}
loop(i,0,maxi+1)
arr[i].PB(-1);
st.build();
dfs(0);
loop(i,0,n)
vertex[arrival[i]]= i;
loop(i,0,q)
{
int node;
cin>> node;
if(maintain[node]==-1)
cout<< "-1\n";
else
cout<< vertex[maintain[node]]<< " "<< num[vertex[maintain[node]]]<< "\n";
}
return 0;
}
I2lmZGVmIF9fQVBQTEVfXwojaW5jbHVkZSA8aW9zdHJlYW0+CiNpbmNsdWRlIDxjc3RyaW5nPgojaW5jbHVkZSA8c3RyaW5nPgojaW5jbHVkZSA8Y3N0ZGlvPgojaW5jbHVkZSA8Y2N0eXBlPgojaW5jbHVkZSA8c3RhY2s+CiNpbmNsdWRlIDxsaXN0PgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxtYXA+CiNpbmNsdWRlIDxzc3RyZWFtPgojaW5jbHVkZSA8Y21hdGg+CiNpbmNsdWRlIDxsaW1pdHM+CiNpbmNsdWRlIDx2ZWN0b3I+CiNpbmNsdWRlIDxhbGdvcml0aG0+CiNpbmNsdWRlIDxpb21hbmlwPgojaW5jbHVkZSA8Yml0c2V0PgojaW5jbHVkZSA8dXRpbGl0eT4KI2luY2x1ZGUgPHNldD4KI2luY2x1ZGUgPG51bWVyaWM+CiNlbHNlCiNpbmNsdWRlPGJpdHMvc3RkYysrLmg+CiNlbmRpZgoKdXNpbmcgbmFtZXNwYWNlIHN0ZDsKCnR5cGVkZWYgdmVjdG9yPGludD4gdmk7CnR5cGVkZWYgcGFpcjxpbnQsaW50PiBpaTsKdHlwZWRlZiB2ZWN0b3I8aWk+IHZpaTsKdHlwZWRlZiB2ZWN0b3I8dmk+IHZ2aTsKCiNkZWZpbmUgbGxpIGxvbmcgbG9uZyBpbnQKI2RlZmluZSB1bGxpIHVuc2lnbmVkIGxvbmcgbG9uZyBpbnQKCiNkZWZpbmUgUEIgcHVzaF9iYWNrCiNkZWZpbmUgTVAgbWFrZV9wYWlyCiNkZWZpbmUgRiBmaXJzdAojZGVmaW5lIFMgc2Vjb25kCiNkZWZpbmUgQUxMKGEpIGEuYmVnaW4oKSxhLmVuZCgpCiNkZWZpbmUgU1ooYSkgKGludCkoYS5zaXplKCkpCgojZGVmaW5lIGxvb3AoaSxhLGIpIGZvcihpbnQgaT1hOyBpPGI7IGkrKykKCmludCBnY2QoaW50IGEsIGludCBiKSB7cmV0dXJuIGI9PTA/YTpnY2QoYixhJWIpO30KaW50IGxjbShpbnQgYSwgaW50IGIpIHtyZXR1cm4gYSooYi9nY2QoYSxiKSk7fQoKI2RlZmluZSBJTkYgMTAwMDAwMDAwMCAgLy8oMTBeOSkKI2RlZmluZSBNT0QgMTAwMDAwMDAwNyAgLy8oMTBeOSs3KQoKLy9GSUxFICpmaW4gPSBmcmVvcGVuKCJpbiIsInIiLHN0ZGluKTsKLy9GSUxFICpmb3V0ID0gZnJlb3Blbigib3V0IiwidyIsc3Rkb3V0KTsKCmludCBuLCBxLCBtYXhpPS0xLCB0PTA7CnZpIHRyZWVbMTAwMDEwXSwgbnVtKDEwMDAxMCksIGFyclsxMDAwMTBdLCBtYWludGFpbigxMDAwMTApOwp2aSB2aXNpdGVkKDEwMDAxMCwtMSksIGFycml2YWwoMTAwMDEwKSwgdmVydGV4KDEwMDAxMCk7CgpzdHJ1Y3QgU2VnbWVudFRyZWVOb2RlewoKCWludCB2YWw7CgoJdm9pZCBhc3NpZ25MZWFmKGludCB2YWx1ZSkKCXsKCQl2YWw9IHZhbHVlOwoJfQoKCXZvaWQgbWVyZ2UoU2VnbWVudFRyZWVOb2RlJiBsZWZ0LCBTZWdtZW50VHJlZU5vZGUmIHJpZ2h0KQoJewoJCXZhbD0gbWF4KGxlZnQudmFsLHJpZ2h0LnZhbCk7Cgl9CgoJaW50IGdldFZhbHVlKCkKCXsKCQlyZXR1cm4gdmFsOwoJfQp9OwoKU2VnbWVudFRyZWVOb2RlIG5vZGVzWzQwMDAxMF07CgpjbGFzcyBTZWdtZW50VHJlZXsKCglwdWJsaWM6CgoJdm9pZCBidWlsZCgpCgl7CgkJYnVpbGRUcmVlKDEsMCxtYXhpKTsKCX0KCglpbnQgZ2V0VmFsdWUoaW50IGxvLCBpbnQgaGkpCgl7CgkJU2VnbWVudFRyZWVOb2RlIHJlc3VsdCA9IGdldFZhbHVlKDEsIDAsIG1heGksIGxvLCBoaSk7CgkJcmV0dXJuIHJlc3VsdC5nZXRWYWx1ZSgpOwoJfQoKCXZvaWQgdXBkYXRlKGludCBpbmRleCwgaW50IHZhbHVlKQoJewoJCXVwZGF0ZSgxLCAwLCBtYXhpLCBpbmRleCwgdmFsdWUpOwoJfQoKCXByaXZhdGU6CgoJdm9pZCBidWlsZFRyZWUoaW50IHN0SW5kZXgsIGludCBsbywgaW50IGhpKQoJewoJCWlmIChsbyA9PSBoaSkKCQl7CgkJCW5vZGVzW3N0SW5kZXhdLmFzc2lnbkxlYWYoLTEpOwoJCQlyZXR1cm47CgkJfQoKCQlpbnQgbGVmdCA9IDIgKiBzdEluZGV4LCByaWdodCA9IGxlZnQgKyAxLCBtaWQgPSAobG8gKyBoaSkgLyAyOwoJCWJ1aWxkVHJlZShsZWZ0LCBsbywgbWlkKTsKCQlidWlsZFRyZWUocmlnaHQsIG1pZCArIDEsIGhpKTsKCQlub2Rlc1tzdEluZGV4XS5tZXJnZShub2Rlc1tsZWZ0XSwgbm9kZXNbcmlnaHRdKTsKCX0KCglTZWdtZW50VHJlZU5vZGUgZ2V0VmFsdWUoaW50IHN0SW5kZXgsIGludCBsZWZ0LCBpbnQgcmlnaHQsIGludCBsbywgaW50IGhpKQoJewoJCWlmIChsZWZ0ID09IGxvICYmIHJpZ2h0ID09IGhpKQoJCQlyZXR1cm4gbm9kZXNbc3RJbmRleF07CgoJCWludCBtaWQgPSAobGVmdCArIHJpZ2h0KSAvIDI7CgkJaWYgKGxvID4gbWlkKQoJCQlyZXR1cm4gZ2V0VmFsdWUoMipzdEluZGV4KzEsIG1pZCsxLCByaWdodCwgbG8sIGhpKTsKCQlpZiAoaGkgPD0gbWlkKQoJCQlyZXR1cm4gZ2V0VmFsdWUoMipzdEluZGV4LCBsZWZ0LCBtaWQsIGxvLCBoaSk7CgoJCVNlZ21lbnRUcmVlTm9kZSBsZWZ0UmVzdWx0ID0gZ2V0VmFsdWUoMipzdEluZGV4LCBsZWZ0LCBtaWQsIGxvLCBtaWQpOwoJCVNlZ21lbnRUcmVlTm9kZSByaWdodFJlc3VsdCA9IGdldFZhbHVlKDIqc3RJbmRleCsxLCBtaWQrMSwgcmlnaHQsIG1pZCsxLCBoaSk7CgkJU2VnbWVudFRyZWVOb2RlIHJlc3VsdDsKCQlyZXN1bHQubWVyZ2UobGVmdFJlc3VsdCwgcmlnaHRSZXN1bHQpOwoJCXJldHVybiByZXN1bHQ7Cgl9CgoJdm9pZCB1cGRhdGUoaW50IHN0SW5kZXgsIGludCBsbywgaW50IGhpLCBpbnQgaW5kZXgsIGludCB2YWx1ZSkKCXsKCQlpZiAobG8gPT0gaGkpCgkJewoJCQlub2Rlc1tzdEluZGV4XS5hc3NpZ25MZWFmKHZhbHVlKTsKCQkJcmV0dXJuOwoJCX0KCgkJaW50IGxlZnQgPSAyICogc3RJbmRleCwgcmlnaHQgPSBsZWZ0ICsgMSwgbWlkID0gKGxvICsgaGkpIC8gMjsKCQlpZiAoaW5kZXggPD0gbWlkKQoJCQl1cGRhdGUobGVmdCwgbG8sIG1pZCwgaW5kZXgsIHZhbHVlKTsKCQllbHNlCgkJCXVwZGF0ZShyaWdodCwgbWlkKzEsIGhpLCBpbmRleCwgdmFsdWUpOwoKCQlub2Rlc1tzdEluZGV4XS5tZXJnZShub2Rlc1tsZWZ0XSwgbm9kZXNbcmlnaHRdKTsKCX0KfTsKClNlZ21lbnRUcmVlIHN0OwoKdm9pZCBkZnMoaW50IHYpCnsKCWludCBmbGFnLCBmbGFnMTsKCXZpc2l0ZWRbdl09IDE7CglhcnJpdmFsW3ZdPSB0Kys7CglhcnJbbnVtW3ZdXS5QQihhcnJpdmFsW3ZdKTsKCWZsYWc9IG51bVt2XS1udW1bMF07CgltYWludGFpblt2XT0gc3QuZ2V0VmFsdWUoZmxhZyxtYXhpKTsKCXN0LnVwZGF0ZShudW1bdl0sYXJyaXZhbFt2XSk7Cglsb29wKGksMCxTWih0cmVlW3ZdKSkKCXsKCQlpZih2aXNpdGVkW3RyZWVbdl1baV1dPT0tMSkKCQkJZGZzKHRyZWVbdl1baV0pOwoJfQoJYXJyW251bVt2XV0ucG9wX2JhY2soKTsKCXN0LnVwZGF0ZShudW1bdl0sYXJyW251bVt2XV0uYmFjaygpKTsKfQoKaW50IG1haW4oKQp7Cglpb3M6OnN5bmNfd2l0aF9zdGRpbyhmYWxzZSk7CgljaW4udGllKE5VTEwpOwoKCWNpbj4+IG4+PiBxOwoJbG9vcChpLDAsbikKCXsKCQljaW4+PiBudW1baV07CgkJbWF4aT0gbWF4KG1heGksbnVtW2ldKTsKCX0KCWxvb3AoaSwwLG4tMSkKCXsKCQlpbnQgeCwgeTsKCQljaW4+PiB4Pj4geTsKCQl0cmVlW3hdLlBCKHkpOwoJCXRyZWVbeV0uUEIoeCk7Cgl9Cglsb29wKGksMCxtYXhpKzEpCgkJYXJyW2ldLlBCKC0xKTsKCglzdC5idWlsZCgpOwoJZGZzKDApOwoKCWxvb3AoaSwwLG4pCgkJdmVydGV4W2Fycml2YWxbaV1dPSBpOwoJbG9vcChpLDAscSkKCXsKCQlpbnQgbm9kZTsKCQljaW4+PiBub2RlOwoJCWlmKG1haW50YWluW25vZGVdPT0tMSkKCQkJY291dDw8ICItMVxuIjsKCQllbHNlCgkJCWNvdXQ8PCB2ZXJ0ZXhbbWFpbnRhaW5bbm9kZV1dPDwgIiAiPDwgbnVtW3ZlcnRleFttYWludGFpbltub2RlXV1dPDwgIlxuIjsKCX0KCgoJcmV0dXJuIDA7Cn0=