Surveillance Robot

A very large rectangular factory is surrounded by walls. Inside the factory there are N (1 <= N <= 100) chimneys, and each chimney has one shape. Several chimneys may have the same shape.

The factory uses one surveillance robot that moves on the x-axis. Its position sensor is inaccurate, so the robot cannot report its x-coordinate directly. Instead, we are given only the order of chimney shapes that the robot observes.

The robot starts at some point on the x-axis while facing left, toward x-coordinate negative infinity. It then rotates clockwise until it faces right, toward x-coordinate positive infinity. During this rotation, it reports the shapes of the chimneys it can see in order. Since all chimneys have the same height, if multiple chimneys lie in the same direction, only the closest one is visible.

This information may not determine a unique position for the robot. The possible positions form several intervals on the x-axis.

Given the order of shapes observed by the robot and the position of every chimney, find every interval on the x-axis where the robot could have been located.

The first line contains the number of chimneys N.

The second line contains a string of chimney shapes in the order observed by the robot. Inputs where the robot observes a shape that does not exist, or observes fewer than N chimneys, are not given.

Each of the next N lines contains an uppercase letter representing a chimney shape, followed by the chimney coordinates x and y. The coordinates satisfy -100 <= x <= 100 and 0 < y <= 100, and all coordinates are integers. No two chimneys have the same coordinates.

On the first line, print the number K of possible intervals.

On each of the next K lines, print two real numbers: the left and right endpoints of an interval. The factory is considered infinitely wide, so if an interval extends to infinity on either side, print * instead of that endpoint coordinate. Relative error up to 10^-4 is accepted.