시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB0000.000%

문제

W Bajtocji uruchomiono właśnie Superszybką Sieć Światłowodową. Łączy ona n domów za pomocą n - 1 kabli światłowodowych tak, że pomiędzy każdą parą domów istnieje dokładnie jedno (być może niebezpośrednie) połączenie. Ulubionym zajęciem mieszkańców Bajtocji jest kręcenie amatorskich filmów przyrodniczych, które potem umieszczają w Sieci, by pochwalić się nimi swoim przyjaciołom.

Gdy mieszkaniec i-tego domu chce pobrać film o wielkości w megabajtów umieszczony przez mieszkańca domu j, musi nawiązać połączenie między domami i oraz j o przepustowości w megabitów (Bajtocczanie są bardzo niecierpliwi). W tym celu na kablach leżących na ścieżce między tymi domami należy zarezerwować przepustowość w megabitów. Pojedynczy kabel może obsługiwać wiele połączeń, należy jednak pamiętać o tym, że ma on swoją maksymalną przepustowość.

Twoim celem jest napisanie programu, który będzie umożliwiał nawiązywanie połączeń w Sieci.

입력

W pierwszym wierszu wejścia znajduje się liczba całkowita n (2 ≤ n ≤ 100 000) oznaczająca liczbę domów w Bajtocji. W kolejnych n wierszach znajdują się po trzy liczby całkowite ai, bi, pi (1 ≤ ai < bin, 1 ≤ pi ≤ 1 000 000) oznaczające, że pomiędzy domami ai oraz bi istnieje kabel o przepustowości pi megabitów.

W następnym wierszu wejścia znajduje się liczba całkowita m (1 ≤ m ≤ 100 000) oznaczająca liczbę zgłoszeń do Sieci. W kolejnych m wierszach znajdują się po trzy liczby całkowite ai, bi, wi (1 ≤ ai < bin, 0 ≤ wi ≤ 1 000 000) oznaczające zgłoszenie między domami ai oraz bi. Jeśli wi > 0, to zgłoszenie jest żądaniem nawiązania połączenia o przepustowości wi megabitów (można nawiązać kilka połączeń między daną parą domów). Dla wi = 0 zgłoszenie jest żądaniem przerwania wszystkich dotychczas nawiązanych połączeń między tymi domami.

출력

Dla każdego żądania nawiązania połączenia należy wypisać na wyjściu jeden wiersz zawierający słowo TAK lub NIE, w zależności od tego, czy rezerwacja się powiodła.

예제 입력 1

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

예제 출력 1

TAK
NIE
TAK
TAK
TAK
TAK
NIE
TAK

출처

Camp > POI Training Camp > ONTAK 2009 4-3번