1262 : Painter

Description

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\), and in each row from \(x_1\) to \(x_2\)).

Sample

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

.....*.....
..*******..
.**@***@**.
.*@@@*@@@*.
.**@***@**.
*****^*****
.****^****.
.**_____**.
.*********.
..*******..
.....*.....
@*@
***
*^*

Hint

Source

Author

FUDAN