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ı yol boyunca olan bütün zirvələrin dəyərlərinin XOR əməliyyatının nəticəsidir. Tapşırığınız 1 \leq u \leq v \leq n şərtini ödəyən bütün zirvə cütləri $(u,v)$ üçün məsafələrin cəmini hesablamaqdır.

\InputFileBirinci sətrdə bir tam ədəd $n$ (1 \leq n \leq 10^5) — ağacdakı zirvələrin sayı verilir.

İkinci sətrdə $n$ tam ədəd a_1, a_2, \ldots, a_n (0 \leq a_i \leq 10^6) — hər zirvəyə aid dəyərlər verilir.

Sonrakı n-1 sətrin hər birində iki tam ədəd u_i və v_i (1 \leq u_i, v_i \leq n) — zirvələr arasında olan kənarı göstərir.

\OutputFileÇıxışa bir tam ədəd verin — 1 \leq u \leq v \leq n şərtini ödəyən bütün zirvə cütləri arasındakı məsafələrin cəmi.

\NoteMəsələn, verilmiş ağac üçün hesablamalar belədir:

• $1$-dən $1$-ə məsafə $1$-dir.

• $1$-dən $2$-yə məsafə $3$-dür.

• $1$-dən $3$-ə məsafə $0$-dır.

• $2$-dən $2$-yə məsafə $2$-dir.

• $2$-dən $3$-ə məsafə $1$-dir.

• $3$-dən $3$-ə məsafə $3$-dür.

Bu məsafələrin cəmi 1 + 3 + 0 + 2 + 1 + 3 = 10-a bərabərdir.