As everyone knows, Bajtazar is a very busy man who is not afraid to take on any life challenges that await him in Bitocja. Eventually, however, he decided to take a break and went on vacation to Bitocja. In Bitocja, there are $n$ cities connected by $n - 1$ bidirectional roads, which allow travel between any pair of cities. Bajtazar does not want to stay in the same city for two days in a row, but he also does not like long journeys, so every evening he plans to travel along one road (to an adjacent city). For each city, Bajtazar has determined an attractiveness coefficient, which defines how pleasant it will be for him to visit that city. Naturally, he would like to have the most pleasant vacation possible.

Bajtazar would not be himself if he did not combine business with pleasure. He will use his vacation time to start writing his diaries. Specifically, he will go sightseeing only every other day of his vacation, and he will spend the remaining days writing.

He would like to plan a vacation of length $2k - 1$ days, in which he will go sightseeing on $k$ odd-numbered days, and he will write diaries on $k - 1$ even-numbered days. The sum of the attractiveness coefficients of the visited cities must be as large as possible, and Bajtazar does not want to visit the same city more than once. However, it does not bother him if, on the days he writes his diaries, he is in a city he has already visited before. Help him plan the most pleasant vacation possible.

Input

The first line of the input contains a single integer $n$ ($1 \le n \le 1\,000\,000$), representing the number of cities in Bitocja. The cities are numbered from $1$ to $n$.

The second line contains a sequence of $n$ integers $w_1, w_2, \dots, w_n$ ($1 \le w_i \le 1\,000\,000$), separated by single spaces; the number $w_i$ denotes the attractiveness coefficient of city $i$.

The next $n - 1$ lines contain the description of the roads in Bitocja; the $i$-th of these lines contains two integers $a_i$ and $b_i$ ($1 \le a_i, b_i \le n$), separated by a single space, indicating that there is a bidirectional road connecting cities $a_i$ and $b_i$.

Output

Your program should output three lines. The first line should contain an integer $W$ representing the maximum sum of attractiveness coefficients that can be obtained for Bajtazar's vacation.

The second line should contain an integer $k$ representing the number of cities that Bajtazar will visit during such a vacation. The third line should contain a sequence of $2k - 1$ integers separated by single spaces, representing the cities where Bajtazar will be staying on consecutive days of his vacation. If there is more than one solution with the maximum $W$, your program may output any of them.

Examples

Input 1

8
3 8 5 4 1 2 1 1
1 2
2 3
2 4
5 4
4 6
7 6
8 7

Output 1

13
4
3 2 1 2 4 6 7

Note 1

The explanation of the example: The figure shows the road network of Bitocja. Bajtazar will visit cities numbered 3, 1, 4, and 7; the sum of the attractiveness coefficients of these cities is $5 + 3 + 4 + 1 = 13$.

Subtasks

The test set is divided into the following subtasks. Tests for each subtask consist of one or more separate test groups.

If your program correctly outputs the first line of the output (the number $W$), and the remaining lines are incorrect, it will receive 40% of the points assigned to the test.