시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 128 MB 39 10 6 30.000%

문제

매우(거의 무한할 정도로) 큰 공장이 하나 있다. 이 공장은 벽으로 둘러싸인 사각형 모양을 하고 있다. 이 공장에는 N(1≤N≤100)개의 굴뚝이 있는데, 각각의 굴뚝들은 어떤 특정한 모양을 하고 있다. 몇 개의 굴뚝들은 서로 같은 모양을 하고 있기도 하다.

이 공장에서는 최신 기술을 이용한 개발이 진행되고 있는데, 이 기술의 보안을 유지하기 위해서 한 대의 감시 로봇을 사용하고 있다. 감시 로봇은 x축을 따라서 움직이게 되는데, 로봇의 위치가 어디인지를 알아야 할 필요가 있다. 그런데 로봇 안에 들어있는 위치 센서가 좋지 않을뿐더러, 건물의 크기가 매우 크기 때문에, 위치를 직접 알려주지는 못하고, 로봇이 굴뚝을 관찰한 순서가 주어지게 된다.

로봇은 우선 x축 위에서, 왼쪽(x좌표가 음의 무한대인 쪽)을 바라보고 서 있다. 그리고 로봇은 시계방향으로 오른쪽(x좌표가 양의 무한대인 쪽)까지 돌게 된다. 로봇은 돌면서 자신이 보게 되는 굴뚝의 모양을 차례대로 알려주게 된다. 모든 굴뚝들의 높이는 같기 때문에, 로봇이 보고 있는 방향에 여러 굴뚝이 있다면 제일 앞에 있는 굴뚝만을 보게 된다.

공장 측에서는 이와 같은 방법을 이용하면 로봇의 위치를 구해낼 수 있을 거라 생각했지만, 답이 유일하게 나오는 것이 아니라 여러 구간의 형태로 나옴을 알게 되었다. 따라서 공장 측에서는, 이와 같은 구간들을 구하려고 한다.

로봇이 굴뚝을 관찰한 순서와 각 굴뚝의 위치가 주어졌을 때, 로봇이 있을 수 있는 위치를 구해내는 프로그램을 작성하시오.

입력

첫째 줄에 굴뚝의 개수 N이 주어진다. 다음 줄에는 로봇이 굴뚝을 관찰한 순서대로 굴뚝의 모양이 주어진다. 건물에 없는 굴뚝을 본 경우나, 굴뚝을 N개 미만으로 본 경우는 입력으로 주어지지 않는다. 다음 N개의 줄에는 각 굴뚝의 모양을 나타내는 문자와, 굴뚝의 x(-100≤x≤100), y(0<y≤100)좌표가 주어진다. 굴뚝의 모양은 알파벳 대문자로 표현되며, 모든 좌표는 정수이다.

출력

첫째 줄에 구간의 개수 K가 주어진다. 다음 K개의 줄에는 두 개의 실수로 구간의 왼쪽, 오른쪽 끝점을 출력한다. 건물의 크기는 매우 크다고(무한하다고) 가정하며, 건물의 양 끝점의 경우에는 좌표 대신에 *을 출력한다. 좌표를 출력할 때에는 소수점 아래 넷째 자리까지 출력한다(다섯째 자리에서 반올림)

예제 입력

4
CDDC
C 0 7
D 4 5
C -2 1
D -2 3

예제 출력

3
* -11.0000
-11.0000 -3.5000
14.0000 *

힌트