Escalators

Binary Casino is a special skyscraper with N floors connected by a tricky network of high speed escalators.

The floor connections are designed so that if an escalator goes from floor A to floor B, another escalator goes from floor B to floor A. Also, for any two floors A and B, there is exactly one way to go from A to B.

The manager decided to run a promotion game to attract more customers. The game has the following rules:

• The game is played in one or more rounds.
• In each round a customer can choose a floor S on which that round starts. At this moment he earns a fixed number of tokens t(S) associated with floor S. Then he may move to other floors using escalators.
• If a customer decides to take an escalator from floor A to floor B and has X tokens, he has to pay X − (X AND t(B)) tokens to enter floor B, where "AND" is the bitwise AND operator, "−" is the standard subtraction operator on numbers, and t(B) is the number of tokens associated with floor B.
• A customer can stop the round on any floor (including S) and keep the tokens from that round. Then he can start a new round from any floor if it is possible.
• No two rounds may have the same pair of starting and ending floors, not even in the opposite direction, that is, when the starting and ending floors are exchanged.

The manager is curious about the maximum number of tokens a customer can earn in the game.

The first line of input contains an integer N (1 ≤ N ≤ 3 · 10^5), the number of floors in the casino skyscraper. The second line contains N integers Vi (0 ≤ Vi < 2^20). The i-th integer Vi is the number of tokens a customer earns on the i-th floor. After that, N − 1 lines follow. Each line contains two integers A and B (0 ≤ A, B < N), an escalator connection between floors A and B.

Output a single number: the maximum number of tokens a customer can earn.