Problem description
Krasnal Xorek jest romantykiem. Chciałby wyznać swoje uczucia krasnalce Nandy, wręczając jej piękny wieniec z polnych kwiatów. Wieniec, który przygotował, składa się z N kwiatów. Kwiat na pozycji i ma Ai płatków. Wieniec ma kształt okręgu, dla 1 ≤ i < N kwiat na pozycji i sąsiaduje z kwiatem na pozycji i + 1, a dodatkowo kwiat na pozycji 1 sąsiaduje z kwiatem na pozycji N.
Gdy Xorek zobaczył gotowy wieniec, uznał, że kompozycja nie spełnia jego oczekiwań i postanowił ją zmienić. Stwierdził, że Nandy dużo bardziej spodobałby się wieniec, w którym na pozycjach 1, 2, …, N kwiaty mają odpowiednio B1, B2, …, BN płatków.
Spotkanie z Nandy ma rozpocząć się już niebawem. Xorek nie ma już czasu sporządzić nowego wieńca od zera. Może natomiast przekształcić wieniec A1, A2, …, AN w wieniec B1, B2, …, BN, wykonując każdą z poniższych operacji dokładnie raz:
- wybrać liczbę całkowitą K (0≤K<N) i obrócić wieniec o K pozycji w lewo. Po obrocie kwiat z pozycji i znajdzie się na pozycji ((i−K−1) mod N) + 1 — innymi słowy, ciąg A1, A2, …, AN stanie się AK + 1, AK + 2, …, AN, A1, …, AK,
- wybrać liczbę całkowitą X (0≤X<230) i rzucić pradawne krasnoludzkie zaklęcie Xorrium, które zmieni liczbę płatków każdego kwiatu z Ai na Ai ⊕ X.
Czy jesteś w stanie pomóc Xorkowi wyznaczyć wszystkie pary liczb (K,X), które pozwolą przekształcić wieniec A w wieniec B?
Wejście
W pierwszym wierszu wejścia znajduje się jedna dodatnia liczba całkowita N oznaczająca długość oryginalnego i docelowego wieńca.
W kolejnym wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych Ai oznaczających liczbę płatków na i‑tym kwiecie wieńca początkowego.
W ostatnim wierszu wejścia znajduje się ciąg N nieujemnych liczb całkowitych Bi oznaczających liczbę płatków i‑tego kwiatu w docelowym wieńcu.
Wyjście
Niech M oznacza liczbę par (K,X) pozwalających przekształcić wieniec początkowy w docelowy. Na wyjściu powinno znajdować się M wierszy. Jeśli takich par nie ma, wyjście jest puste.
W każdym z nich powinny znajdować się dwie liczby całkowite Ki oraz Xi, opisujące jedną poprawną parę. Wypisz pary posortowane rosnąco po K, a w przypadku remisu po X.
Ograniczenia
1 ≤ N ≤ 200 000, 0 ≤ Ai, Bi < 230.
Przykłady
| Wejście | Wyjście | Wyjaśnienie |
|
|
Po obróceniu wieńca o jedną pozycję w lewo ciąg ilości płatków kwiatów jest następujący: (2,1,0). Po rzuceniu zaklęcia Xorrium ciąg zmieni się na (2⊕3,1⊕3,0⊕3), co jest równe (1,2,3). Można pokazać, że nie istnieją inne pary (K,X) przekształcające (0,2,1) w (1,2,3). |
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|
| Wejście | Wyjście | |
|
|