Promocja

Limit pamięci: 64MB

Może nie powinienem tego mówić, ale to zadanie jest o świecie totalitarnym, świecie pełnej kontroli nad jednostką i społeczeństwem, świecie przypominającym ten Orwella czy Zajdla. Żyje w nim nasz bohater, którego imię tutaj, dla jego bezpieczeństwa, przemilczę.

W tym zadaniu zajmiemy się problemem związanym ze znaniem przez Komputer Główny dokładnej lokalizacji każdego obywatela. Partia, aby pokazać swą ``wspaniałomyślność'', jak też przekonać obywateli do niezbędności i przydatności tej wiedzy, postanowiła wprowadzić Promocję na przejazd ulicami, w zależności od tego, którą jest z kolei.

Prawdopodobnie jeszcze nie wspomniałem, ale czynnikiem, który miał stabilizować równość w społeczeńtwie, miały być punkty za przejazd ulicami. Więc, ogłoszono, że aby zachować ogólnonarodową sprawiedliwość i wyrównać szanse przyszłych pokoleń, wprowadza się limit roczny tychże punktów.

Nasz bohater stara przeciwstawiać się Partii jak może, ale oczywiście nie może robić tego bezpośrednio. Jakiekolwiek zgromadzenia, czy chociaż okazywanie w jakikolwiek sposób nieposłuszeństwa, prowadzi do natychmiastowej ewaporacji. Jest tego świadomy, i świadomy jest tego, że bezpieczny jest jedynie w swoich myślach. Dlatego ostatnio postanowił wykorzystywać swój umysł do minimalizacji wydanych punktów za przejazdy.

Przejdźmy jednak do szczegółów. Przed wprowadzeniem Promocji koszt punktowy nie zależał od kolejności wyboru dróg. Promocja polega na tym, że zmieniają się koszty punktowe ulic, jeśli są k-tą przejechaną ulicą począwszy od początku. Partia, aby ułatwić sobie życie, zmienia, dla danego k, punkty za przejazd między każdą parą skrzyżowań.

Nas w międzyczasie będzie interesował koszt najtańszego przejazdu z punktu ai do bi.

Na koniec dodam, że Promocja, jak to promocja, wcale kosztu obniżać nie musi, bo przecież można przekonać obywateli, że cena była tak wysoka od zawsze. Za to infrastruktura drogowa jest dość specjalna, bo każde skrzyżowanie jest połączone z każdym (bez przecięć ulic poza nimi), a na każdym skrzyżowaniu jest rondo (uznawane za ulicę) oraz Partia ogłosiła, że nigdy nie będzie pobierać kosztów za jeżdzenie po rondach!

Wejście

W pierwszym wierszu standardowego wejścia znajdują się trzy liczby całkowite n, kmx, o (1 <= n <= 50, 1 <= kmx <= 1.000, 1 <= o <= 100.000) oznaczająco odpowiednio liczbę skrzyżowań, maksymalną wartość k, jaka może wystąpić w testach, oraz liczbę wykonywanych operacji.

W następnych n liniach będzie po n liczb całkowitych ai,j (0 <= ai,j <= 1.000). j-ta liczba w i-tej linii oznacza początkową opłatę za przejazd ze skrzyżowania i do j. Ponadto ai,i będzie zawsze równe 0.
W następnych o liniach jest litera c oznaczająca jedno z dwóch poleceń, jakie Twój program ma wykonywać.

Przy poleceniu 'Q', wystąpią dwie liczby całkowite a,b (1 <= a,b <= n). Powinieneś wypisać koszt najtańszego wyboru trasy z a do b zgodnie z rozporządzeniami władz.

Przy poleceniu 'U', które wystąpi co najwyżej 100 razy, pojawi się liczba k (1 <= k <= kmx) oznaczająca zmiany kosztów ulic, jeśli są k-te na trasie. Następnie podany jest opis zmian w identyczny sposób, jak początkowe opłaty.

Wyjście

Dla każdego zapytania 'Q', powinieneś wypisać jedną liczbę całkowitą oznaczającą odpowiedź na zadane pytanie.

Przykład 

Wejście:
3 3 5
0 2 7
3 0 8
5 2 0
Q 3 1
Q 1 3
U 3
0 2 7
5 0 1
2 2 0
Q 1 3
Q 2 1

Wyjście:
5
7
3
3

Przy trzecim pytaniu najpierw jedziemy z 1 do 2 za 2 punkty, potem kręcimy się na rondzie 2, a następnie jedziemy z 2 do 3 za 1 punkt. Przy czwartym możemy osiągnąć sumę 3 na więcej niż jeden sposób.