Kapetan Mika ima zadatak da napravi mapu arhipelaga koji se sastoji od n ostrva. Na raspolaganju ima mali brod i hrabru posadu. On se odlučio za sledeću taktiku: za svaka dva različita ostrva A i B , on će se pravolinijski uputiti od ostrva A do ostrva B, izbrojaće koliko se ostalih ostrva nalazi sa desne strane putanje broda i pribeležiće to. Ostrvo se nalazi sa desne strane putanje ako pripada desnoj poluravni (polumoru) određenoj pravom AB. Smer je, naravno, bitan - ako je neko ostrvo sa desne strane putanje od A do B, onda je ono sa leve strane putanje od B do A.

Napomenimo da ne postoje tri kolinearna ostrva, tj. pri pomenutim pravolinijskim putanjama između dva ostrva brod nikad neće naleteti na neko treće ostrvo. Takođe napomenimo da nije poznato kako kapetanove beleške pomažu pri pravljenju mape.

Posle svih putovanja, kapetan Mika se zagledao u svoje beleške i pokušao na osnovu njih da odgovori na k pitanja tipa: "kada sam putovao od ostrva A do ostrva B, da li mi je ostrvo C bilo sa desne strane?", ali nije uspeo. Možete li mu pomoći?

Ulaz.

(Ulazni podaci se učitavaju iz datoteke ostrva.in.) U prvom redu ulazne datoteke nalazi se jedan prirodan broj n - broj ostrva u arhipelagu. Zatim se u narednih n redova (3 ≤ n ≤ 200) nalaze po n celih brojeva - opis matrice a koja predstavlja Mikine beleške. a_ij označava broj ostrva sa desne strane pri putovanju od ostrva i do ostrva j (ostrva su numerisana brojevima od 1 do n ). Elementi na glavnoj dijagonali matrice a će uvek biti 0. U narednom redu ulazne datoteke nalazi se broj k - broj Mikinih upita (1 ≤ k ≤ 10⁵). Najzad, u sledećih k redova se nalaze po 3 cela broja A , B i C (1 ≤ A, B, C ≤ n , A ≠B ≠ C ≠ A) koji predstavljaju pitanje: da li je ostrvo C sa desne strane putanje od ostrva A do ostrva B .

Izlaz.

(Izlazni podaci se ispisuju u datoteku ostrva.out.) Za svaki od k upita je potrebno odgovoriti sa ’DA’ ili ’NE’ (bez navodnika), zavisno od toga da li je odgovarajuće ostrvo sa prave strane. Na pitanja odgovarati u datom redosledu, pri čemu svaki odgovor treba biti ispisan u posebnom redu.

Primer 1.

3
0 1 0
0 0 1
1 0 0
2
1 2 3
1 3 2

DA
NE

Objašnjenje.

Kako se sa desne strane puta od ostrva 1 do ostrva 2 nalazi jedno ostrvo (a₁₂ = 1) i kako imamo samo 3 ostrva, to ostrvo mora biti ostrvo 3, pa je odgovor na prvo pitanje potvrdan. Slično, ostrvo 2 se ne može nalaziti sa desne strane puta od ostrva 1 do ostrva 3.

#include <cstdlib>
#include <cstdio>
#include <memory.h>

const int MaxN = 210;

int n, k;
int a[MaxN][MaxN];
bool sol[MaxN][MaxN][MaxN];
bool mark[MaxN];

int main()
{
  freopen("ostrva.in", "r", stdin);
  freopen("ostrva.out", "w", stdout);

  scanf("%d", &n);
  for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
    {
      scanf("%d", &a[i][j]);
    }

  memset(mark, false, sizeof(mark));

  for (int count = 1; count <= n - 2; count++)
  {
    // nalazenje tacke na konveksnom omotacu
    int x = 0;
    for (int i = 1; i < n; i++)
    {
      if (mark[i]) continue;
      for (int j = i + 1; j <= n; j++)
        if (!mark[j] && a[i][j] == 0)
        {
          x = i;
          break;
        }
      if (x != 0) break;
    }
    mark[x] = true;

    // racunanje odgovora na sve upite koji sadrze tacku x (i,j,x)
    // i izbacivanje tacke x (updateovanje matrice a)
    for (int i = 1; i < n; i++)
      for (int j = i + 1; j <= n; j++)
        if (!mark[i] && !mark[j])
        {
          bool b = (a[x][i] > a[x][j]);
          sol[x][i][j] = sol[i][j][x] = sol[j][x][i] = b;
          sol[x][j][i] = sol[j][i][x] = sol[i][x][j] = !b;

          if (b)
            a[i][j]--;
          else
            a[j][i]--;
        }

  }

  scanf("%d", &k);
  for (int i = 1; i <= k; i++)
  {
    int a, b, c;
    scanf("%d%d%d", &a, &b, &c);
    printf("%s\n", (sol[a][b][c] ? "DA" : "NE"));
  }
  return 0;
}

const
  MaxN = 210;

VAR
  inFile, outFile : text;
  n, k, i, j, count, x, y, z : longint;
  val : boolean;
  a : array[0..MaxN, 0..MaxN] of longint;
  sol: array[0..MaxN, 0..MaxN, 0..MaxN] of boolean;
  mark : array[0..MaxN] of boolean;

BEGIN

  assign(inFile, 'ostrva.in');
  assign(outFile, 'ostrva.out');
  reset(inFile); rewrite(outFile);

  readln(inFile, n);
  for i := 1 to n do
    for j := 1 to n do
      read(inFile, a[i][j]);
  
  fillchar(mark, sizeof(mark), false);

  for count := 1 to n - 2 do begin
  
    // nalazenje tacke na konveksnom omotacu
    x := 0;
    for i := 1 to n - 1 do begin
      if (mark[i]) then continue;
      for j := i + 1 to n do
        if ((NOT mark[j]) AND (a[i][j] = 0)) then begin
          x := i;
          break;
        end;
      if (x <> 0) then break;
    end;
    mark[x] := true;

    // racunanje odgovora na sve upite koji sadrze tacku x (i,j,x)
    // i izbacivanje tacke x (updateovanje matrice a)
    for i := 1 to n - 1 do
      for j := i + 1 to n do
        if ((NOT mark[i]) AND (NOT mark[j])) then begin
          val := (a[x][i] > a[x][j]);
          sol[x][i][j] := val; sol[i][j][x] := val; sol[j][x][i] := val;
          sol[x][j][i] := NOT val; sol[j][i][x] := NOT val; sol[i][x][j] := NOT val;

          if (val) then
            a[i][j] := a[i][j] - 1
          else
            a[j][i] := a[j][i] - 1;
        end;

  end;

  readln(inFile, k);
  for i := 1 to k do begin
    read(inFile, x, y, z);
    if (sol[x][y][z]) then
      writeln(outFile, 'DA')
    else
      writeln(outFile, 'NE');
  end;

        close(inFile);
        close(outFile);

END.