Contest problemset description

Generał Sherman wygrał właśnie arcyważną bitwę z Pułkownikiem Leopardem. Kolumna jego czołgów wraca teraz do bazy aby świętować zwycięstwo. Jednakże ocalałe czołgi Pułkownika Leoparda zastawiły zasadzkę na oddział Generała Shermana. Pomóż centrali rozsztrzygnąć kto wygra to ostateczne starcie.

Wszystkie czołgi możemy prezentować jako punkty w kartezjańskim ukłądzie współrzędnych. Generał Sherman posiada N czołgów o współrzędnych
(x_1, 1,y₁), (x_1, 2,y₁), …, (x_1, N,y₁). Podobnie Pułkownik Leopard ma M czołgów o współrzędnych (x_2, 1,y₂), (x_2, 2,y₂), …, (x_2, M,y₂). Zachodzi y₂ > y₁.

Ponieważ czołgi Generała Shermana wracają do bazy, to ich lufy początkowo są skierowane w prawo. Pułkownik Leopard dobrze przygotował swój atak i lufy jego czołgów są skierowane w kierunku czołgów przeciwnika, w dół. Początkową przykładową sytuajcę ilustruje obrazek.

Gdy rozpocznie się walka, wszystkie czołgi będą mogły zacząć obracać swoje lufy, każdy z tą samą prędkością kątową. Jeśli lufa czołgu jest aktualnie skierowana na inny czołg, to może on go zniszczyć. Nawet jeżeli ma on sam zostać zniszczony w tym samym momencie. W szczególności jeśli dwa czołgi celują w siebie nawzajem to mogą oba siebie zniszczyć.

Pomóż centrali dowiedzieć się, który z przywódców pierwszy zniszczy wszystkie czołgi przeciwnika przy optymalnym postępowaniu obu stron. Może się zdarzyć, że na koniec bitwy wszystkie czołgi zostaną zniszczone, w takim przypadku ogłoś remis.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby: N, M, y₁ i y₂.
W drugim wierszu wejścia znajduje się N liczb: x_1, 1, x_1, 2, …, x_1, N.
W trzecim i ostatnim wierszu wejścia znajduje się M liczb: x_2, 1, x_2, 2, …, x_2, M.

Wyjście

Twój program powinien wypisać dokładnie jeden wiersz.
Jeśli wygrał Generał Sherman powinno się w nim znajdować słowo Sherman.
W przypadku wygranej Pułkownika Leoparda powinno to być słowo Leopard.
A w przypadku remisu słowo Remis.

Ograniczenia

1 ≤ N, M ≤ 100 000
1 ≤ y₁ < y₂ ≤ 1 000 000
1 ≤ x_1, 1 < x_1, 2 < … < x_1, N ≤ 1 000 000
1 ≤ x_2, 1 < x_2, 2 < … < x_2, M ≤ 1 000 000

Podzadania

Przykład

3 2 1 5
1 6 8
3 7

Leopard

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

Kapral Jasio z bardzo dobrym przybliżeniem oszacował ostatnio liczbę niemieckich czołgów. Zauważył, że na każdym z czołgów jest numer seryjny, a numery przyznawane są sekwencyjnie: 1, 2, 3, … i tak dalej. Jeśli więc wśród dwudziestu wytropionych czołgów największy numer był 95, to całkiem niezłym przybliżeniem liczby wszystkich czołgów jest 100. Kapitan Bajtazar pochwalił kaprala Jasia i obiecał mu awans jeżeli rozwiąże ten problem (kolejnych numerów seryjnych) w bajtockiej armii.

Jasio postanowił, że numery seryjne bajtockich czołgów powinny być ułamkami zwykłymi. Aby było łatwiej, ułamki te muszą być nieskracalne. Dla niepoznaki, numery czołgów będą wprowadzane do ściśle tajnego cybernetycznego systemu w postaci liczb dziesiętnych. Przykładowo: czołg o numerze seryjnym $\frac{1}{2}$ będzie figurował w systemie pod nazwą 0.5. System ten jednak przyjmuje numery o skończonej precyzji. Wyklucza to więc niektóre numery seryjne czołgów, takie jak $\frac{1}{3} = 0.333\ldots$. Jasio postanowił więc używać ułamków najprostszych: ułamków zwykłych nieskracalnych, które zapisane jako ułamki dziesiętne mają skończone nieokresowe rozwinięcie. Takie ułamki Jasio nazwał łatwymi. Przykładowo więc, ułamki $\frac{1}{2}$ oraz $\frac{97}{50}$ są łatwe, zaś ułamki $\frac{1}{3}$ oraz $\frac{5}{20}$ nie są. Dodatkowo, Jasio nie uznaje za łatwe ułamków z mianownikiem 1, ani ułamków z licznikiem 0. Są to liczby całkowite, nie ma sensu zapisywać ich w nienormalny sposób.

W wojsku dysponują jedynie skończoną i bardzo niewielką liczbą szablonów cyfr, które można odmalować na czołgach. Każdej cyfry można użyć tylko jeden raz: jako cyfrę licznika ułamka, jako cyfrę mianownika ułamka albo nie użyć jej wcale. Cyfry, zarówno w liczniku jak i w mianowniku, można wstawiać w dowolnej kolejności. Niedopuszczalne jest uzyskanie zer wiodących: ani w liczniku ani w mianowniku. Pomóż Jasiowi zasłużyć na awans w armii. Ile różnych numerów seryjnych czołgu (łatwych ułamków) Jasio może stworzyć ze swojego zbioru cyfr?

Napisz program, który: wczyta (multi)zbiór dostępnych cyfr, wyznaczy liczbę łatwych ułamków jakie możliwe są do uzyskania z dostępnego zbioru i wypisze wynik na wyjście.

Wejście

W pierwszym (jedynym) wierszu wejścia znajduje się ciąg cyfr, bez żadnych odstępów.

Wyjście

W pierwszym (jedynym) wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – reszta z dzielenia przez 10⁹ + 7 liczby możliwych do uzyskania łatwych ułamków.

Ograniczenia

Długość ciągu cyfr nie przekracza 18 znaków.

Przykład

1230

14