Nguồn đề - Free Contest 116: https://drive.google.com/file/d/1Tg9LLqaQNwr4bKtLjdk12CROPC8jQg/view?usp=sharing

Lời giải: https://drive.google.com/file/d/1zr9diHxjS3b9Ovc56hc90aVaITz9S6r2/view?usp=sharing

Cho n hạt, mỗi hạt chỉ mang một loại điện tích là điện tích dương hoặc điện tích âm. Hai hạt có cùng điện tích thì đẩy nhau, còn hai hạt khác điện tích thì hút nhau.

Trong một thí nghiệm, có q yêu cầu được đặt ra. Các yêu cầu thuộc một trong hai loại sau:

• Loại 1: Người làm thí nghiệm đem hai hạt lại gần nhau để xem chúng đẩy hay hút nhau.
• Loại 2: Người làm thí nghiệm được cho hai hạt và được yêu cầu hãy xác định xem hai hạt đó sẽ đẩy hay hút nhau dựa vào kết quả từ các yêu cầu trước.

Hãy in ra câu trả lời cho tất cả các yêu cầu loại 2.

Input

• Dòng đầu tiên gồm 2 số nguyên dương n và q ~(n, q \leq 10^5)~.
• Trong q dòng tiếp theo, mỗi dòng gồm một kí tự t và hai số nguyên dương a và b ~(a, b \leq n)~ là hai hạt được dùng trong mỗi yêu cầu.
  • Nếu t = 'A', yêu cầu loại này là loại 1 và kết quả thí nghiệm cho thấy hai hạt này hút nhau.
  • Nếu t = 'R', yêu cầu loại này là loại 1 và kết quả thí nghiệm cho thấy hai hạt này đẩy nhau.
  • Nếu t = 'Q', đây là yêu cầu loại 2.

Output

• Với mỗi yêu cầu loại 2, in ra một dòng với duy nhất một ký tự là câu trả lời.
  • Nếu hai hạt đẩy nhau, in ra 'R'.
  • Nếu hai hạt hút nhau, in ra 'A'.
  • Nếu không thể xác định được câu trả lời dựa trên các kết quả thu được, in ra '?'.

Sample Input 1

4 6
Q 1 2
R 1 2
A 2 3
A 1 4
Q 1 3
Q 2 4

Sample Output 1

? 
A 
A

Chấm điểm

• Subtask 1 (50% số test): ~n, q \leq 10^3~.
• Subtask 2 (50% số test): Không ràng buộc gì thêm.