삼원색
시간 제한3초메모리 제한256 MB
최대 25,000개의 색칠된 직사각형을 겹치는 부분은 다시 칠하지 않는다는 규칙으로 칠한 뒤, 일곱 가지 색 영역 각각의 넓이를 구합니다.
문제
x축, y축으로 이루어진 평면 위에 직사각형들이 있다. 민성이는 거대한 프린터기로 이 평면 위의 직사각형들을 색칠하려고 한다.
민성에게는 시안, 노랑, 자홍색, 세 가지 색의 잉크가 있다. 어떤 직사각형은 시안색으로, 어떤 직사각형은 노랑색으로, 또 다른 어떤 직사각형은 자홍색으로 칠할 수 있다.
두 개 이상의 직사각형 영역이 겹치면 민성이가 가진 세 잉크의 색이 아닌 다른 색의 영역이 나타날 수 있다. 다음 그림은 시안, 노랑, 자홍색을 섞었을 때 나타날 수 있는 색이다.
\
그림 1: 감산혼합의 3원색 CMYK.
즉 빨간색은 자홍색과 노란색이, 초록색은 노란색과 시안색이, 파란색은 자홍색과 시안색이, 검은색은 자홍색과 노란색과 시안색이 동일한 비율로 섞인 색이다.
민성이는 잉크를 아끼기 위해 한번 어떤 색으로 칠한 곳은 이후에 같은 색의 겹치는 직사각형 영역이 나타나더라도 한 번만 칠하기로 했다. 예를 들어 (0, 0)부터 (2, 2)까지의 영역에 노란색을 칠한 뒤 다시 (1, 1)부터 (3, 3)까지 노란색을 칠해야 하는 상황이 왔다면, (1, 1)부터 (2, 2)까지는 이미 노란색이 칠해져 있으므로 다시 노란색을 덧칠하지 않는다. 이렇게 하면 3원색이 섞이는 비율이 항상 같기 때문에, 민성이는 잉크를 아끼면서 위 그림에 나오지 않은 색이 등장할 일도 없어진다.
서로 다른 색으로 칠할 직사각형들이 주어졌을 때, 민성이가 주어진 색대로 모두 칠한 뒤 각 색깔별 영역의 넓이를 민성이가 일일이 색칠하기 전에 미리 구하고자 한다.
입력
첫 번째 줄에 입력받을 직사각형의 개수 N이 주어진다. (1 ≤ N ≤ 25,000)
두 번째 줄부터 N개의 줄에 걸쳐 각 직사각형의 정보를 나타내는 정수 x1, y1, x2, y2와 문자 c가 공백으로 구분되어 주어진다. (-108 ≤ x1 < x2 ≤ 108, -108 ≤ y1 < y2 ≤ 108)
이는 해당하는 직사각형이 (x1, y1), (x1, y2), (x2, y2), (x2, y1)를 꼭짓점으로 가지고 c에 해당하는 색으로 영역을 칠함을 의미한다.
모든 c는 1글자짜리 문자로, “C”(시안), “M”(자홍), “Y”(노랑) 중 하나이다.
출력
첫 번째 줄에 일곱 개의 정수 Sc, Sm, Sy, Sr, Sg, Sb, Sk를 공백으로 구분하여 출력한다. 각각 시안색 영역의 넓이, 자홍색 영역의 넓이, 노란색 영역의 넓이, 빨간색 영역의 넓이, 초록색 영역의 넓이, 파란색 영역의 넓이, 검정색 영역의 넓이를 의미한다. (CMY RGB K)
(0,0), (1,0), (1,1), (0,1)을 꼭짓점으로 가지는 직사각형의 넓이는 1이다.