About two hundred years ago, a serious dispute evoked between the two neighboring colonies of Khulna: PMG and TNT colony. Up to that time, these two colonies, who used to share a common border between them, lived in harmony. But after one catastrophic incidence, the scenario changed completely.
It started when 18 chickens went miraculously missing from one of the houses of PMG colony. The remnants of the chickens were later found out between the borders of these two colonies. Shocked and infuriated by this, the inhabitants of PMG colony blamed the TNT colony and war irrupted. It has been going on since, and right here, our hero Datta comes in.
Datta is known as the Database of Khulna for his vast knowledge of the landscape and resources of the city. Datta has taken the entire map of Khulna city into his head and came out with a plan for ending this heinous war, once and for all.
The entire Khulna city can be mapped as a graph, where there are directed connecting roads between the two neighboring colonies. Each road can carry a certain amount of people from one rival colony per day. Datta has denoted PMG colony with 0 and TNT colony with N - 1, where N is the total number of colonies in Khulna. Each morning, Datta creates a barricade in one of the connecting roads of the city. Due to his immense influence over the city politics, his barricades are never taken away. After putting one barricade, if it is still possible to send at least one soldier from PMG colony to TNT colony or vice versa, the war will continue to take place. A colony will dominate it's rival, if at a certain point of the war, it can send more soldiers to it's enemy base, than receiving soldiers from the enemy base. Please see the sample cases for further clarification.
Ghosh on the other hand, supplies sweetmeats to both the rival colonies. Ghosh has calculated that if this war stops, his selling of sweets will reduce by a great deal. Obviously Ghosh does not want this to happen and wants the war to continue.
You have to determine, after each barricade has been placed, whether PMG colony or TNT colony would have the upper hand of this war.
The first line of the input file contains N, ( 2 <= N <= 100 ) the number of colonies in Khulna city and M ( 1 <= M <= ( N * ( N - 1 ) ) ) denotes the number of roads between two colonies.
In each of the next M lines, description of the roads will be given in the following format:
u v w
meaning at most w ( 1 <= w <= 1000 ) people of a certain city can go from colony u to colony v ( 0 <= u , v < N ) in a day. You can safely assume that their is at most one directed road for each ordered pair of connected colonies.
After that, an integer D ( 1 <= D <= ( N * ( N - 1 ) ) ) will indicate the number of barricades that Datta would put on. The following D lines will describe Datta's barricades in sequential order. Each line will have two integers u and v to denote that the barricade is between the directed road from u to v. Note that, Datta would only put a barricade between two colonies, it there already exists a road between them.
For each line of Datta's action, you have to print PMG, if PMG colony has the advantage, or TNT if TNT colony has more domination. In case, both the colonies have equal strength and the war is still going on, print Ghosh wins. But if the war ends after placing one of Datta's barricades, print Datta wins.
| Input | Output |
|---|---|
3 4 0 2 10 0 1 5 1 2 7 2 0 2 3 1 2 0 2 2 0 | PMG TNT Datta wins |
| Input | Output |
|---|---|
4 6 0 1 13 0 2 2 1 2 5 2 1 2 1 3 13 2 3 2 2 0 1 0 2 | PMG Datta wins |