실험 전하
면접 대비시간 제한2초메모리 제한512 MB
입자의 전하는 알 수 없고, 서로 끌어당김 또는 밀어냄 관측이 주어질 때 두 입자가 반드시 끌어당기는지, 반드시 밀어내는지, 아니면 둘 다 가능한지 판정한다.
문제
N개의 대전 입자가 있고, 각 입자는 양전하 또는 음전하를 띤다. 각 입자의 전하는 알려져 있지 않지만, 같은 전하를 띤 두 입자를 가까이 하면 서로 밀어내고, 다른 전하를 띤 두 입자를 가까이 하면 서로 끌어당긴다는 사실은 알려져 있다.
실험에서 Q개의 사건이 시간 순서대로 일어난다. 각 사건은 다음 두 종류 중 하나이다.
- 두 입자를 가까이 하고, 두 입자가 밀어내는지 끌어당기는지 주어진다.
- 두 입자를 가까이 할 때, 지금까지의 실험 관측을 바탕으로 두 입자가 밀어내는지, 끌어당기는지, 아니면 둘 다 가능한지 질문한다.
지금까지 주어진 모든 실험 관측과 일치하는 입자의 전하 배치가 적어도 하나 존재한다.
입력
프로그램은 표준 입력에서 입력을 읽는다.
입력의 첫 줄에는 두 정수 N과 Q가 주어진다. N은 대전 입자의 수, Q는 사건의 수이다.
이어서 Q개의 줄이 주어지고, 각 줄에는 문자 1개와 정수 2개가 있다. i번째 줄에는 Ti, Ai, Bi가 있다. Ti = ‘A’이면 입자 Ai와 Bi가 끌어당기는 1번 사건이고, Ti = ‘R’이면 입자 Ai와 Bi가 밀어내는 1번 사건이다. Ti = ‘Q’이면 입자 Ai와 Bi가 끌어당기는지 밀어내는지, 또는 둘 다 가능한지 묻는 2번 사건이다.
출력
프로그램은 표준 출력에 출력한다.
2번 사건마다 한 줄에 문자 하나를 출력한다. 전하가 끌어당기면 ‘A’, 밀어내면 ‘R’, 둘 다 가능하면 ‘?’를 출력한다.
제한
- 1 ≤ N, Q ≤ 105
- 1 ≤ Ai ≠ Bi ≤ N
- Ti = ‘A’, ‘R’, or ‘Q’