적의 적은 나의 아군

세상은 다음과 같은 법칙이 있다.

1. 적의 적은 나의 아군

2. 적의 아군은 나의 적

3. 아군의 적은 나의 적

4. 아군의 아군은 나의 아군

전골국의 명장, 재원장군은 다른 국가간의 관계를 파악하여 전투 전략을 세우려고 한다.

하지만 복잡한 국가 관계에서 이를 파악하기에는 쉽지 않다.

선견지명이 뛰어난 재원장군은 각 국가들간의 확실한 정보들을 미리 파악해 놓았다.

다만 모든 관계가 아닌 일부 관계만 파악했으며, 서로간의 관계가 아군인지 적인지 파악한 상황이다.

재원장군의 참모인 당신은 국가간의 관계를 질문받을 경우, 위 법칙을 이용하여 어떠한 상황인지 답을 주어야 한다.

당신의 능력으로 재원장군을 역사에 남을 명장으로 만들어주자.

입력

첫 줄에 관계의 수 N이 주어진다. (1≤N≤50,000)

그 다음 N줄에 걸쳐서 각 줄마다 국가명 S₁, 국가명 S₂, 관계정보 R이 공백을 구분으로 주어진다.

이는 S₁과 S₂의 서로의 관계가 R이라는 뜻이며 관계정보 R은 항상 'E'아니면 'A'가 주어지며 'E'는 적 관계, 'A'는 아군 관계를 의미한다.

다음 질의의 수 Q가 주어진다. (1≤Q≤100,000)

그 다음 Q줄에 걸쳐서 각 줄마다 국가명 S₁, 국가명 S₂가 공백을 구분으로 주어진다.

국가명 S₁, S₂은 알파벳 대소문자로 최대 10자까지 주어지며 대소문자를 구분하며, 관계에 나오지 않은 국가명도 질의로 들어올 수 있다.

출력

Q개의 질문에 따라

아군 관계일 경우 ALLY,

적 관계일 경우 ENEMY,

존재하지 않은 국가명인 경우 WHAT,

존재하지만 서로 관계를 모를 경우 IDK,

법칙이 어긋난 난전 관계일 경우 DOGFIGHT 를 각 줄마다 출력한다.

예제

출처

eva

적의 적은 나의 아군 1s 128MB