Contest problemset description

Dla przyciągnięcia uwagi kibiców, Liga Mistrzów co jakiś czas zmienia swój format. Jedna z poprzednich zmian dotyczyła zasad odnoszących się do liczby bramek zdobytych na wyjeździe. Dwa zespoły mierzyły się ze sobą w dwumeczu, na podstawie którego decydowały się losy rywalizacji. Jeśli bilans bramkowy był taki sam, to decydowała zasada przewagi bramek zdobytych w meczach wyjazdowych, tzn. drużyna, która strzeliła więcej bramek jako gość, wygrywała.

Twoim zadaniem jest wyłonienie zwycięzcy dwumeczu. Możesz założyć, że zawsze jest to możliwe, tzn. dane wejściowe dobrano tak, aby zwycięzca był wyłoniony jednoznacznie.

Wyniki podane są w formacie: najpierw liczba goli strzelonych przez drużynę domową, a później przez drużynę wyjazdową. W pierwszym meczu drużyną domową jest drużyna A, a wyjazdową – drużyna B. W drugim meczu drużyny zamieniają się rolami, tzn. najpierw podano liczbę bramek zdobytych przez drużynę B, a potem przez drużynę A.

Wejście

Pierwszy wiersz wejścia zawiera dwie liczby całkowite a, b, będące wynikiem pierwszego meczu. Drugi wiersz wejścia zawiera dwie liczby całkowite c, d, będące wynikiem drugiego meczu.

Wyjście

Powinieneś wypisać A, jeśli to drużyna A okazała się zwycięzcą dwumeczu, albo B, jeśli okazała się nią drużyna B.

Ograniczenia

0 ≤ a, b, c, d ≤ 9.

Przykłady

0 3
1 1

B

2 0
3 1

A

Karol już od wielu lat jest trenerem linii obrony. Z doświadczenia wie, że najważniejszym zadaniem zespołu obrońców jest zapewnienie szczelnej bariery, która nie przepuści żadnego piłkarza przeciwnej drużyny. Próbuje ze wszystkich sił nauczyć tego swoją aktualną kadrę piłkarzy, ale nie zawsze staje ona na wysokości zadania…

Aktualnie linia obrony składa się z N zawodników, którzy mają za zadanie zabezpieczyć przed przeciwnikiem całą szerokość boiska, którą dla uproszczenia oznaczamy jako spójny przedział liczb rzeczywistych od 0 do D. Obrońca o numerze i (dla 1 ≤ i ≤ N) jest ustawiony na pozycji p_i i jest w stanie błyskawicznie przemieścić się o odległość r_i , co oznacza, że skutecznie chroni przedział boiska zawierający się w zakresie od p_i − r_i do p_i + r_i. Wszystkie takie przedziały są rozłączne (mogą się stykać co najwyżej końcami) i bardzo ważnym jest to, żeby tak zostało, gdyż ewentualna kolizja piłkarzy mogłaby doprowadzić do kontuzji!

Z racji, że jest już za późno na zmianę taktyki, pozycje piłkarzy nie mogą już zostać zmienione. Na szczęście, każdy z obecnych obrońców zadeklarował, że może on zwiększyć broniony przez siebie zakres r_i o wartość 1, nawet wielokrotnie, ale każdorazowo będzie to wymagało podniesienia jego premii o c_i (w końcu będzie trzeba wtedy zakupić wygodniejsze obuwie, zaplanować dodatkowe masaże po meczach, czy zapewnić sobie dodatkowe bidony z napojem izotonicznym).

Karol zastanawia się teraz, jaki minimalny koszt będzie musiał ponieść, aby linia obrony zrobiła się szczelna, pokryła co najmniej całą szerokość boiska (zasięg bocznych piłkarzy może wychodzić poza boisko) i żadni dwaj piłkarze nie weszli ze sobą w kolizję. Trudno mu nawet zdecydować czy osiągnięcie takiego celu jest w ogóle możliwe! Czy jesteś w stanie mu pomóc?

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz D, oznaczające liczbę obrońców oraz szerokość boiska.
W kolejnych N wierszach znajdują się opisy pozycji, zasięgów i kosztów kolejnych piłkarzy. Każdy z nich składa się z trzech liczb całkowitych p_i, r_i i c_i, oznaczających, że dany obrońca stoi na pozycji p_i, jego aktualny zasięg dobiegu to r_i, a zwiększenie jego zasięgu o wartość 1 kosztuje c_i.

Wyjście

Jeżeli uzyskanie poprawnego wydłużenia zakresów piłkarzy nie jest możliwe, na wyjściu wypisz jedno słowo NIEMOZLIWE. W przeciwnym wypadku wypisz jedną liczbę całkowitą oznaczającą minimalny koszt, jaki trzeba będzie ponieść na premie dla piłkarzy.

Ograniczenia

1 ≤ N ≤ 1 000, 1 ≤ D ≤ 100 000,
0 ≤ c_i ≤ 10⁹,
0 ≤ p_i ≤ D, 1 ≤ r_i ≤ D, p_i + r_i ≤ p_i + 1 − r_i + 1.

Przykłady

3 15
2 1 10
7 2 5
13 1 3

21

4 9
1 1 1
3 1 1
6 1 1
8 1 1

NIEMOZLIWE

Zmiana barw, numerów na koszulkach i wielkie pieniądze — z tym najczęściej kojarzą nam się transfery piłkarskie. Czasem te pieniądze mogą być tak duże, że aż trudno w nie uwierzyć…

Robicik dopiero niedawno zaczął interesować się piłką nożną, a jego głównym źródłem informacji jest jego najlepszy kolega Robajcik. To od niego dowiedział się o transferze swojego ulubionego piłkarza Nbitté do jednego z najlepszych klubów – Rzeczywistego Bajtrytu. Kwota, jaką klub zapłacił za tego zawodnika wyniosła aż T bajtodolarów! Cóż za wspaniała wiadomość! Czy aby nie zbyt wspaniała?

No właśnie… Robicik nie ufa za bardzo swojemu koledze i chciałby sprawdzić autentyczność jego słów. Pamięta, że kilka lat temu Nbitté został zakupiony przez poprzedni klub za S bajtodolarów i od tamtego czasu zawodnik rozegrał N meczów. Za każdy wygrany mecz wartość zawodnika się podwajała, a za przegrany lub zremisowany dzieliła przez 2 (zaokrąglając w dół, gdyż jest to zawsze liczba całkowita). Wystarczyłoby więc policzyć, czy kwota powiedziana przez Robajcika zgadza się z wartością rynkową po wszystkich meczach, prawda?

Otóż jest jeszcze jeden problem, mianowicie Robicik nie pamięta wyników każdego z meczów. Pamięta jednak doskonale, że w całej karierze Nbitté jego wartość rynkowa nigdy nie przekroczyła (i niekoniecznie nawet osiągnęła) M bajtodolarów. Pomóż mu zdecydować, czy na podstawie znanych przez Robicika wyników i początkowej wartości zawodnika, mecze o nieznanych wynikach mogły wypaść tak, że kwota Nbitté po żadnym meczu nie była większa niż M i na koniec wyniosła tyle co zadeklarował Robajcik.

Wejście

W tym zadaniu znajduje się wiele przypadków testowych. Pierwszy wiersz wejścia zawiera jedną liczbę naturalną T, oznaczającą liczbę tych przypadków.
Każdy z przypadków testowych rozpoczyna się wierszem zawierającym cztery liczby N, S, T, M, oznaczające kolejno liczbę meczów, początkową i końcową wartość rynkową zawodnika oraz kwotę, jakiej na pewno ta wartość nigdy nie przekroczyła. W kolejnym wierszu znajduje się ciąg znaków o długości N składający się ze znaków W, P oraz ?. Znak W oznacza mecz wygrany przez drużynę Nbitté, a P przegrany lub zremisowany. Znaki zapytania to mecze, których wyników Robicik zapomniał.

Wyjście

Twój program powinien dla każdego z przypadków testowych wypisać jedną linię zawierającą jedno słowo TAK albo NIE, w zależności od tego, czy w danym przypadku istnieją takie przyporządkowania wyników nieznanych meczów, że kwota Nbitté nie przekroczyła maksymalnej wartości i wynosiła na koniec tyle, co powiedział Robajcik.

Ograniczenia

1 ≤ T, N ≤ 100 000, 1 ≤ S, T ≤ M ≤ 10¹⁸,
łączna suma długości N we wszystkich przypadkach testowych nie przekroczy 500 000.

Przykłady

4
3 2 4 12
PWW
3 2 4 6
WWP
6 1 4 4
W????W
6 1 4 4
W????P

TAK
NIE
TAK
NIE

Bajteuro 2024 już za pasem, a co za tym idzie drużyna Bitocji postanowiła oficjalnie ogłosić już ustawienie, w jakim będzie rozgrywała mecze. Wiadomo, że w trakcie mistrzostw zostanie rozegrane dokładnie M meczów, a w i-tym z nich Bitocja wystawi skład złożony z N_i zawodników. Wiadomo również, że na każdy mecz przygotowano osobne ustawienie. Aby jednak utrudnić przeciwnikom analizę taktyki, postanowiono, że zamiast zwykłego ustawienia, będzie ono miało kształt drzewa. Oznacza to, że z góry zdefiniowano jakie pary piłkarzy mają ze sobą wymieniać podania, przy czym dobrano je tak, że dokładnie jeden piłkarz będzie ustawiony na pozycji bramkarza, a każdy inny zawodnik będzie mógł cofnąć piłkę do dokładnie jednego innego zawodnika. W założeniu ma to wykluczyć poprzeczne podania, co spowoduje, że widowisko będzie bardziej atrakcyjne dla kibiców.

Selekcjoner reprezentacji Bitocji nie przydzielił jeszcze zawodnikom numerów na koszulkach. Chce on przydzielić numery od 1 do N_i włącznie tak, aby żadna para zawodników, którzy mają ze sobą wymieniać podania nie miała numerów różniących się o dokładnie 1. Pomoże to uniknąć nieporozumień w trakcie meczu, kiedy będzie na bieżąco przekazywał komunikaty swojej drużynie.

Dodatkowym wymaganiem sponsora drużyny Bitocji jest również to, by zawodnicy z numerami 1 i N_i również nie wymieniali między sobą podań. Nie jest powiedziane, że zawodnik z numerem 1 miałby być bramkarzem, a zawodnik z numerem N_i napastnikiem, ale mimo to takie połączenie mogłoby zbyt mocno kojarzyć się ze sławetnym zagraniem lagi na Robajcika.

Pomóż selekcjonerowi w przydzieleniu numerów na koszulkach zawodnikom dla każdego ze spotkań. Napisz program, który dla specyfikacji każdego meczu znajdzie dowolne poprawne przydzielenie numerów na koszulkach dla zawodników, albo stwierdzi, że taka konfiguracja nie istnieje.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się jedna liczba M oznaczająca liczbę meczów, które zostaną rozegrane.
Następnie dla każdego meczu w osobnym wierszu znajduje się liczba N_i oznaczająca liczbę zawodników wystawionych w i-tym meczu. W kolejnych N_i − 1 wierszach znajdują się po dwa napisy a oraz b – nazwiska piłkarzy, oznaczające, że zawodnik o nazwisku a wymienia podania z zawodnikiem o nazwisku b.
Wiadomo również, że sieć połączeń między graczami tworzy drzewo (każde nazwisko pojawia się przynajmniej raz oraz graf jest spójny).

Wyjście

Dla każdego ze spotkań, jeżeli istnieje ustawienie spełniające wymogi, to wypisz słowo TAK, a spośród N_i kolejnych wierszy każdy powinien zawierać nazwisko zawodnika oraz numer na jego koszulce w taki sposób, by każdy zawodnik miał przypisany inny numer z zakresu od 1 do N_i, oraz by przypisanie spełniało opisane powyżej warunki. W przeciwnym wypadku w jedynym wierszu wyjścia wypisz słowo NIE. Jeżeli istnieje wiele rozwiązań spełniających powyższe wymogi, to wypisz dowolne z nich.

Ograniczenia

1 ≤ M ≤ 100 000, 2 ≤ N_i ≤ 200 000,
każde nazwisko podane na wejściu jest napisem złożonym z małych liter alfabetu angielskiego o długości co najwyżej 20,
sumaryczna liczba zawodników we wszystkich meczach nie przekroczy 200 000.

Przykłady

3
2
szczesny lewandowski
5
a b
c b
c d
e d
11
boruc jop
bak boruc
zewlakow bak
bak krzynowek
bak lewandowski
lewandowski guerreiro
smolarek guerreiro
saganowski lewandowski
dudka wasilewski
jop wasilewski

NIE
TAK
a 1
b 3
c 5
d 2
e 4
TAK
boruc 7
jop 5
bak 11
zewlakow 9
krzynowek 2
lewandowski 4
guerreiro 8
smolarek 10
saganowski 6
dudka 1
wasilewski 3

Michał, jeden z najlepszych polskich trenerów, często nazywany polskim Pepem, jest świetnym taktykiem — podobnie, jak jego bardziej utytułowany kolega Pep. Wymyślił on skomplikowaną taktykę, wymagającą wielu obliczeń, które ma nadzieję częściowo zautomatyzować.

W swoim planie podzielił on boisko na planszę o N wierszach i M + 2 kolumnach. Bramka reprezentacji Polski znajduje się pośrodku pierwszej kolumny, podczas gdy bramka przeciwnej reprezentacji znajduje się pośrodku M + 2-giej kolumny.

W piłce kluczowe jest szybkie przeniesienie piłki pod bramkę rywala. Będziemy rozważali scenariusz, w którym chcemy dostarczyć piłkę jak najszybciej do M + 2 kolumny — będąc już tak blisko bramki rywala, nie ma znaczenia, czy umieścimy piłkę w bramce, czy nie.

W chwili, gdy zawodnik naszej reprezentacji ma piłkę w polu na planszy, może przenieść się z nią do sąsiedniej kolumny, póki pozostaje w tym samym wierszu. Może również ją zagrać do zawodnika w innym wierszu, ale tylko i wyłącznie jeśli znajduje się on w sąsiadującej kolumnie. Jako że trener Michał jeszcze nie ustalił ustawienia zawodników, to można w symulacji założyć, że takowy zawodnik znajdzie się w odpowiednim miejscu.

Należy jednak pamiętać, że każde takie podanie obarczone jest pewnym ryzykiem, zależnym od długości podania — im dłuższe podanie, tym trudniejsze jest ono do wykonania. Ryzyko podania zagranego z wiersza R₁ do wiersza R₂ wynosi |R₁−R₂|.

Wszystko byłoby bardzo proste, ale niestety na pewnych polach naszej planszy są też przeciwnicy. W naszej symulacji zakładamy, że dla każdej kolumny C od 2 do M + 1, istnieje pewna liczba pierwsza P_C, która oznacza, że przeciwnicy mogą znajdować się tylko w wierszach o numerach podzielnych przez P_C dla kolumny C. Aby zmaksymalizować szansę sukcesu, należy całkowicie unikać tych pól.

Trenera Michała interesuje, jakie jest minimalne ryzyko przemieszczenia się z piłką do M + 2 kolumny z pewnego ustalonego pola na planszy. Twoim zadaniem jest odpowiedzenie na wszystkie jego zapytania.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite N, M i Q, oznaczające wymiary planszy na boisku oraz liczbę zadanych przez trenera Michała zapytań. W drugim wierszu znajduje się M liczb całkowitych, i-ta z nich oznacza P_i + 1.

W kolejnych Q wierszach znajdują się opisy zapytań trenera Michała. W i-tym wierszu znajdują się dwie liczby całkowite R_i, C_i, oznaczające odpowiednio, że pole startowe dla tego zapytania jest w wierszu R_i i kolumnie C_i. Możesz założyć, że w tym polu nie znajduje się żaden przeciwnik.

Wyjście

Na standardowe wyjście powinieneś wypisać dokładnie Q wierszy. Każdy z nich powinien zawierać pojedynczą nieujemną liczbę całkowitą, oznaczającą minimalne ryzyko dla i-tego zapytania.

Ograniczenia

2 ≤ N, M ≤ 100 000, 1 ≤ Q ≤ 1 000 000,
2 ≤ P_i ≤ N, P_i jest pierwsze,
1 ≤ R_i ≤ N, 1 ≤ C_i ≤ M + 1.

Przykłady

4 4 3
2 3 2 2
3 1
2 3
1 1

2
1
0

6 6 6
2 3 5 3 5 2
6 4
4 1
5 1
6 1
5 5
1 4

3
3
2
3
2
0

Na wielkich turniejach piłkarskich, bardzo ważną rolę odgrywa też to czym zajmują się zawodnicy w dniach przed ważnymi meczami. Nietypowe zajęcia, wymagające dużego skupienia i precyzji, pozwalają na istotne zredukowanie stresu. Z tego właśnie powodu niektóre reprezentacje w takich dniach wybierają się na strzelnicę postrzelać z łuku albo do zegarmistrza składać zegarki. Za to reprezentacja Bajtocji będzie zajmowała się składaniem figur z trójwymiarowych klocków.

Celem każdego z piłkarzy będzie złożenie figury składającej się z sześcianów o wymiarach 1 × 1 × 1, z których każdy ma wszystkie wierzchołki w punktach o współrzędnych całkowitych. Ich zadanie polega na określeniu, czy jest możliwe utworzenie danej figury z klocków, które też składają się z takich sześcianów. Każdy klocek może być umieszczony w dowolnym miejscu i być dowolnie obrócony, jeżeli tylko żaden z jego sześcianów nie koliduje z innymi klockami w figurze końcowej.

Niektórym piłkarzom ta sztuka się nie udała. Czy jesteś w stanie im pomóc?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita M, oznaczająca liczbę sześcianów składających się na figurę, którą trzeba utworzyć.
Kolejne M wierszy zawiera pozycje kolejnych sześcianów składających się na figurę. Każdy z tych wierszy zawiera trzy liczby całkowite x, y, z, oznaczające sześcian, którego przeciwległe wierzchołki znajdują się w punktach (x,y,z) oraz (x+1,y+1,z+1) trójwymiarowego układu współrzędnych.
W kolejnym wierszu znajduje się liczba naturalna N, a po niej znajdują się opisy N klocków, każdy z nich w takim samym formacie jak powyżej.
Możesz założyć, że wszystkie figury i klocki podane na wejściu są poprawne i spójne (zakładając że dwa sześciany są sąsiednie jeśli stykają się całymi ścianami). Możesz też założyć, że sumaryczna liczba sześcianów w klockach jest równa liczbie sześcianów w układanej figurze.

Wyjście

Jeżeli z klocków nie da się utworzyć żądanej figury, na wyjściu wypisz -1.
W przeciwnym przypadku na wyjściu wypisz M liczb całkowitych a₁, …, a_M, oddzielając je pojedynczymi spacjami. Liczba a_i powinna oznaczać, że i-ty sześcian figury podanej na wejściu będzie częścią klocka o numerze a_i.
Jeżeli istnieje wiele poprawnych rozwiązań, możesz wypisać dowolne z nich.

Ograniczenia

1 ≤ N, M ≤ 22, 0 ≤ x, y, z ≤ 22.

Przykłady

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

3 3 2 1 3 1 2 2 2 1 1 1

Po zakończeniu sezonu Robicik zdecydował się na zmianę klubu. Zastanawia się on teraz jak dużo będzie w stanie zarobić…

Rynek transferowy jest bardzo dynamiczny, więc Robicik zatrudnił swojego przyjaciela, Robajcika, aby ten przygotował zestawienie ofert, które mają szansę pojawić się podczas okna transferowego. Robajcik dla każdej z hipotetycznych ofert oszacował jakie jest prawdopodobieństwo, że pojawi się ona na rynku. Dodatkowo, każda z tych ofert zawiera informację kiedy się pojawi, do kiedy trzeba będzie podjąć decyzję o jej przyjęciu oraz na jaką opiewa kwotę.

Robicik wie, że jak przyjmie jedną ofertę, to nie będzie mógł już rozważać pozostałych. Czy jesteś w stanie oszacować jaka jest oczekiwana kwota jaką jest on w stanie zarabiać, zakładając, że spróbuje on wybrać ofertę w optymalny sposób?

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba całkowita N, oznaczająca liczbę ofert, które hipotetycznie pojawią się w oknie transferowym.
Każdy z kolejnych N wierszy zawiera opis jednej oferty. Składa się on z jednej liczby rzeczywistej p_i oraz trzech liczb całkowitych a_i, b_i i w_i, oddzielonych pojedynczymi spacjami. Liczby te oznaczają kolejno prawdopodobieństwo pojawienia się danej oferty, dzień okna transferowego w którym dana oferta się pojawi, dzień w którym należy podjąć decyzję oraz wartość danej oferty.

Wyjście

Na wyjściu wypisz jedną liczbę rzeczywistą, oznaczającą oczekiwaną wartość kwoty jaką jest w stanie zarabiać Robicik. Twój wynik będzie uznany za poprawny jeżeli jego błąd względny lub bezwzględny będzie mniejszy niż 10⁻⁶.

Ograniczenia

1 ≤ N ≤ 200 000,
0 ≤ p_i ≤ 1 (podana z dokładnością do 10⁻⁶),
1 ≤ a_i < b_i ≤ 2 ⋅ N, 1 ≤ w_i ≤ 1 000 000,
wszystkie wartości a_i oraz b_i są parami różne.

Przykłady

3
0.500000 1 3 6
0.500000 2 5 1
0.100000 4 6 59

6.3750000000

Wyjaśnienie

$\\$ Zauważmy, że w tym przypadku ostatnia oferta ma wartość oczekiwaną 5.9. Zastanówmy się zatem co może się wydarzyć w momencie 3.

• Z prawdopodobieństwem 0.25 nie pojawiła się żadna z pierwszych dwóch ofert – wtedy wartość oczekiwana zarobków Robicika to 5.9.
• Z prawdopodobieństwem 0.25 pojawiła się pierwsza oferta, a druga nie – wtedy Robicikowi opłaca się ją wziąć, bo jest warta 6, a to więcej niż 5.9.
• Z prawdopodobieństwem 0.5 pojawi się druga oferta – wtedy zauważmy, że niezależnie od tego czy pierwsza oferta się pojawiła czy nie, wartość oczekiwana zarobków Robicika w momencie 4 wyniesie 0.1 ⋅ 59 + 0.9 ⋅ 1 = 6.8, więc opłaca mu się poczekać.

Sumując powyższe wartości otrzymujemy 0.25 ⋅ 5.9 + 0.25 ⋅ 6 + 0.5 ⋅ 6.8 = 6.375.

$\\$

3
0.200000 1 6 10
0.100000 2 5 5
1.000000 3 4 1

3.1200000000

4
0.500000 1 2 7
0.500000 3 4 4
0.500000 5 6 9
0.500000 7 8 6

6.5000000000

Choć ostatnie EURO nie potoczyło się tak, jak w Polsce oczekiwano, to nie mogło się ono rozstrzygnąć w lepszy sposób z punktu widzenia Hiszpanów. Jednym z dowodów na to, jak intensywnie hiszpańscy kibice przeżywali mecze, są zapisy komentatorskie z ich meczów.

Po dowolnej bramce strzelonej przez Hiszpanów można było usłyszeć radosne “GOOOOOOOL GOL GOL GOL GOL GOL GOL”. Bramki dla rywali były komentowane w dużo smutniejszy sposób, więc kibice słyszeli tylko “GOL”. Mając dany zapis komentarza z meczu, można więc spróbować wywnioskować, ile goli padło w danym spotkaniu.

Przykładowo, mając dany skrawek komentarza “Yamal! GOOOOL! Cada día te quiero más”, można wywnioskować, że padła jedna bramka, ponieważ występuje w nim słowo GOL — liczba liter O nie ma tu znaczenia. W przypadku komentarza “Morata! GOL GOL GOL Capitan” wnioskujemy nadal, że padła zaledwie jedna bramka, ponieważ słowo GOL, choć padło trzykrotnie, to zostały one wypowiedziane tuż po sobie.

Twoim zadaniem jest na podstawie danego zapisu komentatorskiego ustalić liczbę bramek, która padła w meczu. Dla ułatwienia podany zapis składa się tylko z małych i dużych liter alfabetu łacińskiego.

Wejście

W pierwszym wierszu standardowego wejścia znajduje się pojedyncza liczba całkowita N, oznaczająca długość zapisu komentatorskiego ze spotkania. W drugim wierszu standardowego wejścia znajduje się ciąg N małych i dużych liter alfabetu łacińskiego, oznaczający zapis komentatorski ze spotkania.

Wyjście

W jedynym wierszu standardowego wyjścia powinna znaleźć się jedna liczba całkowita nieujemna, oznaczająca liczbę goli, która padła w tym spotkaniu według zasad podanych w treści zadania.

Ograniczenia

1 ≤ N ≤ 100 000.

Przykłady

33
YamalGOOOLAZZZOCadadiatequieromas

1

22
MorataGOLGOLGOLCapitan

1

50
OlmoGooooooooolWirtzGolMerinoGOLGOLGOLGOLGOLGOLGOL

3

10
golGOLggol

2

21
GOooOOOlllazzzooooGol

2

10
gollgolgol

2

Trener Karol z niedowierzaniem patrzył jak jego zespół, Wrocławskie Krasnoludki, rozgromił faworyta spotkania, Krakowskie Smoki, 5 do 0. Radości nie było końca, właśnie awansowali do finału Mistrzostw Szkół Średnich w Kopaniu Zespołowym.

Trener Karol wie, że nie można osiąść na laurach. Musi przygotować drużynę do gry przeciwko zawodnikom drużyny Warszawskie Syrenki, którzy są znani z agresywnej gry, nawet w polu karnym. Aby nie zmarnować żadnej szansy, na najbliższym treningu zawodnicy będą ćwiczyli wykonywanie rzutów wolnych. Dla uproszczenia ćwiczeń, strzały będą wykonywane tylko po ziemi i w linii prostej.

Każde ćwiczenie można opisać w następujący sposób. Gracz wykonujący rzut wolny stoi w punkcie (0,0). Bramkę symbolizuje odcinek,  równoległy do osi OY. Wewnątrz bramki, czyli na wspomnianym właśnie odcinku, stoi bramkarz, który jest w stanie obronić fragment bramki. Ten fragment też stanowi odcinek. Pomiędzy atakującym, a bramką ustawiony jest mur. W danym ustawieniu jest szansa na strzelenie gola, jeżeli istnieje półprosta zaczynająca się w punkcie (0,0) i przecinająca odcinek symbolizujący bramkę, ale nie przecina odcinka symbolizującego mur ani fragmentu, który może obronić bramkarz.

Pomóż trenerowi Karolowi i powiedz, czy w danym ustawieniu jest szansa na strzelenie gola, bo wtedy zostanie ono dodane do planu treningowego.

Wejście

Pierwszy wiersz zawiera trzy liczby B_X, BG_Y i BD_Y, oznaczające odpowiednio współrzędną X bramki oraz współrzędne Y górnego i dolnego końca bramki.
Drugi wiersza zawiera dwie liczby FG_Y oraz FD_Y, oznaczające współrzędną Y górnego oraz dolnego końca fragmentu bramki, który jest w stanie obronić bramkarz.
Ostatni wiersz zawiera cztery liczby MG_X, MG_Y, MD_X oraz MD_Y, spośród których pierwsza para oznacza współrzędne górnego końca muru, a druga – współrzędne dolnego końca muru.

Wyjście

Jeżeli w danym ustawieniu jest możliwe strzelenie gola, to twój program powinien wypisać jedno słowo TAK, a w przeciwnym przypadku jedno słowo NIE.

Ograniczenia

1 ≤ MG_X < B_X ≤ 10⁹,
1 ≤ MD_X < B_X ≤ 10⁹,
 − 10⁹ ≤ BD_Y < BG_Y ≤ 10⁹,
BD_Y ≤ FD_Y < FG_Y ≤ BG_Y,
 − 10⁹ ≤ MD_Y < MG_Y ≤ 10⁹.

Przykłady

6 8 2
8 6
3 3 5 2

TAK

6 8 2
8 6
3 3 3 1

NIE

6 8 2
8 6
3 2 3 1

TAK

10 20 -20
10 -10
9 30 1 -50

NIE

$\\[0.1cm]$

Wyjaśnienie

Powyższe rysunki przedstawiają sytuację w pierwszym i drugim teście przykładowym. Kolorem czarnym i literą B oznaczona jest bramka, kolorem niebieskim i literą M oznaczony jest mur, a kolorem fioletowym i literą F jest oznaczony fragment, którego broni bramkarz.

W przypadku pierwszego testu zobrazowany jest przykładowy kierunek celnego strzału.

W drugim teście taki kierunek nie istnieje — jeżeli zawodnik odda strzał poniżej muru, to nie trafi w bramkę, a jeżeli powyżej, to strzał zostanie obroniony przez bramkarza.

Robicik i Robajcik postanowili, że ich ćwiczenia na treningu powinny nie tylko poprawiać szybkość i zwinność, ale również powinny skupiać się na taktyce, logicznym myśleniu oraz znajomości sytuacji na boisku. Dlatego też obmyślili nowe ćwiczenie z pachołkami.

Na początku ćwiczenia, piłkarze narysowali na środku boiska układ współrzędnych, po czym podzielili go na kwadraty o rozmiarze 1 × 1 o rogach mających całkowite współrzędne. Robicik i Robajcik ustawili się w pewnych dwóch kwadratach. Następnie, we wszystkich rogach powyższych kwadratów, gdzie suma współrzędnych jest nieparzysta, postawili pachołek. W ten sposób na każdej pionowej i poziomej linii były naprzemiennie pachołek oraz puste pole.

Piłkarze mogą teraz wykonywać ruchy polegające na przejściu do kwadratu sąsiadującego bokiem z tym, na którym aktualnie stoją. Jednakże, aby wykonać taki ruch, na dokładnie jednym z końców boku, przez który chcą przejść, musi znajdować się pachołek. Po przejściu przez dany bok, piłkarz musi przełożyć ten pachołek na drugi koniec tego boku.

Całe ćwiczenie polega na tym, żeby piłkarze, startując z pewnych pozycji A i B wykonali sekwencję ruchów, po której zamienią się oni miejscami. Możesz założyć, że boisko jest na tyle duże, że zawsze będą mieli wystarczająco miejsca na wykonanie dozwolonego ruchu w dowolną ze stron.

Robicik i Robajcik najwyraźniej nie radzą sobie z tym ćwiczeniem. Są nawet przekonani, że w niektórych przypadkach poprawna sekwencja ruchów nie istnieje! Czy jesteś w stanie im pomóc oraz sprawdzić czy rzeczywiście mają rację?

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie, oddzielone pojedynczym odstępem, liczby całkowite X_a, Y_a oznaczające kwadrat w którym znajduje się Robicik (a dokładniej, to współrzędne jego lewego dolnego rogu). Analogicznie, w drugim wierszu znajdują się liczby X_b, Y_b oznaczające kwadrat, w którym znajduje się Robajcik.
Możesz założyć, że początkowe pozycje piłkarzy są różne.

Wyjście

W pierwszym wierszu wyjścia powinna znaleźć się liczba kroków n, która oznacza długość zaproponowanego przez ciebie rozwiązania. Następnie, w n kolejnych wierszach powinny znaleźć się opisy ruchów.
Opis jednego ruchu składa się z dwóch znaków – pierwszy z nich powinien oznaczać numer piłkarza wykonującego ruch (A oznacza Robicika, a B oznacza Robajcika). Drugi znak powinien natomiast oznaczać kierunek ruchu: L (lewo), P (prawo), G (góra) albo D (dół). Dwa znaki oznaczające jeden ruch nie powinny być oddzielone odstępem.
Wypisana przez Ciebie liczba ruchów n nie może być większa niż 1 000 000. Można pokazać, że jeśli odpowiedni ciąg ruchów istnieje to (przy przyjętych ograniczeniach) istnieje także taki o długości co najwyżej 1 000 000.
W przypadku gdy zamiana pionków miejscami nie jest możliwa, należy w jedynym wierszu wyjścia umieścić liczbę -1.

Ograniczenia

1 ≤ X_a, Y_a, X_b, Y_b ≤ 500.

Przykłady

1 1
1 3

4
AG
BD
AG
BD

Bajtockie Mistrzostwa w Piłce Nożnej zbliżają się wielkimi krokami. Jako, że jest to najbardziej wyczekiwane wydarzenie sportowe roku, komitet organizacyjny chce się upewnić, że wszystko jest dopięte na ostatni guzik, a szczególną wagę przykłada do miejsca rozgrywek.

Bajtocja składa się z N miast, połączonych N − 1 drogami tak, że z każdego miasta można dojechać do każdego innego (tzn. bajtockie drogi mają strukturę drzewa). Jeśli Mistrzostwa są rozgrywane w mieście i, z którego wychodzi k dróg, weźmie w nich udział k drużyn: każda grupa miast, z której wjeżdża się do miasta i tą samą drogą, stworzy wspólny zespół. Mieszkańcy miasta i są gospodarzami i nie będą rywalizować w turnieju. Jak wiadomo, w piłce nożnej najważniejsza jest strategia. Każde z miast tworzące wspólną drużynę wyśle po jednym trenerze, którzy razem stworzą sztab opracowujący strategię na mecze. Oczywiście trener trenerowi nierówny, szkoleniowiec z miasta j ma poziom doświadczenia d_j.

Jakość sztabu dana jest wzorem

$$J = \sum_{t = 1}^{\infty} \ t \cdot W_{\mathrm{cnt}_t},$$ gdzie cnt_t oznacza liczbę trenerów w sztabie, których poziom doświadczenia jest wielokrotnością t. Od dawna wiadomo, że współczynnik W₀ = 0, a pozostałe współczynniki W też zostały już wyznaczone przez amerykańskich naukowców na zamówienie komitetu. I całe szczęście, bo współczynnik jakości sztabu jest kluczowy do obliczenia współczynnika jakości Mistrzostw, który jest równy iloczynowi współczynników jakości sztabów wszystkich drużyn, które staną w szrankach. Pomóż zorganizować Mistrzostwa stulecia i oblicz ich poziom, gdyby odbywały się w każdym z miast Bajtocji. Komitet jest świadomy, że nie jest to łatwe, dlatego wystarczy mu wynik modulo 1 000 000 007.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbę naturalną N, oznaczającą liczbę miast w Bajtocji.
Drugi wiersz wejścia składa się z N liczb naturalnych d₁, d₂, …d_n, oznaczających poziomy doświadczenia trenerów mieszkających w poszczególnych miastach.
Trzeci wiersz wejścia zawiera N współczynników W₁, W₂, …W_n.
Kolejne N − 1 wierszy składa z dwóch różnych liczb naturalnych a, b, oznaczających drogę pomiędzy miastami a i b.

Wyjście

Na wyjściu należy wypisać N oddzielonych pojedynczymi spacjami liczb naturalnych, gdzie i-ta z nich powinna oznaczać współczynnik jakości Mistrzostw modulo 1 000 000 007, gdyby te odbyły się w i-tym mieście.

Ograniczenia

2 ≤ N ≤ 100 000, 1 ≤ a, b ≤ N, 1 ≤ d_i ≤ 10⁶, 1 ≤ w_i ≤ 10³.

Przykłady

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

650 7488 208 32 32 228 34 34 

Wyjaśnienie

Razem daje to współczynnik jakości Mistrzostw równy 26 ⋅ 6 ⋅ 8 ⋅ 6 = 7488.

Jeśli Mistrzostwa odbyłyby się w mieście nr 4, wystartowałaby w nich tylko jedna drużyna tworzona przez wszystkie miasta oprócz 4-tego. Wtedy wśród poziomów doświadczenia trenerów mamy 7 wielokrotności 1 (w₇ = 3), 2 wielkrotności 2 (w₂ = 1), 5 wielkrotności 5 (w₅ = 2) oraz po 2 wielokrotności 7 i 10 (w₂ = 1), co daje współczynnik jakości równy 1 ⋅ 3 + 2 ⋅ 1 + 5 ⋅ 2 + 7 ⋅ 1 + 10 ⋅ 1 = 32.

10
13 13 13 7 7 7 7 2 2 2
1 1 2 1 2 2 3 1 2 2
1 2
2 3
3 4
4 5
5 6
6 7
4 8
8 9
9 10

26 350 196 2688 320 304 46 108 108 37 

Ze względu na liczne kontrowersje związane z liczbą minut doliczonych do meczu przez arbitra, Bajtocki Związek Piłki Nożnej postanowił ujednolicić zasadę dotyczącą wyliczania tej wartości.

Po długich debatach, związkowi udało się ostatecznie dojść do porozumienia w związku z wyborem wspólnej reguły. A mianowicie, na liczbę doliczonych minut będzie miało wpływ to, ile fauli popełniono podczas meczu, ile razy piłkarze byli na spalonym, ile razy wykonywali rzuty rożne, liczba interwencji systemu WAR oraz sumaryczna liczba zmian zawodników. Do wszystkich pięciu rodzajów zdarzeń zostanie przydzielona liczba sekund, która powinna zostać doliczona za ich każdorazowe wystąpienie podczas meczu.

Liczba doliczonych minut oczywiście musi być całkowita, dlatego obliczona powyżej sumaryczna liczba sekund musi zostać zaokrąglona w górę do wielokrotności liczby 60.

Czy jesteś w stanie zaimplementować system wspomagający arbitrów w powyższych obliczeniach?

Wejście

W pierwszym wierszu wejścia znajduje się pięć liczb całkowitych a, b, c, d i e, oznaczających kolejno liczbę fauli, spalonych, rzutów rożnych, interwencji WAR-u i wykonanych zmian, które wydarzyły się podczas meczu.
Drugi wiersz wejścia zawiera pięć liczb całkowitych A, B, C, D i E, oznaczających ile sekund powinno zostać doliczone do czasu za każde z tych zdarzeń. Są one wymienione w tej samej kolejności.

Wyjście

Na wyjściu wypisz jedną liczbę całkowitą, oznaczającą liczbę minut, jaką arbiter powinien doliczyć do podstawowego czasu gry.

Ograniczenia

0 ≤ a, b, c, d, e, A, B, C, D, E ≤ 100 000.

Przykłady

3 2 5 2 0
15 25 10 30 17

4

Karol postanowił wykonać w swoim klubie kilka transferów. Jego plan jest taki, żeby wymienić niektórych piłkarzy na takich, którzy są co najmniej tak samo dobrzy. Jednakże przeciwna drużyna nie zgodzi się na piłkarza, który jest zbyt słaby, co sprawia, że decyzja robi się trochę trudniejsza.

Karol ocenia każdego piłkarza w 20 kryteriach (ponumerowanych od 1 do 20). Ocena jest binarna, co oznacza, że każdy piłkarz może albo spełniać dane kryterium, albo nie. Dzięki temu może on zapisać ocenę piłkarza jako liczbę binarną, gdzie bit o wadze 2^k − 1 oznacza, że piłkarz spełnia k-te kryterium. Przykładowo, ocena 13₁₀ = 1101₂ oznacza, że piłkarz spełnia kryteria 1, 3 oraz 4. Uznajemy, że piłkarz a jest lepszy lub równy od piłkarza b wtedy, gdy piłkarz a spełnia każde kryterium, które spełnia piłkarz b. Na przykład, piłkarz z oceną 13 jest lepszy lub równy piłkarzom z ocenami 9, 0 lub 13, ale nie jest lepszy lub równy piłkarzom z ocenami 31, 11 albo 2.

Karol posiada w swojej drużynie N piłkarzy. Dostał on też Q ofert, z których każda jest charakteryzowana przez dwie liczby całkowite a oraz b. Oznaczają one, że działacze danego klubu oferują piłkarza z oceną a, ale nie przyjmą oni w zamian piłkarza, jeśli b będzie od niego lepszy lub równy.

Czy jesteś w stanie dla każdej oferty określić, czy w drużynie Karola jest piłkarz x, taki żeby a był lepszy lub równy x, ale za to b nie był lepszy lub równy x? Jeśli taki piłkarz istnieje, to wskaż go!

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby całkowite N oraz Q, oznaczające kolejno liczbę piłkarzy w drużynie Karola oraz liczbę ofert z innych klubów.
W kolejnych N wierszach znajduje się po jednej liczbie całkowitej – każda z nich oznacza ocenę jednego piłkarza z drużyny Karola.
W kolejnych Q wierszach znajdują się po dwie liczby całkowite a oraz b oznaczające oferty, tak jak zostały one opisane w treści.

Wyjście

Na wyjściu wypisz Q wierszy, a w każdym z nich odpowiedź na jedną ofertę (w tej samej kolejności, w jakiej zostały one podane na wejściu). Jeżeli Karol posiada piłkarza, który spełnia daną ofertę, podaj jego ocenę, a jeśli taki piłkarz nie istnieje, na wyjściu wypisz słowo NIE. Jeżeli wielu piłkarzy spełnia dane kryterium, możesz wypisać dowolnego z nich.

Ograniczenia

1 ≤ N, Q ≤ 1 000 000,
każda inna liczba podana na wejściu jest z przedziału [0,2²⁰−1].

Przykłady

5 5
31
0
7
21
19
31 1
19 31
23 7
15 9
15 7

21
NIE
21
7
NIE

Po kolejnym treningu w upalny dzień, zawodnicy mieli już dość. Z plastronów można było wyciskać pot niczym z gąbki. Zarząd wpadł na genialny pomysł, który miał to zmienić: postanowiono, że zawodnicy, zamiast plastronów będą nosić opaski (po jednej na każdej ręce). Sportowcy są szczęśliwi, bo nie odnoszą już wrażenia, jakby trening odbywał się na basenie. Wyniki zespołu się poprawiły, a zarząd jest wniebowzięty.

Jedynie trener – Karol, nie jest zadowolony ze zmian, ponieważ po każdym treningu, ma do zebrania dwa razy więcej sztuk odzieży porozrzucanej po boisku. Każda z N par opasek ma przypisany numer od 1 do N włącznie. W szatni znajduje się N wieszaków, każdy z dokładnie dwoma haczykami. Na każdym haczyku można zawiesić maksymalnie jedną opaskę. Przed treningiem na i-tym wieszaku wisiały obie opaski z numerem i. Teraz, na części z nich zawodnicy odwiesili już opaski, ale niekoniecznie poprawnie.

Napisz dla Karola program, który policzy, ile maksymalnie wieszaków będzie miało poprawnie przyporządkowane obie opaski, jeżeli optymalnie rozwiesi pozostałe opaski, nie zmieniając miejsca tych już wiszących (pozwoli mu to lepiej określić liczbę pajacyków, jaką będą musieli wykonać zawodnicy przed kolejnym treningiem, jako karę za robienie bałaganu).

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N – liczba wieszaków.
W i-tym z kolejnych N wierszy znajdują się po dwie liczby oddzielone pojedynczym odstępem a_i oraz b_i, oznaczające numery opasek odwieszone na i-tym wieszaku. Jeżeli na którymś haczyku nic nie wisi, to liczba mu odpowiadająca będzie równa 0.
Możesz założyć, że żaden numer opaski nie pojawi się na wejściu więcej niż dwukrotnie.

Wyjście

Twój program powinien wypisać jedną liczbę, oznaczającą liczbę wieszaków, które będą miały poprawnie odwieszone opaski, zakładając że Karol optymalnie rozwiesi opaski nieodwieszone przez zawodników.

Ograniczenia

1 ≤ N ≤ 100 000,
0 ≤ a_i, b_i ≤ N.

Przykłady

5
1 0
2 3
0 0
0 2
5 5

2

Dla Robicika właśnie rozpoczął się nowy sezon. Po zimowym czasie odpoczynku dostał od swojego trenera Karola plany treningowe na najbliższe trzy miesiące.

Aby zbytnio nie przeciążyć młodego zawodnika, w każdym miesiącu (który w Bitocji zawsze ma 2 ⋅ N dni) jest zaplanowanych N treningów oraz N dni odpoczynku. Mimo to Robicik obawia się, że może nabawić się kontuzji. Chciałby zatem, żeby plan na pierwszy miesiąc był subiektywnie nie trudniejszy niż plan na drugi miesiąc, oraz plan na drugi miesiąc był subiektywnie nie trudniejszy niż ten na trzeci miesiąc. Plan A jest dla Robicika subiektywnie nie trudniejszy niż plan B, gdy dla każdego i-tego z 2 ⋅ N dni miesiąca, liczba treningów w pierwszych i dniach planu A jest nie większa niż liczba treningów w pierwszych i dniach planu B.

Aby osiągnąć swój cel, Robicik może zamienić miejscami harmonogram na sąsiednie dni w tym samym miesiącu. Aby nie wzbudzić podejrzliwości trenera Karola, Robicik chce wykonać jak najmniej zmian. Pomóż mu i powiedz, ile minimalnie zamian musi wykonać, aby plan na pierwszy miesiąc był subiektywnie nie trudniejszy niż plan na drugi miesiąc, a plan na drugi miesiąc był subiektywnie nie trudniejszy niż plan na trzeci miesiąc.

Wejście

Pierwszy wiersz wejścia zawiera jedną liczbą N.
Kolejne trzy wiersze opisują po kolei plany na kolejne miesiące. Każdy z tych wierszy zawiera 2 ⋅ N cyfr, spośród których dokładnie N jest cyfrą 0 i dokładnie N jest cyfrą 1. Cyfra 1 na i-tej pozycji oznacza, że trener Karol zaplanował w i-tym dniu miesiąca trening, a 0, że na ten dzień zaplanowany jest odpoczynek.

Wyjście

Twój program powinien wypisać jedną liczbę – minimalną liczbę zmian, których musi dokonać Robicik, aby osiągnąć swój cel.

Ograniczenia

1 ≤ N ≤ 1 000 000.

Przykłady

2
0011
1010
1100

0

2
1001
0110
1010

1

3
100110
011001
100101

3