Mistrzostwa Polski Szkół Średnich w Programowaniu Zespołowym 2023

Old page Regulations Schedule RODO info Ranking

Problem description


Ucieczka z miasta
(ucieczka-z-miasta)
Memory limit: 512 MB
Time limit: 5.00 s

Firma Januszex S.A. otwiera się na transport! Jak powszechnie wiadomo, korki w Nowym Jorku są niestety dość duże. Szczególnie w piątek wieczór, gdy wszyscy chcą wyjechać z miasta. Pan Janusz postanowił pomóc Amerykanom rozwiązać ten problem poprzez inteligentne rozwiązania informatyczne planujące kierowcom ścieżki wyjazdu z miasta.

Jak wiadomo, miasto Nowy Jork (a szczególnie dzielnica Manhattan) jest wyjątkowe – składa się w zasadzie jedynie z pionowych ulic oraz poziomych alei. Wszystkie ulice przecinają się z wszystkimi alejami zawsze pod kątem prostym tworząc ,,kratkę’’. Zakładamy, że wszystkie ulice biegną z północy na południe, a wszystkie aleje z zachodu na wschód.

Pan Ryszard z Januszex S.A. ma następujący, genialny pomysł na rozwiązanie problemu:

  • wpuszczasz parę samochodów na ulicę,
  • i czyścisz kolejkę!
  • a potem wpuszczasz kolejnych kilka żeby wyjechało,
  • i tak dalej aż wszyscy wyjadą.

Prawda, że jest to bajecznie proste? Niestety, sytuacja na mieście jest bardzo dynamiczna. Kierowcy wsiadają do samochodów a czasami widząc ruch na drodze rezygnują z jazdy. Sytuację pogarszają też trwające roboty drogowe, które czasami zaskakują kierowców tym, że się zaczynają (co blokuje przejazd niektórymi skrzyżowaniami) lub kończą (co odblokowuje przejazd).

Oprogramowanie ma umożliwiać szybką reakcję na tego typu zdarzenia i ciągle ma wyznaczać czy jest możliwe wyznaczenie dla każdego samochodu zarejestrowanego w systemie znalezienie jakiejkolwiek niekolizyjnej ścieżki wyjeżdżającej poza obręb miasta, z którejkolwiek strony. Ścieżkę uznajemy za niekolizyjną, gdy nie przebiega przez żadne skrzyżowanie ani żadną drogę, którą jedzie jakikolwiek inny samochód.

Przykładowy Nowy Jork z siedmioma ulicami i czterema alejami. Samochody oznaczone są zaczernionymi kółkami, a przykładowa bezkolizyjna droga wyjazdu z miasta oznaczona pogrubioną łamaną. Blokady drogowe oznaczone są przekreślonymi niezaczernionymi kółkami.

Napisz program, który: wczyta opis miasta i opis występujących zdarzeń na drodze, po każdym zdarzeniu wyznaczy czy jest możliwy bezkolizyjny wyjazd wszystkich pojazdów z miasta i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajdują się trzy liczby naturalne N, M oraz Q pooddzielane pojedynczymi odstępami i określające kolejno: liczbę ulic, liczbę alei oraz liczbę zapytań.

W kolejnych Q wierszach znajdują się kolejne zapytania. Każde zapytanie jest w osobnym wierszu i jest jednej z następujących postaci:

  • S+, pojedynczy odstęp i dwie liczby x oraz y oddzielone pojedynczym odstępem – określające pojawienie się samochodu na skrzyżowaniu x-tej ulicy oraz y-tej alei,
  • S-, pojedynczy odstęp i dwie liczby x oraz y oddzielone pojedynczym odstępem – określające zniknięcie samochodu na skrzyżowaniu x-tej ulicy oraz y-tej alei,
  • B+, pojedynczy odstęp i dwie liczby x oraz y oddzielone pojedynczym odstępem – określające pojawienie się blokady drogowej na skrzyżowaniu x-tej ulicy oraz y-tej alei,
  • B-, pojedynczy odstęp i dwie liczby x oraz y oddzielone pojedynczym odstępem – określające zniknięcie blokady drogowej na skrzyżowaniu x-tej ulicy oraz y-tej alei.

Ulice numerowane są kolejnymi liczbami naturalnymi od 1 do N włącznie. Aleje numerowane są kolejnymi liczbami naturalnymi od 1 do M włącznie.

Możesz założyć, że ciąg operacji na wejściu jest sensowny – tzn. nigdy nie pojawi się operacja S+ w miejscu, gdzie znajduje się już pojazd lub blokada drogowa, nigdy nie pojawi się operacja S- w miejscu, gdzie pojazdu nie ma, nigdy nie pojawi się operacja B+ w miejscu, gdzie znajduje się już blokada drogowa lub pojazd, a także nigdy nie pojawi się operacja B- w miejscu, gdzie nie ma blokady drogowej. Możesz założyć, że początkowa sytuacja w mieście jest taka, że nie ma żadnych robót drogowych ani żadnych samochodów. Dodatkowo, gwarantowane jest, że po każdej operacji, w mieście jest co najmniej jeden samochód.

Wyjście

Twój program powinien wypisać na wyjście dokładnie Q wierszy. W i-tym z nich powinna się znaleźć odpowiedź TAK, jeśli możliwe jest zapewnienie bezkolizyjnego wyjazdu z miasta wszystkim pojazdom oraz NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ N, M ≤ 40, 1 ≤ Q ≤ 5 000.

Przykład

Input Output
3 3 12
S+ 1 2
S+ 2 1
S+ 2 3
S+ 3 2
S+ 2 2
B+ 3 3
B+ 3 1
S- 3 2
B+ 3 2
S- 1 2
B- 3 2
B+ 1 2
TAK
TAK
TAK
TAK
NIE
NIE
NIE
TAK
NIE
TAK
TAK
TAK