Contest problemset description

Jak dobrze wiadomo, żołnierze mogą należeć do batalionu czołgowego. Z niewiadomych jednak przyczyn żołnierze nie lubią się, jeżeli numery batalionów, do których należą różnią się o więcej niż d.

Generał w wolnym czasie lubi grać w brydża, ale zgodnie z zasadami potrzebuje do tego trzech dodatkowych graczy. Żeby zapewnić sobie trochę różnorodności, postanowił, że będzie grał każdego wieczoru z inną trójką żołnierzy: nie będzie dwóch dni, w których zagra z tą samą trójką.

Dodatkowo przez jego złe doświadczenia z przeszłości, wie, że jeżeli w wybranej trójce żołnierzy będzie jakaś para, która się nie lubi to gra będzie nieprzyjemna.

Zastanawia się więc przez ile dni może grać w brydża, tak aby każda gra była przyjemna oraz żeby nigdy nie zagrał z taką samą trójką żołnierzy. Wiedząc, do którego batalionu czołgów należy każdy z żołnierzy, odpowiedz na jego pytanie.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N, d oznaczające odpowiednio liczbę żołnierzy oraz maksymalną różnicę w numerach batalionów czołgowych, do których należą żołnierze, którzy się lubią. W drugim wierszu wejścia znajduje się N liczb całkowitych a_i określających, do którego batalionu czołgów należy i-ty żołnierz.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się odpowiedź na pytanie generała.

Ograniczenia

1 ≤ a_i, d ≤ N ≤ 100 000.

Przykład

5 2
1 1 2 3 6

4

Do bazy przybyła nowa dostawa N czołgów oraz N rodzajów amunicji. Każdą z amunicji możemy scharakteryzować liczbą a_i oznaczającą jej poziom kompatybilności, analogicznie c_i oznacza poziom kompatybilności czołgu i.

Generał wie, że jeżeli włoży amunicję typu i do czołgu typu j, to użyteczność tego czołgu wynosić będzie a_i XOR c_i.

Problem w tym, że podczas dostawy, nie została mu przekazana informacja, którą amunicję najlepiej włożyć do którego czołgu. Atak na Mickiewiczówek już jutro i generał nie ma czasu na zastanawianie się, jakie jest przydzielenie maksymalizujące sumaryczną użyteczność. Chce jednak wiedzieć, jaka jest sumaryczna użyteczność czołgów po każdym możliwym przydzieleniu amunicji, przy założeniu, że do każdego czołgu został przydzielony inny jej rodzaj modulo 10⁹ + 7

Wejście

W pierwszym wierszu wejścia znajduje się liczba N oznaczająca liczbę czołgów i rodzajów amunicji. W drugim wierszu wejścia znajduje się N liczb a₁, a₂, …, a_N określające poziom kompatybilności amunicji i. W trzecim wierszu wejścia znajduje się N liczb c₁, c₂, …, c_N określające poziom kompatybilności czołgu i.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć sumaryczna użyteczność czołgów po wszystkich możliwych przydzieleniach modulo 10⁹ + 7.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ a_i, c_i ≤ 10⁹.

Przykład

2
0 1
1 4

10

4
4 2 3 7
1 0 5 6

360

Jest N nocowisk czołgów, które są połączone siecią N − 1 kabli. Okazało się jednak, że sieć ta jest niespójna, niektóre nocowiska nie są ze sobą połączone nawet pośrednio.

Generał przemyślał sprawę i uznał, że najtaniej będzie nie kupować nowych kabli tylko przepiąć stare, tak aby pomiędzy każdą parą nocowisk było (pośrednie lub bezpośrednie) połączenie.

Przepinanie polega na odpięciu kabla z obu nocowisk i wybraniu nowej pary, do której będzie on dodany.

Żeby się za bardzo nie napracować, generał chce wiedzieć ile minimalnie kabli musi przepiąć. Pomóż mu w tym zadaniu.

Wejście

W pierwszym wierszu wejścią znajduje się liczb N oznaczająca liczbę nocowisk czołgów. W kolejnych N − 1 wierszach znajdują po dwie liczby x, y oznaczające połączenie kablem nocowisk x oraz y.

Mogło się zdarzyć, że kable były łączone bardzo dziwnie i x może być równe y oraz uporządkowane pary x, y pojawiają się parę razy na wejściu.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć minimalna liczba kabli, które trzeba przepiąć.

Ograniczenia

1 ≤ x, y ≤ N ≤ 1 000 000.

Przykład

5
1 2
2 3
1 3
2 1

2