XOR

Verilmiş bir ağacda, hər bir $i$-ci zirvənin $a_i$ dəyəri var. İki zirvə arasındakı məsafə, həmin zirvələr arasındakı yolda olan bütün zirvələrin $xor$ əməliyyatının nəticəsidir. $1\le u\le v\le n$ şərtini ödəyən bütün $u$ və $v$ zirvələri arasındakı məsafələrin cəmini hesablayın.

Giriş formatı

Birinci sətirdə bir tam ədəd $n(1\le n\le 10^5)$ — zirvələrin sayını göstərir.İkinci sətirdə $n$ tam ədəd $a_1$, $a_2$, ..., $a_n$ ($0\le a_i\le 10^6$) verilmişdir.Sonrakı $n-1$ sətirin hər biri iki tam ədəd $u_i$ və $v_i$ (1 ≤ $u_i$, $v_i$ ≤ n) ehtiva edir.

Çıxış formatı

Problemin cavabını çıxarın.

Qeyd

Birinci nümunədə həll belədir:

• 1-dən 1-ə məsafə 1,

• 1-dən 2-yə məsafə 3,

• 1-dən 3-ə məsafə 0,

• 2-dən 2-yə məsafə 2,

• 2-dən 3-ə məsafə 1,

• 3-dən 3-ə məsafə 3.

Ümumi məsafə $1+3+0+2+1+3=10$ bərabərdir.

Nümunələr