재활용 수거함 배정

뉴질랜드에 집 앞 분리수거 제도가 들어오면서 오클랜드부터 인버카길까지 모든 도시가 이 방식을 따라 하고 있다. 수거함은 빨강, 주황, 노랑, 초록, 파랑 다섯 가지 색이고, 재활용 대상 폐기물도 플라스틱, 유리, 알루미늄, 강철, 신문지 다섯 가지로 정해졌다. 도시끼리 협의한 적이 없어서 어느 색 수거함에 어떤 폐기물을 넣을지는 도시마다 제각각이다.

정부는 보건, 복지, 교육 개편 같은 당장의 자잘한 문제를 정리하고 나서 다음 과제를 찾고 있다. 환경잡동사니부 장관은 "고형 폐기물의 수거함 색 배정 정규화 법안"을 국회에 내려고 하는데, 그러려면 먼저 자신이 밀 배정안을 정해야 한다. 장관은 (적어도 가끔은) 민주주의를 믿는 사람이라 이 제도를 쓰는 도시를 모두 조사했다. 그 결과를 바탕으로 나머지 지역에 강제했을 때 충격이 가장 작은 배정안, 즉 지금의 배정에서 바꿔야 하는 횟수의 합이 가장 적은 배정안을 정하려 한다. 어떤 배정안을 채택하면 도시마다 그 배정안과 폐기물이 다른 수거함 하나당 한 번씩 바꿔야 한다.

여러 도시의 배정을 읽어서, 가능한 모든 배정안 중 전국에 적용했을 때 바꾸는 횟수가 가장 적은 배정안을 구하는 프로그램을 작성하시오. 가장 좋은 배정안은 항상 하나뿐이다.

입력은 여러 개의 블록으로 이루어진다. 한 블록은 여러 줄로 이루어지고, # 한 글자만 있는 줄로 끝난다. 파일 전체도 # 한 글자만 있는 줄로 끝난다.

블록의 각 줄은 도시 하나의 배정이며, 배정 다섯 개를 쉼표로 구분해 적는다. 배정 하나는 색/폐기물 꼴이다. 색은 r(빨강), o(주황), y(노랑), g(초록), b(파랑) 중 하나이고, 폐기물은 P(플라스틱), G(유리), A(알루미늄), S(강철), N(신문지) 중 하나다. 한 줄에는 다섯 색과 다섯 폐기물이 각각 정확히 한 번씩 나오며, 적는 순서는 도시마다 다를 수 있다.

입력의 블록마다 한 줄씩 출력한다. 각 줄에는 그 블록에서 전국 표준으로 삼아야 할 배정안을 적는다. 수거함은 r, o, y, g, b 순서로 쓰고 쉼표로 구분하므로, 각 줄은 r/폐기물,o/폐기물,y/폐기물,g/폐기물,b/폐기물 형식이 된다.