ASCII Art

Interview

Time limit1sMemory limit512 MB

Summary

Read an N by M grid of RGB triples, apply the given intensity formula, map each value to a character via the threshold table, and print the grid.

Level: Easy2 of 10
Topics: Implementation, Math, Array
Solved: No attempts yet

Problem

A picture drawn with ASCII characters, like the one above, is called 'ASCII art'. Common image files (.jpg, .png, and so on) are stored by dividing the image into a two-dimensional grid of pixels at its resolution and keeping each pixel's information. That information has several parts, but the 'R', 'G', and 'B' values indicate how much of each of the three colors 'Red', 'Green', and 'Blue' is mixed in, and each value is an integer between 0 and 255 inclusive.

ASCII art draws a picture by assigning one character to each pixel of a grid, so any image file can be redrawn as ASCII art. Unlike an image file, which can have many colors, ASCII art cannot adjust color and can only adjust the shade within each pixel. If the original image is grayscale, the result can look fairly similar, but if it is made of many colors, it is hard to preserve the feel of the original.

However, if you can convert the original image to grayscale with a filter, and then convert it to ASCII art, the quality can improve. The following shows an example of one image turning into ASCII art.

To convert an image to grayscale, an Intensity function decides the ratio in which the three colors R, G, and B are mixed for each pixel. The Intensity function takes integers R, G, and B between 0 and 255 and returns one integer, and is defined below.

$I(R,G,B)=2126R+7152G+ 722B$

The result of this function is between 0 and 2,550,000 inclusive. A higher value means a pixel closer to white, and a lower value means a pixel closer to black. ASCII art is completed by converting each pixel, which the intensity function turned into a single integer, according to the table below.


Intensity	Character	ASCII code
0 to less than 510,000	#	35
510,000 to less than 1,020,000	o (lowercase letter)	111
1,020,000 to less than 1,530,000	+	43
1,530,000 to less than 2,040,000	-	45
2,040,000 or more	.	46

If you have followed everything so far, you can build a fine ASCII Art Generator.

Given the resolution of an original image and the R, G, and B values of each pixel, write a program that prints the ASCII art of the image.

Input

The first line gives the height N and the width M of the picture. (1 ≤ N, M ≤ 400)

From the second line to the N+1-th line, each line contains 3M integers.

Among these, the 3j-2-th, 3j-1-th, and 3j-th integers on the i+1-th line mean R(i,j), G(i,j), B(i,j) respectively, and every value is between 0 and 255 inclusive.

Here R(i,j) is the R value of the pixel in row i, column j, G(i,j) is the G value of the pixel in row i, column j, and B(i,j) is the B value of the pixel in row i, column j.

Output

Print the given picture converted to ASCII art, in the form of an N×M grid.

Be careful not to print unneeded spaces at the end of lines.

Hint

The original picture of the sample looks like this.

Examples1

Example 1

Input

16 11
255 252 255 255 254 255 249 255 248 245 255 244 254 255 249 255 241 255 255 237 255 255 244 253 255 255 239 255 255 243 255 249 255
255 246 255 238 255 251 213 255 241 83 145 106 229 255 242 235 255 255 223 255 255 226 255 255 244 255 253 255 250 248 255 251 255
255 244 255 230 255 248 191 255 224 64 161 92 74 152 100 191 255 236 178 255 244 55 158 115 222 255 249 254 255 253 255 255 251
251 248 255 244 255 248 92 147 92 74 163 83 60 168 83 53 165 89 59 166 96 64 161 94 77 155 97 223 255 234 241 255 246
240 255 255 255 251 255 255 253 241 217 255 217 60 170 83 64 160 86 216 255 220 219 255 220 62 161 79 69 161 96 238 255 251
240 255 253 255 246 255 255 249 255 227 255 246 193 255 216 74 156 94 226 255 241 91 148 115 63 159 98 199 255 230 239 255 250
254 255 253 248 255 255 238 255 255 224 255 245 92 153 93 82 153 85 208 255 235 207 255 250 218 255 251 237 255 248 252 255 253
255 246 255 252 255 246 241 255 224 122 137 78 117 131 52 75 115 19 94 150 61 112 139 88 255 247 243 255 237 255 255 248 255
255 240 255 255 244 216 128 91 13 239 186 92 135 85 0 119 95 0 217 197 82 246 184 101 174 57 39 255 219 243 255 236 255
255 229 250 150 68 47 177 65 2 255 158 83 255 161 92 255 177 101 165 73 0 194 57 0 221 43 15 195 45 56 255 235 253
255 224 238 171 63 63 202 46 33 241 31 16 241 29 18 195 42 28 169 57 37 255 213 193 230 27 20 215 40 45 255 231 239
255 227 232 163 55 68 209 37 59 255 9 39 255 9 36 214 37 63 161 61 85 255 212 236 233 30 52 224 38 51 255 237 239
255 240 236 149 58 65 212 36 56 255 15 40 255 15 36 210 35 52 160 58 79 173 50 78 215 30 61 202 39 58 255 240 243
255 250 243 255 236 234 193 44 46 238 30 30 234 29 26 200 45 40 255 217 217 255 219 225 183 51 65 255 224 236 255 244 248
243 255 249 255 246 242 255 230 228 171 56 53 179 54 48 180 53 47 173 54 50 158 63 61 255 237 236 255 248 249 255 255 255
245 255 253 255 254 255 255 243 250 255 242 251 255 233 242 255 222 234 255 219 228 255 236 237 254 255 250 229 255 255 240 255 255

Expected output

...........
...+.......
...++..+...
..+++++++..
....++..++.
.....+.++..
....++.....
...++o++...
..o-oo--o..
.oo---oooo.
.oooooo.oo.
.oooooo.oo.
.ooooooooo.
..oooo..o..
...ooooo...
...........