Archiwum zadań programistycznych WWSI

Jakże wielkie było nasze zaskoczenie kiedy zajrzeliśmy dzisiaj rano do magazynu WWSI. Otóż kartony, w których znajdowały się nagrody dla zwycięzców MWWSIP zniknęły! Jeszcze wczoraj po południu leżały wszystkie na stosie o numerze p a teraz po prostu ich nie ma! Wyniki śledztwa jakie natychmiastowo rozpoczęliśmy trochę nas uspokoiły, wciąż jednak sytuacja nie jest w stu procentach jasna...

Nasze śledztwo wykazało, że wczoraj tuż po naszym opuszczeniu budynku jeden z pracowników szukał czegoś w magazynie i poprzestawiał w nim większość kartonów. Na naszą prośbę odtworzył z pamięci wygląd magazynu sprzed szukania oraz ruchy jakie wykonywał. W ten sposób uzyskaliśmy informację, że "początkowo na stosie o numerze jeden znajdowały się 3 kartony, na stosie o numerze dwa było 5 kartonów, a na n-tym stosie 38 kartonów. Wasze kartony były na p-tym stosie - najpierw wziąłem dwa kartony ze stosu drugiego i przełożyłem je na stos czwarty, potem wziąłem trzy kartony ze stosu n-tego i przełożyłem je na stos pierwszy... itd."

Wszystko to rzetelnie spisaliśmy i teraz potrzebujemy programu, który na podstawie informacji o liczbie kartonów znajdujących się na danym stosie, numerze stosu który zawierał nasze kartony (stos ten zwierał wyłącznie nasze kartony), a także wykonywanych przez sprzątającego ruchach określi ile obecnie należących do nas kartonów znajduje się na danym stosie. Należy brać pod uwagę, że w takich sytuacjach pamięć bywa zawodna tak więc czasem opis może okazać się nieprecyzyjny - tzn. czasami według relacji, sprzątający wziął ze stosu pięć kartonów podczas kiedy w rzeczywistości znajdowały się na nim jedynie trzy innym razem z kolei twierdził, że brał kartony ze stosu który w rzeczywistości był pusty... Zakładamy wtedy że w pierwszym przypadku sprzątający wziął w rzeczywistości jedynie trzy kartony, a liczba pięć była po prostu pomyłką a w drugim przypadku nie wziął ich wcale (są to jedyne rodzaje nieścisłości jakie mogą wystąpić).

Wejście

W pierwszej linii wejścia znajdują się dwie liczby n (1 ≤ n ≤ 1000) oraz p (1 ≤ p ≤ n) określające odpowiednio liczbę stosów znajdujących się w magazynie oraz numer stosu na którym początkowo znajdowały się interesujące nas kartony. W drugiej linii znajduje się n liczb z przedziału od 1 do 10⁶, każda z nich określa początkowy rozmiar danego stosu (i-ta liczba określa i-ty stos). W trzeciej linii wejścia znajduje się liczba m (1 ≤ m ≤ 10000) opisująca ile ruchów wykonała osoba sprzątająca magazyn, a po niej w każdej z następnych m linii znajduje się opis kolejnego wykonanego przestawienia. Opis ten składa się z trzech liczb a, b oraz c (1 ≤ a, b ≤ n; a ≠ b; 1 ≤ c ≤ 10) oznaczających odpowiednio numer stosu, z którego wzięte zostały kartony, numer stosu na jaki kartony zostały przełożone i liczbę przełożonych kartonów. Należy założyć, że kartony zawsze przekładane są pojedynczo (w końcu nie ma co przeciążać kręgosłupa dźwigając dwa kartony za jednym razem!).

Wyjście

Na wyjściu należy wypisać n liczb oddzielonych od siebie pojedynczymi spacjami. Liczby te powinny określać ile interesujących nas kartonów znajduje się na danym stosie (i-ta liczba opisuje i-ty stos).

Przykład

Wejście:

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

Wyjście:

2 0 0 0 1