#define DEBUG_ON
#define CONDITION true
using namespace std;/*{{{*/

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/time.h>
#include <vector>

#define INF (1e9)
static const double PI = acos(-1.0);
static const double EPS = 1e-10;

typedef long long int LL;
typedef unsigned long long int ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef complex<double> P;

#define FOR(i, b, e) for (typeof(e) i = (b); i != (e); i < (e)? ++i : --i)
#define REP(i, n) FOR(i, 0, n)

#define IFC(c) if(c) continue;
#define IFB(c) if(c) break;
#define IFR(c, r) if(c) return r;

#define OPOVER(_op, _type) inline bool operator _op (const _type &t) const

#define arrsz(a) ( sizeof(a) / sizeof(a[0]) )

#define F first
#define S second
#define MP(a, b) make_pair(a, b)

#define SZ(a) ((LL)a.size())
#define PB(e) push_back(e)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(c,it) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define BIT(n) (assert(n < 64), (1ULL << (n)))
#define BITOF(n, m) (assert(m < 64), ((ULL)(n) >> (m) & 1))

#define RANGE(a, b, c) ((a) <= (b) && (b) <= (c))

#define PQ priority_queue
#define SC static_cast

#ifdef DEBUG_ON
	#define dprt(fmt, ...) if (CONDITION) fprintf(stderr, fmt, ##__VA_ARGS__)
	#define darr(a) if (CONDITION) copy( (a), (a) + arrsz(a), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define darr_range(a, f, t) if (CONDITION) copy( (a) + (f), (a) + (t), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define dvec(v) if (CONDITION) copy( ALL(v), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define darr2(a, n, m) if (CONDITION) FOR(i, 0, (n)){ darr_range( (a)[i], 0, (m) ); }
	#define dvec2(v) if (CONDITION) FOR(i, 0, SZ(v)){ dvec( (v)[i] ); }
	#define WAIT() if (CONDITION) { string _wait_; cerr << "(hit return to continue)" << endl; getline(cin, _wait_); }
	#define dump(x) if (CONDITION) cerr << " [L" << __LINE__ << "] " << #x << " = " << (x) << endl;
	#define dumpf() if (CONDITION) cerr << __PRETTY_FUNCTION__ << endl;
	#define dumpv(x) if (CONDITION) cerr << " [L:" << __LINE__ << "] " << #x << " = "; REP(q, (x).size()) cerr << (x)[q] << " "; cerr << endl;
	#define where() if (CONDITION) cerr << __FILE__ << ": " << __PRETTY_FUNCTION__ << " [L: " << __LINE__ << "]" << endl;
	#define show_bits(b, s) if(CONDITION) { REP(i, s) { cerr << BITOF(b, s-1-i); if(i%4 == 3) cerr << ' '; } cerr << endl; }
#else
	#define cerr if(0) cerr
	#define dprt(fmt, ...)
	#define darr(a)
	#define darr_range(a, f, t)
	#define dvec(v)
	#define darr2(a, n, m)
	#define dvec2(v)
	#define WAIT()
	#define dump(x)
	#define dumpf()
	#define dumpv(x)
	#define where()
	#define show_bits(b, s)
#endif

/* Inline functions */
inline int onbits_count(ULL b) { int c = 0; while(b != 0) { c += (b & 1); b >>= 1; } return c; }
inline int bits_count(ULL b) { int c = 0; while(b != 0) { ++c; b >>= 1; } return c; }
inline int toInt(string s) { int v; istringstream sin(s);sin>>v;return v; }
template<class T> inline string toString(T x) { ostringstream sout;sout<<x;return sout.str(); }
inline double now(){ struct timeval tv; gettimeofday(&tv, NULL); return (static_cast<double>(tv.tv_sec) + static_cast<double>(tv.tv_usec) * 1e-6); }
inline VS split(string s, char delimiter) { VS v; string t; REP(i, s.length()) { if(s[i] == delimiter) v.PB(t), t = ""; else t += s[i]; } v.PB(t); return v; }

/* Tweaks */
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& d) {return s << "(" << d.first << ", " << d.second << ")";}

/* Frequent stuffs */
int n_dir = 4;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}; /* CSS order */
enum direction {
	UP, RIGHT, DOWN, LEFT
};
// int n_dir = 8;
// int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
// enum direction {
	// UP, UPRIGHT, RIGHT, DOWNRIGHT, DOWN, DOWNLEFT, LEFT, UPLEFT
// }
#define FORDIR(d) REP (d, n_dir)

/*}}}*/

class Competitor {
	public:
		VVI card;
		map<int, PII> num_to_pos;
		int quota;
		int n_bingo;
		Competitor(int n, int q): quota(q), n_bingo(0) {
			card = VVI(n, VI(n, 0));
		}
		void write_card(int y, int x, int v) {
			card[y][x] = v;
			num_to_pos[v] = MP(y, x);
		}
		void punch(int number) {
			if (!EXIST(num_to_pos, number)) {
				return;
			}
			PII p = num_to_pos[number];
			card[p.F][p.S] = 0;
			bool bingo = true;
			// vertical
			REP (i, card.size()) {
				if (card[i][p.S]) {
					bingo = false;
				}
			}
			n_bingo += bingo;
			bingo = true;
			// horizontal
			REP (j, card.size()){
				if (card[p.F][j]) {
					bingo = false;
				}
			}
			n_bingo += bingo;
			// diagonal
			if (p.F == p.S) {
				bingo = true;
				REP (i, card.size()){
					if (card[i][i]) {
						bingo = false;
					}
				}
				n_bingo += bingo;
			}
			// diagonal reverse
			if (p.F == card.size() - 1 - p.S) {
				bingo = true;
				REP (i, card.size()) {
					if (card[i][card.size() - 1 - i]) {
						bingo = false;
					}
				}
				n_bingo += bingo;
			}
			if (card.size() == 1) {
				n_bingo = n_bingo > 0;
			}
		}
		bool is_winning() {
			return n_bingo >= quota;
		}
		void print_card() {
			REP (i, card.size()) {
				REP (j, card.size()) {
					cerr << card[i][j] << " ";
				}
				cerr << endl;
			}
		}
};

int main()
{
	std::ios_base::sync_with_stdio(false);
	int n, u, v, m; cin >> n >> u >> v >> m;
	Competitor usagi(n, u), neko(n, v);
	vector<Competitor*> competitors; competitors.PB(&usagi); competitors.PB(&neko);
	REP (c, 2) {
		REP (i, n) {
			REP (j, n) {
				int val; cin >> val;
				competitors[c]->write_card(i, j, val);
			}
		}
	}
	bool u_win = false, n_win = false, draw = false;
	REP (_, m) {
		int val; cin >> val;
		IFC(u_win || n_win || draw);
		REP (c, 2) {
			competitors[c]->punch(val);
		}
		if (usagi.is_winning() && neko.is_winning()) {
			draw = true;
		} else if (usagi.is_winning()) {
			u_win = true;
		} else if (neko.is_winning()) {
			n_win = true;
		}
		// cerr << "---" << endl;
		// usagi.print_card();
		// cerr << "---" << endl;
		// neko.print_card();
	}
	if (u_win) {
		cout << "USAGI" << endl;
	} else if (n_win) {
		cout << "NEKO" << endl;
	} else {
		cout << "DRAW" << endl;
	}
}

// vim: foldmethod=marker
### Prompt

Please provide a Cpp coded solution to the problem described below:

Rabbits and cats are competing. The rules are as follows.

First, each of the two animals wrote n2 integers on a piece of paper in a square with n rows and n columns, and drew one card at a time. Shuffle two cards and draw them one by one alternately. Each time a card is drawn, the two will mark it if the same number as the card is written on their paper. The winning condition is that the number of "a set of n numbers with a mark and is in a straight line" is equal to or greater than the number of playing cards drawn at the beginning.

Answer which of the rabbit and the cat wins up to the mth card given. However, the victory or defeat is when only one of the two cards meets the victory condition when a certain card is drawn and marked. In other cases, it is a draw. Cards may be drawn even after one of them meets the victory conditions, but this does not affect the victory or defeat.



Input

Line 1: “nuvm” (square size, number of rabbit playing cards, number of cat playing cards, number of cards drawn) 2- (N + 1) Line: n2 numbers that the rabbit writes on paper ( N + 2)-(2N + 1) Line: n2 numbers that the cat writes on paper (2N + 2)-(2N + M + 1) Line: m cards drawn
1 ≤ n ≤ 500
1 ≤ u, v ≤ 13
1 ≤ m ≤ 100 000
1 ≤ (number written) ≤ 1 000 000


The number of n2 rabbits write on paper, the number of n2 cats write on paper, and the number of m cards drawn are different.

Output

Output "USAGI" if the rabbit wins, "NEKO" if the cat wins, and "DRAW" if the tie, each in one line.

Examples

Input

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


Output

USAGI


Input

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


Output

DRAW

### Response

```cpp
#define DEBUG_ON
#define CONDITION true
using namespace std;/*{{{*/

#include <algorithm>
#include <cassert>
#include <cctype>
#include <climits>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <iterator>
#include <list>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <string>
#include <sys/time.h>
#include <vector>

#define INF (1e9)
static const double PI = acos(-1.0);
static const double EPS = 1e-10;

typedef long long int LL;
typedef unsigned long long int ULL;
typedef vector<int> VI;
typedef vector<VI> VVI;
typedef vector<double> VD;
typedef vector<VD> VVD;
typedef vector<bool> VB;
typedef vector<VB> VVB;
typedef vector<char> VC;
typedef vector<VC> VVC;
typedef vector<string> VS;
typedef pair<int, int> PII;
typedef complex<double> P;

#define FOR(i, b, e) for (typeof(e) i = (b); i != (e); i < (e)? ++i : --i)
#define REP(i, n) FOR(i, 0, n)

#define IFC(c) if(c) continue;
#define IFB(c) if(c) break;
#define IFR(c, r) if(c) return r;

#define OPOVER(_op, _type) inline bool operator _op (const _type &t) const

#define arrsz(a) ( sizeof(a) / sizeof(a[0]) )

#define F first
#define S second
#define MP(a, b) make_pair(a, b)

#define SZ(a) ((LL)a.size())
#define PB(e) push_back(e)
#define SORT(v) sort((v).begin(), (v).end())
#define RSORT(v) sort((v).rbegin(), (v).rend())

#define ALL(a) (a).begin(), (a).end()
#define RALL(a) (a).rbegin(), (a).rend()
#define EACH(c,it) for(__typeof((c).begin()) it=(c).begin(); it!=(c).end(); ++it)
#define EXIST(s,e) ((s).find(e)!=(s).end())

#define BIT(n) (assert(n < 64), (1ULL << (n)))
#define BITOF(n, m) (assert(m < 64), ((ULL)(n) >> (m) & 1))

#define RANGE(a, b, c) ((a) <= (b) && (b) <= (c))

#define PQ priority_queue
#define SC static_cast

#ifdef DEBUG_ON
	#define dprt(fmt, ...) if (CONDITION) fprintf(stderr, fmt, ##__VA_ARGS__)
	#define darr(a) if (CONDITION) copy( (a), (a) + arrsz(a), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define darr_range(a, f, t) if (CONDITION) copy( (a) + (f), (a) + (t), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define dvec(v) if (CONDITION) copy( ALL(v), ostream_iterator<int>(cerr, " ") ); cerr << endl
	#define darr2(a, n, m) if (CONDITION) FOR(i, 0, (n)){ darr_range( (a)[i], 0, (m) ); }
	#define dvec2(v) if (CONDITION) FOR(i, 0, SZ(v)){ dvec( (v)[i] ); }
	#define WAIT() if (CONDITION) { string _wait_; cerr << "(hit return to continue)" << endl; getline(cin, _wait_); }
	#define dump(x) if (CONDITION) cerr << " [L" << __LINE__ << "] " << #x << " = " << (x) << endl;
	#define dumpf() if (CONDITION) cerr << __PRETTY_FUNCTION__ << endl;
	#define dumpv(x) if (CONDITION) cerr << " [L:" << __LINE__ << "] " << #x << " = "; REP(q, (x).size()) cerr << (x)[q] << " "; cerr << endl;
	#define where() if (CONDITION) cerr << __FILE__ << ": " << __PRETTY_FUNCTION__ << " [L: " << __LINE__ << "]" << endl;
	#define show_bits(b, s) if(CONDITION) { REP(i, s) { cerr << BITOF(b, s-1-i); if(i%4 == 3) cerr << ' '; } cerr << endl; }
#else
	#define cerr if(0) cerr
	#define dprt(fmt, ...)
	#define darr(a)
	#define darr_range(a, f, t)
	#define dvec(v)
	#define darr2(a, n, m)
	#define dvec2(v)
	#define WAIT()
	#define dump(x)
	#define dumpf()
	#define dumpv(x)
	#define where()
	#define show_bits(b, s)
#endif

/* Inline functions */
inline int onbits_count(ULL b) { int c = 0; while(b != 0) { c += (b & 1); b >>= 1; } return c; }
inline int bits_count(ULL b) { int c = 0; while(b != 0) { ++c; b >>= 1; } return c; }
inline int toInt(string s) { int v; istringstream sin(s);sin>>v;return v; }
template<class T> inline string toString(T x) { ostringstream sout;sout<<x;return sout.str(); }
inline double now(){ struct timeval tv; gettimeofday(&tv, NULL); return (static_cast<double>(tv.tv_sec) + static_cast<double>(tv.tv_usec) * 1e-6); }
inline VS split(string s, char delimiter) { VS v; string t; REP(i, s.length()) { if(s[i] == delimiter) v.PB(t), t = ""; else t += s[i]; } v.PB(t); return v; }

/* Tweaks */
template<typename T1, typename T2> ostream& operator<<(ostream& s, const pair<T1, T2>& d) {return s << "(" << d.first << ", " << d.second << ")";}

/* Frequent stuffs */
int n_dir = 4;
int dx[] = {0, 1, 0, -1}, dy[] = {-1, 0, 1, 0}; /* CSS order */
enum direction {
	UP, RIGHT, DOWN, LEFT
};
// int n_dir = 8;
// int dx[] = {0, 1, 1, 1, 0, -1, -1, -1}, dy[] = {-1, -1, 0, 1, 1, 1, 0, -1};
// enum direction {
	// UP, UPRIGHT, RIGHT, DOWNRIGHT, DOWN, DOWNLEFT, LEFT, UPLEFT
// }
#define FORDIR(d) REP (d, n_dir)

/*}}}*/

class Competitor {
	public:
		VVI card;
		map<int, PII> num_to_pos;
		int quota;
		int n_bingo;
		Competitor(int n, int q): quota(q), n_bingo(0) {
			card = VVI(n, VI(n, 0));
		}
		void write_card(int y, int x, int v) {
			card[y][x] = v;
			num_to_pos[v] = MP(y, x);
		}
		void punch(int number) {
			if (!EXIST(num_to_pos, number)) {
				return;
			}
			PII p = num_to_pos[number];
			card[p.F][p.S] = 0;
			bool bingo = true;
			// vertical
			REP (i, card.size()) {
				if (card[i][p.S]) {
					bingo = false;
				}
			}
			n_bingo += bingo;
			bingo = true;
			// horizontal
			REP (j, card.size()){
				if (card[p.F][j]) {
					bingo = false;
				}
			}
			n_bingo += bingo;
			// diagonal
			if (p.F == p.S) {
				bingo = true;
				REP (i, card.size()){
					if (card[i][i]) {
						bingo = false;
					}
				}
				n_bingo += bingo;
			}
			// diagonal reverse
			if (p.F == card.size() - 1 - p.S) {
				bingo = true;
				REP (i, card.size()) {
					if (card[i][card.size() - 1 - i]) {
						bingo = false;
					}
				}
				n_bingo += bingo;
			}
			if (card.size() == 1) {
				n_bingo = n_bingo > 0;
			}
		}
		bool is_winning() {
			return n_bingo >= quota;
		}
		void print_card() {
			REP (i, card.size()) {
				REP (j, card.size()) {
					cerr << card[i][j] << " ";
				}
				cerr << endl;
			}
		}
};

int main()
{
	std::ios_base::sync_with_stdio(false);
	int n, u, v, m; cin >> n >> u >> v >> m;
	Competitor usagi(n, u), neko(n, v);
	vector<Competitor*> competitors; competitors.PB(&usagi); competitors.PB(&neko);
	REP (c, 2) {
		REP (i, n) {
			REP (j, n) {
				int val; cin >> val;
				competitors[c]->write_card(i, j, val);
			}
		}
	}
	bool u_win = false, n_win = false, draw = false;
	REP (_, m) {
		int val; cin >> val;
		IFC(u_win || n_win || draw);
		REP (c, 2) {
			competitors[c]->punch(val);
		}
		if (usagi.is_winning() && neko.is_winning()) {
			draw = true;
		} else if (usagi.is_winning()) {
			u_win = true;
		} else if (neko.is_winning()) {
			n_win = true;
		}
		// cerr << "---" << endl;
		// usagi.print_card();
		// cerr << "---" << endl;
		// neko.print_card();
	}
	if (u_win) {
		cout << "USAGI" << endl;
	} else if (n_win) {
		cout << "NEKO" << endl;
	} else {
		cout << "DRAW" << endl;
	}
}

// vim: foldmethod=marker
```