////////////////////////////////////////
///  tu3 pro-con template            ///
////////////////////////////////////////
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <regex>
using namespace std;

//// MACRO ////
#define countof(a) (sizeof(a)/sizeof(a[0]))

#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define RFOR(i,s,n) for (int i = (n)-1; i >= (s); i--)
#define pos(c,i) c.being() + (i)
#define allof(c) c.begin(), c.end()
#define aallof(a) a, countof(a)
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define apartof(a,i,n) a + (i), a + (i) + (n)
#define long long long

#define EPS 1e-9
#define INF (1L << 30)
#define LINF (1LL << 60)

#define PREDICATE(t,a,exp) [&](const t & a) -> bool { return exp; }
#define COMPARISON_T(t) bool(*)(const t &, const t &)
#define COMPARISON(t,a,b,exp) [&](const t & a, const t & b) -> bool { return exp; }
#define CONVERTER(TSrc,t,TDest,exp) [&](const TSrc &t)->TDest { return exp; }

inline int sign(double x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
inline bool inRange(int val, int min, int max) { return val >= min && val < max; }
inline bool inRange(double val, double min, double max) { return val - min > -EPS && val - max < EPS; }
template <class T> struct vevector : public vector<vector<T>> { vevector(int n = 0, int m = 0, const T &initial = T()) : vector<vector<T>>(n, vector<T>(m, initial)) { } };
template <class T> struct vevevector : public vector<vevector<T>> { vevevector(int n = 0, int m = 0, int l = 0, const T &initial = T()) : vector<vevector<T>>(n, vevector<T>(m, l, initial)) { } };
template <class T> struct vevevevector : public vector<vevevector<T>> { vevevevector(int n = 0, int m = 0, int l = 0, int k = 0, const T &initial = T()) : vector<vevevector<T>>(n, vevevector<T>(m, l, k, initial)) { } };

//// i/o helper ////

#ifdef _DEBUG
#define DEBUG WRITE
inline void readfrom(string filename) { freopen(filename.c_str(), "r", stdin); }
inline void writeto(string filename) { freopen(filename.c_str(), "w", stdout); }
#else
#define DEBUG(...)
inline void readfrom(...) { }
inline void writeto(...) { }
#endif
#ifdef ccout
#  define cout ccout
#  define endl cendl
#endif

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
struct _Writer { bool f; _Writer() : f(false) { } template <class T> _Writer operator ,(const T &rhs) { cout << (f ? " " : "") << rhs; f = true; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__
#define WRITE(...) _Writer(), __VA_ARGS__; cout << endl

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i, n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i, n) v.push_back(read<T>(m)); return v; }
template <class T> vevector<T> readjag() { return read<T>(read<int>()); }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(readjag<T>()); return v; }

template <class T1, class T2> inline istream & operator >> (istream & in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; }
template <class T1, class T2> inline ostream & operator << (ostream &out, pair<T1, T2> &p) { out << p.first << p.second; return out; }
template <class T> inline ostream & operator << (ostream &out, const vector<T> &v)
{
	ostringstream ss;
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	out << s.substr(0, s.length() - 1) << endl;
	return out;
}

//// start up ////
void solve();


int main()
{
	solve();
	return 0;
}

////////////////////
/// template end ///
////////////////////

void solve()
{
	int testcases = 1;
	REP(testcase, testcases)
	{
		READ(int, n, u, v, m);
		vector<int> usa(2 * n + 2, n), neko(2 * n + 2, n);
		vector<int> usamap(1000001, -1), nekomap(1000001, -1);
		REP(i, n) REP(j, n) { usamap[read<int>()] = i << 16 | j; }
		REP(i, n) REP(j, n) { nekomap[read<int>()] = i << 16 | j; }

		int win = 0;
		REP(i, m)
		{
			READ(int, d);
			if (!win)
			{
				REP(k, 2)
				{
					const vector<int> &mp = !k ? usamap : nekomap;
					vector<int> &te = !k ? usa : neko;
					int &re = !k ? u : v;
					int c = 0;
					if (mp[d] == -1) continue;
					int i = mp[d] >> 16, j = (short)mp[d];
					if (--te[i] == 0) { c++; } // たて
					if (--te[n + j] == 0) { c++; } // よこ
					if (i - j == 0) if (--te[2 * n] == 0) { c++; } // ななめ
					if (i + j + 1 == n) if (--te[2 * n + 1] == 0) { c++; }
					if (n == 1) { c = min(c, 1); }
					re -= c;
					if (re <= 0) { win |= 1 << k; }
				}
			}
		}

		switch (win)
		{
		case 1: WRITE("USAGI"); break;
		case 2: WRITE("NEKO"); break;
		default: WRITE("DRAW"); break;
		}
	}
}
### Prompt

Your challenge is to write a cpp solution to the following problem:

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
////////////////////////////////////////
///  tu3 pro-con template            ///
////////////////////////////////////////
#include <cassert>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <iostream>
#include <sstream>
#include <algorithm>
#include <numeric>
#include <functional>
#include <vector>
#include <queue>
#include <string>
#include <complex>
#include <stack>
#include <set>
#include <map>
#include <list>
#include <unordered_map>
#include <unordered_set>
#include <bitset>
#include <regex>
using namespace std;

//// MACRO ////
#define countof(a) (sizeof(a)/sizeof(a[0]))

#define REP(i,n) for (int i = 0; i < (n); i++)
#define RREP(i,n) for (int i = (n)-1; i >= 0; i--)
#define FOR(i,s,n) for (int i = (s); i < (n); i++)
#define RFOR(i,s,n) for (int i = (n)-1; i >= (s); i--)
#define pos(c,i) c.being() + (i)
#define allof(c) c.begin(), c.end()
#define aallof(a) a, countof(a)
#define partof(c,i,n) c.begin() + (i), c.begin() + (i) + (n)
#define apartof(a,i,n) a + (i), a + (i) + (n)
#define long long long

#define EPS 1e-9
#define INF (1L << 30)
#define LINF (1LL << 60)

#define PREDICATE(t,a,exp) [&](const t & a) -> bool { return exp; }
#define COMPARISON_T(t) bool(*)(const t &, const t &)
#define COMPARISON(t,a,b,exp) [&](const t & a, const t & b) -> bool { return exp; }
#define CONVERTER(TSrc,t,TDest,exp) [&](const TSrc &t)->TDest { return exp; }

inline int sign(double x) { return (abs(x) < EPS ? 0 : x > 0 ? 1 : -1); }
inline bool inRange(int val, int min, int max) { return val >= min && val < max; }
inline bool inRange(double val, double min, double max) { return val - min > -EPS && val - max < EPS; }
template <class T> struct vevector : public vector<vector<T>> { vevector(int n = 0, int m = 0, const T &initial = T()) : vector<vector<T>>(n, vector<T>(m, initial)) { } };
template <class T> struct vevevector : public vector<vevector<T>> { vevevector(int n = 0, int m = 0, int l = 0, const T &initial = T()) : vector<vevector<T>>(n, vevector<T>(m, l, initial)) { } };
template <class T> struct vevevevector : public vector<vevevector<T>> { vevevevector(int n = 0, int m = 0, int l = 0, int k = 0, const T &initial = T()) : vector<vevevector<T>>(n, vevevector<T>(m, l, k, initial)) { } };

//// i/o helper ////

#ifdef _DEBUG
#define DEBUG WRITE
inline void readfrom(string filename) { freopen(filename.c_str(), "r", stdin); }
inline void writeto(string filename) { freopen(filename.c_str(), "w", stdout); }
#else
#define DEBUG(...)
inline void readfrom(...) { }
inline void writeto(...) { }
#endif
#ifdef ccout
#  define cout ccout
#  define endl cendl
#endif

struct _Reader { template <class T> _Reader operator ,(T &rhs) { cin >> rhs; return *this; } };
struct _Writer { bool f; _Writer() : f(false) { } template <class T> _Writer operator ,(const T &rhs) { cout << (f ? " " : "") << rhs; f = true; return *this; } };
#define READ(t,...) t __VA_ARGS__; _Reader(), __VA_ARGS__
#define WRITE(...) _Writer(), __VA_ARGS__; cout << endl

template <class T> T read() { T t; cin >> t; return t; }
template <class T> vector<T> read(int n) { vector<T> v; REP(i, n) { v.push_back(read<T>()); } return v; }
template <class T> vevector<T> read(int n, int m) { vevector<T> v; REP(i, n) v.push_back(read<T>(m)); return v; }
template <class T> vevector<T> readjag() { return read<T>(read<int>()); }
template <class T> vevector<T> readjag(int n) { vevector<T> v; REP(i, n) v.push_back(readjag<T>()); return v; }

template <class T1, class T2> inline istream & operator >> (istream & in, pair<T1, T2> &p) { in >> p.first >> p.second; return in; }
template <class T1, class T2> inline ostream & operator << (ostream &out, pair<T1, T2> &p) { out << p.first << p.second; return out; }
template <class T> inline ostream & operator << (ostream &out, const vector<T> &v)
{
	ostringstream ss;
	for (auto x : v) ss << x << ' ';
	auto s = ss.str();
	out << s.substr(0, s.length() - 1) << endl;
	return out;
}

//// start up ////
void solve();


int main()
{
	solve();
	return 0;
}

////////////////////
/// template end ///
////////////////////

void solve()
{
	int testcases = 1;
	REP(testcase, testcases)
	{
		READ(int, n, u, v, m);
		vector<int> usa(2 * n + 2, n), neko(2 * n + 2, n);
		vector<int> usamap(1000001, -1), nekomap(1000001, -1);
		REP(i, n) REP(j, n) { usamap[read<int>()] = i << 16 | j; }
		REP(i, n) REP(j, n) { nekomap[read<int>()] = i << 16 | j; }

		int win = 0;
		REP(i, m)
		{
			READ(int, d);
			if (!win)
			{
				REP(k, 2)
				{
					const vector<int> &mp = !k ? usamap : nekomap;
					vector<int> &te = !k ? usa : neko;
					int &re = !k ? u : v;
					int c = 0;
					if (mp[d] == -1) continue;
					int i = mp[d] >> 16, j = (short)mp[d];
					if (--te[i] == 0) { c++; } // たて
					if (--te[n + j] == 0) { c++; } // よこ
					if (i - j == 0) if (--te[2 * n] == 0) { c++; } // ななめ
					if (i + j + 1 == n) if (--te[2 * n + 1] == 0) { c++; }
					if (n == 1) { c = min(c, 1); }
					re -= c;
					if (re <= 0) { win |= 1 << k; }
				}
			}
		}

		switch (win)
		{
		case 1: WRITE("USAGI"); break;
		case 2: WRITE("NEKO"); break;
		default: WRITE("DRAW"); break;
		}
	}
}
```