There is a tree with N vertices, numbered 1 through N. The i-th of the N-1 edges connects vertices a_i and b_i.

Currently, there are A_i stones placed on vertex i. Takahashi and Aoki will play a game using this tree.

First, Takahashi will select a vertex and place a piece on it. Then, starting from Takahashi, they will alternately perform the following operation:

* Remove one stone from the vertex currently occupied by the piece.
* Then, move the piece to a vertex that is adjacent to the currently occupied vertex.



The player who is left with no stone on the vertex occupied by the piece and thus cannot perform the operation, loses the game. Find all the vertices v such that Takahashi can place the piece on v at the beginning and win the game.

Constraints

* 2 ≦ N ≦ 3000
* 1 ≦ a_i,b_i ≦ N
* 0 ≦ A_i ≦ 10^9
* The given graph is a tree.

Input

The input is given from Standard Input in the following format:


N
A_1 A_2 … A_N
a_1 b_1
:
a_{N-1} b_{N-1}


Output

Print the indices of the vertices v such that Takahashi can place the piece on v at the beginning and win the game, in a line, in ascending order.

Examples

Input

3
1 2 3
1 2
2 3


Output

2


Input

5
5 4 1 2 3
1 2
1 3
2 4
2 5


Output

1 2


Input

3
1 1 1
1 2
2 3


Output
#include <bits/stdc++.h>
using namespace std;
int n,m,head[10001],f[10001],x,y,kl,a[10001];
struct line{int next,to;}q[1000001];
void pushline(int x,int y)
{
	q[++kl].next=head[x];head[x]=kl;q[kl].to=y;
}
inline void dfs(int x,int fa)
{
    f[x]=0;
    for (int p=head[x];int v=q[p].to;p=q[p].next) 
	{
        if(v==fa||a[v]>=a[x])continue;
        dfs(v,x);
		if (!f[v])f[x]=1;
    }
}
signed main() 
{
	cin>>n;
	for(int i=1;i<=n;i++)cin>>a[i];
	for(int i=1;i<n;i++)
	{
		cin>>x>>y;
		pushline(x,y);pushline(y,x);
	}
	for(int i=1;i<=n;i++)
	{
		dfs(i,0);
		if(f[i])cout<<i<<" "; 
	}
	
}
/*
直接考虑一条边，假装当前点的石头少，如果我推过去的话就亏大发了，因为对手可以推回来，然后死循环
最后直接没了
因此可以给边定向，拉向小的位置。 
这样直接成个DAG了，拓排之后倒着扫可以直接做完。 
如果有相等 怎么办 
删掉边。然后统一按照必败点处理 
考虑DAG上一个终止节点，它应该是必胜的 
*/