TV 쇼 게임
시간 제한1초메모리 제한512 MB
k개의 램프에 빨강 또는 파랑을 칠해, n명의 참가자가 제시한 세 가지 색 추측이 모두 두 개 이상 적중하도록 만들고, 불가능하면 -1을 출력한다.
문제
TV 쇼 프로그램으로 유명한 다주다 씨는 가끔 관객에게 재미있는 게임을 제안하고 상품으로 선물을 준다. 이번 주에 그가 제안한 게임은 다음과 같다.
무대 위의 k(> 3)개의 램프는 게임이 시작될 때 모두 꺼져 있다. 편의를 위해 램프에 1부터 k까지 번호를 붙인다. 각 램프에는 빨간색 또는 파란색의 색이 있다. 하지만 램프를 켜기 전에는 그 색을 알 수 없다. 게임 참가자는 무작위로 램프 세 개를 골라 그 색을 맞힌다. 그런 다음 각 참가자는 고른 램프에 대해 예상한 색을 적은 종이를 진행자 다주다 씨에게 제출한다. 모든 램프가 켜지면 각 참가자는 예상한 색이 실제 램프의 색과 몇 개나 일치하는지 확인한다. 두 개 이상 일치하면 상품으로 좋은 선물을 받는다.
다주다 씨는 오늘 특별한 선물을 준비했다. 즉, 게임 참가자에게 받은 모든 종이를 검토한 뒤, 가능하면 모든 참가자가 선물을 받을 수 있도록 각 램프의 색을 조정하려고 한다.
위와 같이 예상한 색에 대한 정보가 주어질 때, 모든 참가자가 선물을 받을 수 있도록 모든 램프의 색을 조정할 수 있는지 판별하는 프로그램을 작성하라.
입력
프로그램은 표준 입력에서 입력을 읽는다. 입력의 첫 줄에는 두 정수 k와 n(3 < k ≤ 5,000, 1 ≤ n ≤ 10,000)이 주어지는데, k는 램프의 수이고 n은 게임 참가자의 수이다. 그다음 n개의 줄 각각에는 (l, c) 쌍 세 개가 주어지는데, l은 참가자가 고른 램프 번호이고 c는 그 램프에 대해 예상한 색을 나타내는 문자로 파란색은 B, 빨간색은 R이다. l과 c 사이에는 공백이 있고, 각 (l, c) 쌍도 아래 샘플과 같이 공백으로 구분된다.
출력
프로그램은 표준 출력에 출력을 쓴다. 모든 참가자가 선물을 받을 수 있도록 모든 램프의 색을 조정할 수 있으면 k개의 문자를 한 줄에 출력한다. i번째 문자는 i번째 램프의 색을 나타내며 파란색은 B, 빨간색은 R이다. 불가능하면 -1을 출력한다. 답이 여러 개면 그중 아무거나 출력해도 된다.