Codah ClubΕξασκήσου. Υπόβαλε. Βελτιώσου.
Σύνδεση
Ελληνικά
#0006AF

Ostrva - Izborno

Captain Mika has a very important task: he must create a map of an archipelago containing n islands. He has a small ship and a brave crew under his command. He has opted for the following strategy: For each possible path from one island A to a different island B, he will count the amount of other islands located on the right hand side of the ship's path and he will note it down. An island is located to the right of the path if it is contained within the right half plane ("half sea") defined with the straight line AB. The direction is, of course, important - if an island is located to the right of the path from A to B, then it is located to the left of the path from B to A.


Bear in mind that there won't be three distinct collinear islands, i.e. the ship will never run into a third island while on a straight line path from any two islands. Also bear in mind that it is not known how exactly the captain's notes are helpful in drawing the actual map.


After all his journeys were complete, captain Mika has started checking his notes and tried to answer k queries of the type: "when I travelled from island A to island B, was island C to my right?, but has failed. Would you be able to help him?


InputFrom the first line of the standard input read a single integer n - the amount of islands in the archipelago. In the following n lines (3 ≤ n ≤ 200) there are n integers in each line - they represent the matrix which represents Mika's notes. aij marks the amount of islands to the ship's right while traveling from island i to island j (the islands are marked by integers from 1 to n). The elements of the main diagonal of the matrix a will always be 0. From the following line of the standard input read the number k - the amount of Mika's queries (1 ≤ k ≤ 10^5). Ultimately, in each of the following k lines, 3 integers A, B and [] are located (1 ≤ A, B, C ≤ n, A ≠ B ≠ C ≠ A). These numbers represent a query of the form: has the island C been on the right hand side of the path from island A to island B?

OutputFor each of the k queries you should answer with 'DA' if the answer to the question is positive, and 'NE' otherwise (without apostrophes). Answer the queries in the order of the input, and write each answer in a separate line of the standard output.

Input:
[c]3
0 1 0
0 0 1
1 0 0
2
1 2 3
1 3 2
Output:
DA
NE
Explanation: Since there is a single island on the right hand side of the path from island 1 to island 2 (a12 = 1) and since there are only 3 islands in the archipelago, that island has to be island number 3, so the answer to the first query is positive. Analogously, the answer to the second query is negative (island 2 can't be on the right hand side of the path from island 1 to island 3).

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.