ASCII Art

Some users still work in monochrome text terminals instead of color graphics. For them, ASCII art is the only way to draw pictures. As part of a project to implement Doom in ASCII, you must build a renderer that fills triangles with characters.

The input contains triangles and viewing data. Each triangle gives the X, Y, and Z coordinates of its three vertices and a single character colour. Here colour is the character drawn on the screen. If colour is E, that region is filled with E.

The screen size S is an S by S square grid of characters with uniform spacing. The coordinate system is right handed. Standing on the positive Z axis and looking toward the origin, positive Y points up and positive X points right.

If S is 4, the screen is a 4 by 4 grid. Vertex coordinates are real numbers from 0 through 4. Pixel centers are at 0.125, 0.375, and so on, following (2i+1)/(2S). Color a pixel when its center lies inside or on the border of a triangle.

You render several scenes. Each scene starts with S T. S is the screen size (0 ≤ S ≤ 40) and T is the number of triangles (0 < T ≤ 20). Input ends when both S and T are 0.

Next come T lines. Each line has one non-space character colour and nine floats X1 Y1 Z1 X2 Y2 Z2 X3 Y3 Z3 for the three vertices. Items on a line are separated by a single space.

The following line gives the camera position X Y Z, then the look-at point X Y Z, then the field of view in degrees and the near and far limits.

For each scene, print a blank line, a row of S asterisks, the S rendered rows, and another row of S asterisks.

Near triangles hide far ones. You may assume every triangle lies inside the viewing volume defined by the field of view and the near and far limits.