M. Painter
time limit per test
1.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Little G is a painter and is painting on a 2D plane. Each integral point has a color character and the initial color characters for all integral points are "."(ASCII = 46). Now Little G is planning to do some operations one by one, where each operation is in one of the following three types:

  1. "Circle $$$x\,y\,r\,col$$$", which means to draw a circle. Formally, change the color characters to $$$col$$$ for these points $$$(u,v)$$$ that $$$(u-x)^2+(v-y)^2\le r^2$$$.
  2. "Rectangle $$$x_1\,y_1\,x_2\,y_2\,col$$$", which means to draw a rectangle. Formally, change the color characters to $$$col$$$ for these points $$$(u,v)$$$ that $$$x_1 \le u \le x_2, y_1 \le v \le y_2$$$.
  3. "Render $$$x_1\,y_1\,x_2\,y_2$$$", which means to render the image of given region. Formally, print the color characters for these points $$$(u,v)$$$ that $$$x_1 \le u \le x_2, y_1 \le v \le y_2$$$.

But now, Little G is busy replying clarifications, so could you help him and be the painter?

Input

The first line contains one integers $$$n$$$ ($$$1\le n\le 2000$$$), denoting the number of operations.

Following $$$n$$$ lines each contains one operation, which is in one of the following three types:

  1. "Circle $$$x\,y\,r\,col\,(0 \le |x|,|y|,r \le 10^9)$$$", which means to draw a circle. Formally, change the color characters to $$$col$$$ for these points $$$(u,v)$$$ that $$$(u-x)^2+(v-y)^2\le r^2$$$.
  2. "Rectangle $$$x_1\,y_1\,x_2\,y_2\,col\,(-10^9 \le x_1 \le x_2 \le 10^9, -10^9 \le y_1 \le y_2 \le 10^9)$$$", which means to draw a rectangle. Formally, change the color characters to $$$col$$$ for these points $$$(u,v)$$$ that $$$x_1 \le u \le x_2, y_1 \le v \le y_2$$$.
  3. "Render $$$x_1\,y_1\,x_2\,y_2\,(-10^9 \le x_1 \le x_2 \le 10^9, -10^9 \le y_1 \le y_2 \le 10^9)$$$", which means to render the image of given region. Formally, print the color characters for these points $$$(u,v)$$$ that $$$x_1 \le u \le x_2, y_1 \le v \le y_2$$$.

It is guaranteed that all of the $$$x,y,r,x_1,y_1,x_2,y_2$$$ above are integers.

It is guaranteed that the sum of the rendering region areas(which equal $$$(x_2 - x_1 + 1)\times(y_2 - y_1 + 1)$$$) doesn't exceed $$$10^4$$$, and that $$$col$$$ denotes visible characters, whose ASCII codes are between $$$33$$$ and $$$126$$$.

Output

For each rendering operation "Render $$$x_1\,y_1\,x_2\,y_2$$$", print $$$y_2 - y_1 + 1$$$ lines each containing one string of length $$$x_2 - x_1 + 1$$$, denoting the region image(from row $$$y_2$$$ to row $$$y_1$$$).

Example
Input
7
Circle 0 0 5 *
Circle -2 2 1 @
Circle 2 2 1 @
Rectangle 0 -1 0 0 ^
Rectangle -2 -2 2 -2 _
Render -5 -5 5 5
Render -1 0 1 2
Output
.....*.....
..*******..
.**@***@**.
.*@@@*@@@*.
.**@***@**.
*****^*****
.****^****.
.**_____**.
.*********.
..*******..
.....*.....
@*@
***
*^*