감시 로봇

매우 큰 직사각형 공장이 벽으로 둘러싸여 있다. 이 공장에는 N(1 <= N <= 100)개의 굴뚝이 있고, 각 굴뚝은 하나의 모양을 가진다. 서로 같은 모양을 가진 굴뚝이 여러 개 있을 수 있다.

공장에서는 기술 보안을 위해 x축 위를 움직이는 감시 로봇 한 대를 사용한다. 로봇의 위치 센서는 정확하지 않아서, 로봇의 x좌표를 직접 알 수 없다. 대신 로봇이 굴뚝들을 바라보며 관찰한 모양의 순서만 주어진다.

로봇은 x축 위의 어떤 위치에서 왼쪽, 즉 x좌표가 음의 무한대로 가는 방향을 바라본 채 시작한다. 그런 다음 시계방향으로 회전하여 오른쪽, 즉 x좌표가 양의 무한대로 가는 방향까지 바라본다. 회전하는 동안 로봇은 자신에게 보이는 굴뚝의 모양을 순서대로 보고한다. 모든 굴뚝의 높이는 같으므로, 같은 방향에 굴뚝이 여러 개 있으면 로봇은 가장 앞에 있는 굴뚝만 볼 수 있다.

이 정보만으로 로봇의 위치가 하나로 정해지지 않을 수 있다. 가능한 위치들은 x축 위의 여러 구간으로 나타난다.

로봇이 관찰한 굴뚝 모양의 순서와 각 굴뚝의 위치가 주어질 때, 로봇이 있을 수 있는 x축 위의 모든 구간을 구하라.

첫째 줄에 굴뚝의 개수 N이 주어진다.

둘째 줄에는 로봇이 관찰한 순서대로 굴뚝의 모양이 문자열로 주어진다. 존재하지 않는 모양을 관찰했거나, 관찰한 굴뚝 수가 N개보다 작은 경우는 입력으로 주어지지 않는다.

다음 N개의 줄에는 각 굴뚝의 모양을 나타내는 문자와 굴뚝의 좌표 x, y가 주어진다. -100 <= x <= 100, 0 < y <= 100이며, 모든 좌표는 정수이다. 굴뚝의 모양은 알파벳 대문자 하나로 주어진다. 두 굴뚝이 같은 좌표에 있는 경우는 없다.

첫째 줄에 가능한 구간의 개수 K를 출력한다.

다음 K개의 줄에는 각 구간의 왼쪽 끝점과 오른쪽 끝점을 실수 두 개로 출력한다. 공장의 가로 크기는 무한하다고 가정하므로, 구간이 무한히 뻗는 쪽의 끝점은 좌표 대신 *를 출력한다. 상대 오차는 10^-4까지 허용된다.