Problem description

Japońska społeczność miłośników Shogi (szachów japońskich) wzywa Cię na pomoc! Jak głosi miejska legenda, przy każdym z N skrzyżowań Tokio mieszka jakiś mistrz szachowy. Na dodatek, ostatniej nocy spadły dwa centymetry śniegu. Jak na tamtejsze standardy to bardzo dużo i niestety żadna z M ulic Tokio nie jest przejezdna.

Dzięki temu, że różni szachiści używają różnych technik gry, a każdy z nich opracowuje swoje własne taktyki, partie szachów bywają bardzo widowiskowe. Dokładniej rzecz biorąc, styl gry i-tego szachisty (mieszkającego przy i-tym skrzyżowaniu) można opisać nieujemną liczbą X_i. To, jak bardzo partia pomiędzy szachistami z a-tego i b-tego skrzyżowania będzie ciekawa, jest proporcjonalne do X_a ⊕ X_b (xor liczb X_a oraz X_b) . Intuicyjnie, taki model rzeczywiście wydaje się być właściwy – gra szachisty z nim samym byłaby dość nudna: X_a ⊕ X_a = 0, za to różnice w użyciu niektórych taktyk bardzo zwiększają widowiskowość pojedynków.

Po otrząśnięciu się z początkowego zaskoczenia, drogowcy przystąpili do udrażniania miasta i powoli odśnieżają ulice, jedna po drugiej. Szachiści mieli na dzisiaj zaplanowany bardzo ważny turniej, więc bardzo dłuży im się oczekiwanie na zakończenie pracy drogowców. Każdy z nich ciągle zastanawia się, jaką najciekawszą partię mógłby rozegrać z jakimś szachistą, z którym może się spotkać przy obecnym stanie infrastruktury drogowej. Oczywiście, w miarę jak kolejne ulice są odblokowywane, ich perspektywy mogą się poprawiać.

Jeśli odblokowanie pewnej ulicy spowodowało, że dany szachista może teraz rozegrać ciekawszą partię niż dotychczas, to bardzo się ucieszy i natychmiast opublikuje pochlebnego tweeta na temat władz miasta.

Dobry wizerunek w mediach społecznościowych jest bardzo ważny dla prezydenta Tokio. Dlatego chciałby wiedzieć, ilu pozytywnych tweetów może się spodziewać po odśnieżeniu każdej z ulic.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N i M, oznaczające odpowiednio liczbę skrzyżowań i ulic. Drugi wiersz wejścia składa się z N liczb X₁, X₂, …X_N, pooddzielanych pojedynczymi odstępami, opisujących style gry kolejnych szachistów. Każdy z kolejnych M wierszy zawiera dwie liczby a i b opisujące ulicę łączącą skrzyżowania a oraz b. Ulice podane są w kolejności odśnieżania.

Wyjście

Na wyjściu należy wypisać M wierszy – i-ty z nich powinien zawierać liczbę szachistów, którym odśnieżenie i-tej ulicy umożliwiło dotarcie do przeciwników, z którymi mogą oni rozegrać ciekawszą partię niż dotychczas.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ M ≤ 200 000, 0 ≤ X_i < 2⁴⁰.

We wszystkich testach oprócz przykładowych liczby X_i są losowane niezależnie od siebie i jednostajnie z zakresu [0, 2⁴⁰).

Przykłady

5 5
0 1 4 5 0
1 2
2 3
4 5
1 3
3 5

2
3
2
0
1

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

2
2
2
2
4
4
8