[Due to SPOJ restrictions, this problem has been modified with respect to the original version used in the Argentinian Programming Tournament of 2016 in order to have multiple test cases per input file. The original version of this problem (in Spanish) can be found at http://torneoprogramacion.com.ar/wp-content/uploads/2016/09/tap2016.pdf ]

Mabel Eucalyptus spent last night training in the art of eucalyptus leaf eating. She is finally ready to face her evil arch-nemesis, Peaceful, in a last game which will decide once and for all which of them is the best koala.

The game will take place in a forest containing N eucalyptus trees numbered from 1 to N. The trees are connected by N-1 ropes, each of which joins two different trees. These ropes allow koalas to move from one tree to the other, and the eucalyptus forest is such that it is possible to go from a given tree to any other successively using the ropes.

The eucalyptus trees contain a non-negative amount of leaves. When a tree contains no leaves, we say it is empty. Initially, none of the N trees in the forest is empty.

Before commencing the game, each koala is assigned a different tree. At the beginning of the game, each player climbs the tree that was assigned to her and eats all the leaves it contains. After that both players take turns, Mabel being in charge of making the first move. In each turn, the corresponding player moves to a non-empty tree connected by a rope to the tree she is currently in. Then, she eats all the leaves this tree contains, thus leaving it empty. If a player can't make a valid move in her turn, she forfeits her turn staying wherever she is, and the other player gets to move again. The game ends when both players cannot make a valid move.

Once the game has finished, the number of leaves eaten by each koala is counted, and the difference between the amount eaten by Mabel and the amount eaten by Peaceful is calculated. Mabel will play aiming to maximize this difference, whereas Peaceful will play to minimize it. Your task is to determine what the result of the game will be, assuming that both koalas play optimally.

Input

There are multiple test cases in the input file. For each test case, the first line contains three integer numbers N, M y P, representing the number of trees in the forest, the tree where Mabel starts, and the tree where Peaceful starts, respectively (2 ≤ N ≤ 10⁵ and 1 ≤ M, P ≤ N with M ≠ P). The second line contains N integer numbers C₁, C₂, ..., C_N, representing C_i the number of leaves contained in the i-th tree (1 ≤ C_i ≤ 100 for i = 1, 2, ..., N). Each of the following N-1 lines contains two integer numbers U and V, representing that there is a rope connecting trees number U and V (1 ≤ U, V ≤ N with U ≠ V).

Output

For each test case, output a single line containing an integer number, representing the difference between the number of leaves eaten by Mabel and the number of leaves eaten by Peaceful if both of them play optimally.

Example

Input:
2 1 2
5 3
1 2
6 2 3
1 6 4 3 2 2
1 2
2 3
3 4
3 5
5 6
Output:
2
-1