Contest problemset description

Klatka, ciemność, strach, a w końcu światełko w tunelu i wyjście na świat; chociaż w zasadzie to na nowy wybieg. Szeregowy wychodząc z klatki do swojego nowego domu, bał się i zastanawiał czy nowe pingwiny będą dla niego miłe.

Trzęsą mi się kolana – ciekawy objaw połączenia niepokoju i niepewności, myślał sobie Kowalski, wychodząc na pokład Central Park Zoo. Chociaż czy pingwiny rzeczywiście mają kolana? Intrygujące.

Ricooo.

Skipper dokładnie analizował każdy szczegół otaczającego go świata, w końcu nic nie mogło go zaskoczyć; a więc to tak prezentuje się mój nowy oddział.

– Witajcie panowie na naszym nowym polu bitwy! – zarzucił ptak o lekko spłaszczonej głowie – Czy któryś z was ma jakieś propozycje, co powinniśmy robić?

– Zapoznać się? – nieśmiało powiedział uroczy i gruszkokształtny pingwin.

– Odmawiam – odpowiedział mu pingwin o ewidentnych zdolnościach przywódczych – Jajogłowy, ty tu wyglądasz na rozgarniętego; jakie mamy opcje?

– Yyy, jestem Kowalski, no pewnie wypadałoby poszukać jakiegoś schronienia – odpowiedział Kowalski. – Tylko że nie mamy żadnych narzędzi.

Wszystkie pingwiny odwróciły się w stronę odgłosu żelastwa upadającego na ziemię. Przed tym o szalonym spojrzeniu pojawiła się właśnie sterta ciężkich narzędzi. Skipper nie wchodził w szczegóły, a Kowalski był gotowy do zadania mnóstwa pytań, Szeregowy w sumie nie do końca wiedział, co się dzieje.

– Panowie, zbudujemy prostokątną bazę o obwodzie D. Chciałbym, aby jej pole powierzchni było jak największe. Kowalski podaj mi odpowiednie dla niej wymiary – powiedział znacząco Skipper.

Kowalski od razu podał Skipperowi wymiary prostokątnej bazy, dla których powinna ona mieć największe pole powierzchni. Niestety Skipper nie ufał jeszcze głowie jajogłowego i chciałby zweryfikować czy podane przez niego wymiary rzeczywiście maksymalizują powierzchnię przyszłej bazy. Twoim zadaniem będzie więc pomóc Skipperowi i napisać program, który wczyta obwód D przyszłej bazy i wyznaczy wymiary, dla których jej pole powierzchni będzie maksymalne.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba naturalna D, oznaczająca obwód bazy pingwinów.

Wyjście

W pierwszym wierszu wyjścia powinny znaleźć się dwie liczby naturalne, oddzielone pojedynczym odstępem i oznaczające wymiary bazy, której obwód będzie wynosił D, a pole powierzchni będzie maksymalne. Jeśli odpowiedź nie istnieje, na wyjście należy wypisać tylko słowo NIE. Jeśli istnieje wiele poprawnych odpowiedzi, wypisz tą, w której pierwsza liczba będzie możliwie najmniejsza.

Ograniczenia

1 ≤ D ≤ 10¹⁸.

Przykład

10

2 3

9

NIE

2

NIE

Bunkier to to nie jest, ale też jest zaczepisty!

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

Podczas budowy tajnej pingwiniej bazy doszło do pewnego incydentu …

Z żołądka Rico, w nieznanych nikomu okolicznościach, na świat wydostała się bomba; na domiar złego bomba była odpalona. Jak można się domyślić, wskutek tego wydarzenia doszło do eksplozji. Kaboom. Wybuch doprowadził do rozszczelnienia się basenu otaczającego wybieg pingwinów, przez co codziennie ulatuje z niego K litrów wody.

Oczywiście, jeśli ze zbiornika ucieknie zbyt dużo wody, to władze Zoo zainteresują się tym incydentem, a tym bardziej zainteresują się faktem powstania tajnej bazy pod wybiegiem pingwinów, do czego, jak wiadomo, dopuścić nie można (na podstawie odcinka “Ostrożnie z życzeniami”). Dlatego też nieloty podjęły działania zapobiegawcze i za N + 1 dni zaplanowały wyprawę po materiały, które pozwolą na załatanie wycieku.

Niestety przez najbliższe N dni do basenu codziennie należy dolewać trochę wody, tak by jej poziom nie spadł poniżej A litrów, oraz nie przekroczył B litrów. Dokładnie każdego z N dni najpierw pingwiny dolewają X_i litrów wody, następnie z basenu wycieka K litrów wody, a następnie Alice robi obchód i sprawdza poziom wody na wybiegu pingwinów; jeśli wody będzie zbyt mało lub zbyt dużo, to oznacza to tarapaty dla pingwinów.

Pingwiny zastanawiają się teraz, ile wody należy nalać do basenu na początku, aby do tarapatów nie doszło. Twoim zadaniem będzie im pomóc i napisać program, który stwierdzi czy istnieje takie początkowe napełnienie basenu, że jeśli pingwiny będą codziennie dolewały wodę zgodnie z planem, to każdego dnia będzie ona w odpowiednim przedziale.

Uwaga: z basenu nie może wyciec więcej wody, niż w nim jest, przykładowo, jeśli w basenie znajduje się 5 litrów wody, a wyciec z niego ma 6 litrów, to po wycieku w basenie znajdować się będzie 0 litrów wody.

Wejście

W pierwszym wierszu wejścia znajdują się cztery liczby naturalne N, K, A i B, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio liczbę dni, przez które do basenu będzie dolewana woda, liczbę litrów wody, która będzie codziennie wyciekać z basenu, minimalną liczbę litrów oraz maksymalną liczbę litrów wody dopuszczalną przez Alice w basenie. W drugim i ostatnim wierszu wejścia znajduje się ciąg N liczb naturalnych X_i, pooddzielanych pojedynczymi odstępami i oznaczających liczbę litrów wody, która dolewana będzie w kolejnych dniach do basenu.

Wyjście

W pierwszym wierszu wyjścia powinna znaleźć się jedna liczba naturalna – maksymalny początkowy stan napełnienia basenu, dla którego stan wody nie spadnie poniżej A litrów, oraz nie przekroczy B litrów wody. Jeśli poszukiwany stan napełnienia wody nie istnieje, zamiast tego należy wypisać słowo NIE.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ K, X_i ≤ 10⁹, 0 ≤ A ≤ B ≤ 10⁹.

Przykład

7 2 2 5
3 3 1 3 4 0 1

1

4 3 7 9
3 5 4 0

NIE

7 4 0 4
2 3 3 5 2 8 1

5

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

– Jadę ulicą, opony asfalt drą, pingwiny jak zobaczą drzewo, na zawał umerą. Hej! Julian, Julian, on twardy jest jak głaz. – radośnie śpiewał sobie Król Julian, jadąc ciężarówką, na którą załadowane było zwędzone świąteczne drzewo.

– Jedziemy panie ciut za wolno, trzeba wcisnąć gaz – donucił melodyjnie piszczącym głosem Mort.

– Gonią nas z dużą prędkością.

– O poważnie, to wcisnę sprzęgło.

– Panowie, lemury zbliżają się do nas ze zbyt dużą prędkością, a do tego wiozą jakieś nie najgorszej jakości drzewo – zarzucił Skipper. – Nie możemy być gorsi; Kowalski opcje!

– No wie szef, można byłoby wysadzić Lemury – opowiedział Kowalski, na co Rico entuzjastycznie wypluł laskę dynamitu.

– Rico, Kowalski ma na myśli wysadzenie Choinki Lemurów, a nie Lemurów. Prawda Kowalski? – zareagował z oburzeniem Szeregowy.

– Yyy, tak, to miałem na myśli, oczywiście – Wychrząkał Kowalski. – Możemy też zrobić własne drzewo.

– Uuu to mi się podoba Kowalski. Rico piła! A Ty Kowalski powiedz jak zrobić, żeby drzewo było piękne.

No więc szefie. Drzewo jest grafem spójnym, ma N wierzchołków, ponumerowanych kolejnymi liczbami naturalnymi od 1 do N i N − 1 krawędzi je łączących. Moim zdaniem drzewo, podające się za choinkę, jest najpiękniejsze, gdy odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami jest minimalna. Powinniśmy pozbyć się jednej krawędzi i dołożyć jedną tak, by było możliwie najładniejsze (i oczywiście dalej było poprawnym drzewem).

No i tutaj pojawił się problem, bo Pingwiny nie wiedzą, jak piękne może być drzewo po ich poprawce. Twoim zadaniem będzie napisanie programu, który wyznaczy minimalną odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami, jaką można uzyskać po usunięciu jednej krawędzi z oryginalnego drzewa i dodaniu nowej.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N. W kolejnych N − 1 wierszach znajdują się po dwie liczby naturalne X_i i Y_i, oddzielone pojedynczym odstępem i oznaczające krawędź pomiędzy wierzchołkami o numerach X_i i Y_i.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna odległość pomiędzy dwoma najbardziej odległymi od siebie wierzchołkami, jaką można uzyskać po usunięciu jednej krawędzi z oryginalnego drzewa i dodaniu nowej.

Ograniczenia

1 ≤ N ≤ 300 000, 1 ≤ X_i, Y_i ≤ N.

Przykład

5
1 2
2 3
3 4
4 5

3

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

3

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

– Lemurze podły. Wytłumacz swoją tu obecność! – krzyknął Skipper do Juliana – Kowalski, raport taktyczny! Jak pozbyć się tych wstrętnych lemurów?

Julian bez ogródek wszedł do pingwiniej bazy i zaczął się panoszyć. Wyciągnął już paczkę chrupek z Rico i rozsiadł się wygodnie przed telewizorem.

– Moris podnóżek! – powiedział Julian, po czym do bazy wszedł Moris, ulokował podnóżek w postaci Morta pod nogami Króla i zaczął go wachlować.

– Ssaki gadowe opuśćcie tę bazę już!

– Nie umiecie się dzielić? To się nauczcie. Moris podaj mi tę poduszkę.

– Nie udawaj głupiego, Ogoniasty!

– A jeśli nie udaję?

– Won! Precz!

Nie ma co owijać w bawełnę, że bezduszne lemury znęcają się bezdusznie nad biednymi pingwinami. Pingwiny postanowiły więc zrobić coś z tym faktem i dookoła swojej bazy zainstalować anty-ssakowo-przeciw-lemurowe zabezpieczenie. Takie zabezpieczenie składa się z N ustawionych w rzędzie i ponumerowanych kolejnymi liczbami naturalnymi od 1 do N ultradźwiękowych nadajników. Nadajnik o numerze i ma moc o wartości A_i. Dodatkowo moce nadajników są parami różne. Wydajność całego zabezpieczenia określa się jako sumę N − 1 wartości bezwzględnych różnic nadajników ustawionych przy sobie:

$$\sum^{N-1}_{i=1} |A_{i+1} - A_{i}|$$

Pingwiny zdobyły już wszystkie nadajniki. Muszą je jeszcze ustawić w odpowiedniej kolejności, która zmaksymalizuje wydajność zabezpieczenia. Sytuacja jednak nie jest taka prosta, ponieważ o tym, czy zabezpieczenie działa poprawnie, decyduje to, który z każdej pary sąsiednich nadajników ma większą moc. Dokładnie określone jest to w następujący sposób: i-ty nadajnik ma mieć mniejszą moc niż i + 1-wszy, gdy parametr zabezpieczenia B_i jest równy 1, a większą, gdy parametr zabezpieczenia B_i jest równy 0.

Twoim zdaniem jest pomóc pingwinom i napisać program, który na podstawie mocy poszczególnych nadajników oraz parametrów zabezpieczenia wyznaczy jego maksymalną wydajność, możliwą do uzyskania.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę nadajników. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i, pooddzielanych pojedynczymi odstępami i oznaczających moce poszczególnych nadajników ultradźwiękowych. W trzecim wierszu wejścia znajduje się ciąg N − 1 liczb naturalnych B_i, pooddzielanych pojedynczymi odstępami i oznaczających kolejne parametry zabezpieczenia.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – maksymalna wydajność zabezpieczenia, możliwa do uzyskania.

Ograniczenia

1 ≤ N ≤ 300 000, 1 ≤ A_i ≤ 10⁹, 0 ≤ B_i ≤ 1.

Przykład

4
1 2 3 4
1 0 1

7

10
5 10 20 8 30 100 7 1 4 42
0 0 1 1 1 0 1 1 0

299

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

Ach lemury, lemury, lemury, znowu oszukują i znęcają się nad biednymi pingwinami; tym razem robią to, poruszając się po koronach drzew, deklasując przy tym pingwiny w grze polowej, ale jak to na świecie bywa, każda bajka musi się kończyć happy-endem, a pingwiny muszą ostatecznie górować nad ssakami.

– Nie jest tajemnicą, że lemury mnie nic nie obchodzą – groźnie powiedział Skipper.

– Nawzajem, gburze we fraku! – odburknął Julian.

W celu zdeklasowania lemurów w grze polowej nasze nieloty poczuły chęć latania. I tak wyposażywszy się w jetpacki napędzane Polococtą i Mentosami wzbiły się w powietrze. Jednak zanim lemury zostaną rozłożone na łopatki, pingwiny muszą poważnie potrenować, bo jak wiadomo, trening czyni mistrza.

Pingwiny będą trenować w pobliskim parku na N ustawionych w rzędzie drzewach, ponumerowanych kolejnymi liczbami od 1 do N. Drzewo o numerze i ma wysokość H_i. Aby nie marnować cennego Polocotowego napędu, pingwiny postanowiły, że na razie będą tylko szybować, czyli zlatywać z korony wyższego drzewa na koronę niższego drzewa. I tak pingwiny mogą zszybować z drzewa o numerze x na drzewo o numerze y, gdy drzewo o numerze x jest wyższe oraz pomiędzy drzewami o numerach x i y wszystkie drzewa są niższe od drzewa o numerze x. Formalnie z drzewa o numerze x można zszybować do drzewa o numerze y, gdy H_y < H_x oraz H_i < H_x dla każdego i spełniającego min(x,y) < i < max(x,y).

Pingwiny chciałby oczywiście, aby po wspięciu się na określone drzewo “lot” trwał jak najdłużej dlatego, dla każdego ze swoich planów treningowych, chciałyby poznać maksymalną liczbę zszybowań. Plany treningowe pingwinów mają dwa różne typy:

• 1 X_i Y_i – pingwiny chcą wykonać możliwie wiele szybowań, by dostać się z drzewa o numerze X_i do drzewa o numerze Y_i lub z drzewa o numerze Y_i do drzewa o numerze X_i;

• 2 X_i – pingwiny chcą wykonać możliwie wiele szybowań, zaczynając z drzewa o numerze x.

Twoim zadaniem będzie napisanie programu, który na podstawie kolejnych wysokości drzew w parku dla każdego planu treningowego wyznaczy maksymalną liczbę szybowań.

Wejście

W pierwszym wierszu wejścia znajdują się dwie liczby naturalne N i Q, oznaczające liczbę drzew oraz liczbę planów treningowych pingwinów. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych H_i pooddzielanych pojedynczymi odstępami i oznaczającymi wysokości kolejnych drzew w parku. W kolejnych Q wierszach znajdują się opisy planów treningowych, zgodne z formatem podanym w treści zadania.

Wyjście

Na wyjście należy wypisać dokładnie Q wierszy, w i-tym z nich powinna znaleźć się odpowiedź na i-te zapytanie. Jeśli wykonanie i-tego planu treningowego nie jest możliwe, to w i-tym wierszu wyjścia należy wypisać liczbę 0.

Ograniczenia

1 ≤ N, Q ≤ 100 000, 1 ≤ H_i, X_i, Y_i ≤ N.

Przykład

12 8
1 4 6 6 6 4 4 4 2 3 8 6
2 3
2 4 
1 7 11
1 7 9
2 5
1 1 11
2 7
1 9 12

2
0
2
0
3
3
0
0

Niestety fabryka Polococty została już wysadzona.

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

Zoo ostatnio otworzyło nową atrakcję, która ma na celu zwabić małe ludzkie pociechy. Tą atrakcją jest oczywiście Małe Zoo, którego mieszkańcami są zwierzęta typowo wiejskie. Jednym z tych mieszkańców jest pewna kwoka, która śmie twierdzić, że jest mądrzejsza od pingwinów (i to nawet od Kowalskiego)! Problem jest niestety taki, że kilka razy udało jej się zagiąć pingwiny, w szczególności oznacza to więc, że przeciwnik jest dużo poważniejszy od niezbyt rozgarniętych lemurów.

No i tutaj pojawił się plan kontrataku. Postanowiły one zaznaczyć totalną dominację, deklasację i pokazać kurze gdzie pieprz yyy ro, gdzie raki zimują! Chcą wymyślić, coś tak ambitnego, że kapcie jej spadną, chcą pokazać, że nawet Rico będzie w stanie pokonać ją w jakiejś grze logicznej.

Niestety plan pokazania tego, że kura w przysłowiach niedaleko pada od jeża, może nie być najprostszy. W końcu, jaki Rico jest, każdy wie. Pingwiny postanowiły zatem pomóc szczęściu, tak by wygrał lepszy. Zaplanowały, że ułożą zagadkę z zapałek, mające postać prostego wyrażenia. Zagadka ma polegać na przestawieniu jednej zapałki w taki sposób, żeby po przestawieniu wyrażenie stało się poprawne. Pingwiny ustaliły już, że poszczególne znaki z zapałek będą formowane w następujący sposób.

Zagadka będzie miała postać wyrażenia złożonego z dwóch liczb jednocyfrowych zestawionych znakiem + lub -, przyrównanego do liczby jednocyfrowej. Przykładowo zagadkę 6+7=9, możemy rozwiązać, przestawiając zapałkę z liczby 7 do liczby 6 i uzyskując ostatecznie 8+1=9.

Twoim zadaniem będzie dopomóc szczęściu Rico i pokazać kwoce gdzie jej miejsce; musisz napisać program, który wczyta zagadkę i wyznaczy dowolne jej rozwiązanie.

Uwaga: znak + możemy zamienić na znak - zabierając jedną zapałkę, a znak - na znak + dokładając jedną zapałkę. Znaku równości, nie można zamienić na żaden inny.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się napis złożony z cyfr i znaków -, + oraz =. Pierwsza, trzecia i piąta pozycja napisu zawiera cyfry, druga pozycja napisu zawiera znak - lub +, a czwarta pozycja napisu zawsze zawiera znak =.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinno znaleźć się rozwiązanie zagadki, zgodne z formatem opisanym w treści zadania i przekładające dokładnie jedną zapałkę lub słowo NIE jeśli rozwiązanie zagadki nie istnieje.

Przykład

6+7=9

8+1=9

4-0=9

NIE

1-1=0

1-1=0

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

– Powiem to bardzo powoli, bo widzę, że cierpisz na ciężki przypadek półgłówstwa – powiedziała Julianowi Darla.

– Moris! Skąd ona ma dostęp do moich wyników badań? – spytał Morisa Julian – Jak mogę Ci udowodnić Darlo, że jednak nie jestem półgłówkiem?

– No dobrze, jeśli rozwiążesz prostą zagadkę logiczną, to uznam, że cierpisz jednak tylko na ćwierćgłówstwo.

– Stoi zatem! Król może cierpieć na szlachetne ćwierćgłówstwo!

– Błagam, musicie, musicie mi pomóc – skruszonym głosem Julian żebrał o pomoc.

– A co my niby będziemy z tego mieli, Ogoniasty? – odpowiedział drwiąco Skipper.

– Wdzięczność Króla.

– No więc widzisz Ogoniasty, po nic jest nam Twoja wdzięczność, a do tego Pingwini Honor zabrania pomagania lemurom w biedzie.

– Ale szefie, dobrze jest pomagać potrzebującym – wtrącił się Szeregowy. – A może Julian złoży nam przysięgę, że już nigdy, ale to nigdy, nie wejdzie do naszej bazy nieproszony.

– A wiesz co Szeregowy, całkiem podoba mi się ten pomysł!

Julian został nazwany półgłówkiem (być może słusznie, być może nie słusznie, to już musicie ocenić sami). Są jednak plusy tego zjawiska. Dostał on do rozwiązania prostą zagadkę logiczną, którą jeśli rozwiąże, to pingwiny będą miały upragniony święty spokój, a Król Julian XIII zostanie Królem Julianem XIII Ćwierćgłówkiem. Jako że Pingwini Honor nie pozwala pomagać lemurom, Julianowi będziesz musiał pomóc Ty.

Darla narysowała na murze N niebieskich kropek w rzędzie, ponumerowanych kolejnymi liczbami naturalnymi od 1 do N, następnie kazała Julianowi dorysować minimalną liczbę żółtych kropek w tym samym rzędzie, tak by każda niebieska kropka była w odległości nie większej niż 5 stóp od dowolnej żółtej kropki.

Twoim zadaniem będzie napisanie programu, który pomoże Julianowi (a tak naprawdę pingwinom pozbyć się Juliana) wyznaczyć minimalną liczbę żółtych kropek, które musi dorysować.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N oznaczająca liczbę niebieskich kropek narysowanych na murze. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych A_i pooddzielanych pojedynczymi odstępami i oznaczających odległości kolejnych kropek w rzędzie od początku muru.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna – minimalna liczba żółtych kropek, które musi dorysować Julian.

Ograniczenia

1 ≤ N ≤ 100 000, 0 ≤ A_i ≤ 10⁹, A_i ≤ A_i + 1.

Przykład

5
1 2 6 95 105

2

6
5 10 15 30 40 50

3

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

– Gdybym tylko wzmocnił fale swego mózgu z supergenialnych do supermegagenialnych! – zachwycał się Kowalski.

– Ja myślałem, że twoje fale mózgowe są już pod niebo! – odpowiedział Szeregowy.

– I myślałeś, że w lodówce mieszka ludzik, co włącza i gasi światło.

– Kiedyś go dopadnę!

Marcel wie, że w lodówce nie mieszka, żaden ludzik co zapala i gasi światło, no ale Marcel nie jest pingwinem, tylko człowiekiem co jeździ swoim Nissanem 370Z. Na dodatek Marcel jest Informatykiem, który w antycznych czasach buraków i górek, zdobył finał OI. O tym, że nasz bohater jest całkiem biegły w te klocki może zaświadczyć jego sposób implementacji algorytmu Union-Find:

int p[SIZE];
int counter = 0;

int Find(int u){
    counter++;
    return p[u] == u ? p[u] : p[u] = Find(p[u]);
}
void Union(int x, int y){
    p[Find(x)] = Find(y);
}
void Init(int n){
    for (int i = 0; i <= n; i++)
        p[i] = i;
}

No ale może szkoda rzucać bezwartościowe słowa na wiatr. Czas zająć się właściwą treścią zadania. Marcel zawsze bał się potworków. Oczywiście nie takich co mają futerko, groźne kły i ostre jak brzytwa pazury. Marcel boi się straszliwych problemów informatyczno-algorytmicznych. Przykładowo przez wiele lat swojego życia próbował dowiedzieć się, dlaczego powyższa implementacja algorytmu Union-Find działa w 𝒪(N log N). Niestety Marcel nie jest burakiem i ten problem zwyczajnie go przerósł. Zagadka ta była jednak na tyle nurtująca, że postanowił zrobić absolutnie wszystko, by tylko poznać odpowiedź na nią. Pomyślał sobie, kto może znać rozwiązanie nurtującego go problemu i przypomniał sobie o największym geniuszu, jaki stąpał po tej Ziemii – Kowalskim. Już po chwili, za swoje ciężko zarobione pieniądze z organizacji konkursów informatycznych, kupił bilet do Stanów Zjednoczonych. W Central Park Zoo spotkało go jednak rozczarowanie. Pingwiny wcale nie były zbyt rozgarnięte i nawet pomimo dokładnych tłumaczeń zdawały się wcale nie rozumieć problemu Marcela.

Marcel porzucił już wszelkie nadzieje. Uwierzył, że powyższa implementacja algorytmu Union-Find działa w 𝒪(1) i nic nie jest w stanie go przekonać, że jest inaczej (warto tutaj zaznaczyć, że Marcel nie wierzy w jakieś odwrotne funkcje Ackermanna). Chyba że ktoś poda mu twardy dowód na to, że jednak istnieje przypadek, w którym powyższa implementacja algorytmu Union-Find wykonuje 𝒪(N log N) operacji.

Twoim zadaniem będzie więc napisanie programu, który ułoży test zdolny przekonać Marcela do tego, że jego implementacja działa jednak w czasie 𝒪(N log N).

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się jedna liczba naturalna M, oznaczająca liczbę wywołań funkcji Find, którą należy osiągnąć.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba naturalna Q oznaczająca liczbę operacji do wykonania, w kolejnych Q wierszach powinny się znaleźć opisy operacji w postaci słowa Union, pojedynczego odstępu i dwóch liczb X_i, Y_i, oddzielonych pojedynczym odstępem i odpowiadających argumentom wywołania funkcji Union lub w postaci słowa Find, pojedynczego odstępu i liczby X_i odpowiadającej argumentowi wywołania funkcji Find.

Ograniczenia

1 ≤ Q, X_i, Y_i ≤ 1 000 000.

Ocenianie

W tym zadaniu są tylko dwa testy, przykładowy i główny. W teście przykładowym M = 10, można za ten test otrzymać 0 punktów. W drugim właściwym teście M = 10 000 000, można za niego otrzymać wszystkie punkt za to zadanie.

Przykład

10

7
Union 1 2
Union 2 3
Union 3 4
Find 1
Union 6 5
Union 5 4
Find 6

Autor zadania uspokaja i na podstawie wykonanych testów twierdzi, że powyższa implementacja jest praktycznie nierozróżnialna czasowo od tej, która dodatkowo używa optymalizacji mniejszy do większego. Przynajmniej na zawodach programistycznych.

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

– Kowalski! – piszczał Szeregowy.

– Kowalski! Co wyście zrobili?! – krzyczał Skipper. – Nawet nie zapytam was o opcje, bo nie chcę ich znać.

Zastanawiacie się, co takiego zrobił Kowalski? Odpowiedź jest prosta, stworzył prawdziwe monstrum żywiące się bitą śmietaną. Stworzył Żelusia. Problemu by nie było, gdyby nie to, że Żeluś przy każdym solidnym dostarczeniu energii się podwaja. No właśnie podwaja, jako programista powinieneś doskonale rozumieć, co to oznacza. Apokalipsa ma wykładniczy postęp, a świat skończy się za logarytmicznie wiele czasu.

Pingwiny już pogodziły się z tym, że nie uda im się wyjść cało z tej przygody. Co z tego, że w przyspieszonym procesie za winnego uznany został Kowalski, skoro kreatura pochłonie już za moment całe Zoo, a chwilę potem i cały świat. Można się tylko schować w miejscu Zoo, które zostanie najpóźniej przejęte, może akurat Kowalski wymyśli w tym czasie jakieś sensowne opcje (byle nie kontrpotwora, który zje Żelusia).

Zoo ma kształt prostokątnego placu o wymiarach N × M metrów i może w oczywisty sposób zostać podzielone na N ⋅ M kawałków jednostkowych. Kawałek jednostkowy może być jednoznacznie wyznaczony przez podanie jego współrzędnych X i Y, zgodnie z układem kartezjańskim. Jeśli w kawałku jednostkowym o współrzędnych X i Y znajduje się aktualnie przedstawiciel gatunku Żeluś, to w następnej jednostce czasu, w jednym z sąsiednich pól również będzie znajdował się przedstawiciel gatunku Żeluś (jeśli już się tam znajduje, to nic się nie dzieje, wynika to z miękkości Żelusia). Kowalskiemu udało się nawet zauważyć, że to, w jaką stronę przedstawiciele Żelusia “rozdwoją” w danej jednostce czasu zależy od jego kodu DNA, który Kowalskiemu jest dobrze znany. Jako że Żeluś jest tworem sztucznym, to jego DNA składa się z literek “G”, “D”, “L” i “P”.

Kowalski wyznaczył już nawet jaka literka DNA będzie odpowiadała za zachowanie się Żelusia w następnych Q jednostkach czasu. Ustalił również, jak poszczególne literki genotypu przekładają się na kierunek rozdwajania się Żelusia:

• “G” – Żeluś rozdwaja się w górę, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X i Y + 1,
• “D” – Żeluś rozdwaja się w dół, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X i Y − 1,
• “L” – Żeluś rozdwaja się w lewo, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X − 1 i Y,
• “P” – Żeluś rozdwaja się w prawo, to jest z kawałka jednostkowego o współrzędnych X i Y na kawałek jednostkowy o współrzędnych X + 1 i Y.

Twoim zadaniem będzie pomóc Pingwinom i napisać program, który na podstawie aktualnych pozycji Żelusia, wypisze czas, po jakim Żeluś przejmie całe Zoo oraz mapę Zoo z zaznaczonymi kawałkami jednostkowymi, które zajęte będą najpóźniej.

Uwaga: dla uproszczenia zakładamy, że świat poza Zoo nie istnieje, a przedstawiciele gatunku Żeluś wychodzący poza Zoo znikają. Możesz założyć, że Q jednostek czasu wystarczy Żelusiowi na pochłonięcie całego Zoo.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M i Q, pooddzielane pojedynczymi odstępami i oznaczające odpowiednio wymiary planszy oraz liczbę jednostek czasu, dla których Kowalski wyznaczył kierunek rozdwajania się Żelusiów.

W drugim wierszu znajduje się ciąg Q znaków, złożony z liter “G”, “D”, “L” i “P” i oznaczających kierunki rozdwajania się Żelusia w kolejnych jednostkach czasu.

W każdym z kolejnych N wierszy znajduje sią ciąg M znaków określających, w których kawałkach jednostkowych aktualnie znajduje się Żeluś, “#” odpowiada kawałkowi jednostkowemu, w którym znajduje się aktualnie przedstawiciel gatunku Żeluś, a “.” pusty kawałek jednostkowy.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna liczba całkowita – liczba jednostek czasu, w których będzie istniał przynajmniej jeden kawałek jednostkowy niezajęty przez Żelusia. W każdym z kolejnych N wierszy należy wypisać ciąg M znaków “.” i “#”, reprezentujących Zoo, z zaznaczonymi kawałkami jednostkowymi, które zostaną zajęte jako ostatnie; kawałki jednostkowe, które zostaną zajęte jako ostatnie, powinny być oznaczone znakiem “.”, a pozostałe znakiem “#”.

Ograniczenia

1 ≤ N, M ≤ 1000, 1 ≤ Q ≤ 10 000.

Przykład

5 4 16
GLDPGLDPGLDPLLPP
....
.#..
....
.#..
....

8
###.
###.
###.
###.
###.

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.

Ach nadchodzi, nadchodzi właśnie nasza pyszna rybka. Pingwiny czuły już jej zapach, a woń smakowitego dorsza rozpieszczała żołądki. Pingwiny czuły już ten niesamowity smak rozpływającego się w dziobach śledzia. Po prostu wszystkie znaki na niebie i ziemi wskazywały, że Alice będzie tu już za chwilkę i dostarczy pingwinom masę smakołyków.

– No i co to ma być? – powiedział ze sporym oburzeniem w głosie Skipper.

– Jedna ryba szefie – odparł Kowalski, na co Rico zabulgotał z rozpaczy.

– Ale jak my się tym mamy niby najeść szefie? – zapytał smutny Szeregowy.

– Nie Panowie, nie damy się głodzić! Ogłaszam operację Fokstrot, Tango!

Operacja Fokstrot, Tango zaczęła się; pingwini oddział doślizgał się do automatu z najbardziej uniwersalną walutą na świecie – chrupkami serowo-rybnymi.

Praca się zwraca! Już po chwili obserwacji Pingwiny zobaczyły w jaki sposób dostawca chrupek serowo-rybnych uzupełnia zapasy. Żeby otworzyć automat bez żadnych kołaczy, wystarczy odpowiednio przepisać wyświetlający się na monitorze kod, należy jednak odwrócić przy tym wszystkie samogłoski. Przykładowo, gdyby kodem wyświetlającym się na monitorze był napis: lemurysaniefajne, to kodem otwierającym automat byłby napis: lemaresinayfujne.

Twoim zadaniem jest ocalenie Pingwinów przed zagłodzeniem jednorybnym i napisanie programu, który wczyta kod wyświetlany na monitorze i wypisze kod z odwróconymi samogłoskami.

Wejście

W pierwszym i jedynym wierszu wejścia znajduje się napis S złożony z małych liter alfabetu łacińskiego.

Wyjście

W pierwszym i jedynym wierszu wyjścia powinien znaleźć się napis powstały poprzez odwrócenie samogłosek w słowie S.

Ograniczenia

1 ≤ |S| ≤ 100 000.

Przykład

lemurysaniefajne

lemaresinayfujne

Dla przypomnienia lista samogłosek: ‘a’, ‘e’, ‘i’, ‘o’, ‘u’ i ‘y’. Tak, żebyś nie musiał sprawdzać szemranych stronek internetowych w ich poszukiwaniu (samogloski pl).

Niezbędny przypis: postacie z treści pochodzą z serialu “Pingwiny z Madagaskaru”.