Usaneko Matrix

A rabbit and a cat play a game. The rules are as follows.

First, the two animals each write $n^2$ integers on paper in an $n \times n$ square grid, and each draws one playing card. Then they shuffle 1 000 000 cards, each bearing one of the numbers from 1 to 1 000 000, and draw them one at a time, alternating turns. Whenever a card is drawn, each animal marks the number on its own paper if that number appears there. The winning condition is that the number of "sets of $n$ marked numbers that lie on a single straight line" becomes at least the number on the playing card drawn at the start.

Answer which of the rabbit and the cat wins by the time the given $m$-th card has been drawn. The winner is decided at the moment a card is drawn and marked, if exactly one of the two animals satisfies the winning condition; otherwise the game is a draw. Cards may still be drawn after one animal satisfies the winning condition, but this does not affect the outcome.

Line 1: "$n$ $u$ $v$ $m$" (the size of the square grid, the rabbit's playing card number, the cat's playing card number, the number of cards drawn) Lines 2 to $n+1$: the $n^2$ numbers the rabbit writes on paper Lines $n+2$ to $2n+1$: the $n^2$ numbers the cat writes on paper Lines $2n+2$ to $2n+m+1$: the $m$ cards drawn

• $1 \le n \le 500$
• $1 \le u, v \le 13$
• $1 \le m \le 100\,000$
• $1 \le$ (numbers written) $\le 1\,000\,000$

The $n^2$ numbers the rabbit writes, the $n^2$ numbers the cat writes, and the numbers on the $m$ drawn cards are each distinct within their own group.

Print "USAGI" if the rabbit wins, "NEKO" if the cat wins, or "DRAW" for a draw, each on a single line.