eolymp
bolt
Try our new interface for solving problems
Problems

Fractal Cake

Fractal Cake

Time limit 1 second
Memory limit 64 MiB

Fyodor celebrates his birthday today. Before the guests come he decorates a cake with chocolate cream in a special way. At the beginning cake looks like a square divided into 4 equal white square parts. Fyodor calls fractalization the following sequence of actions. All the little squares of cake get united into groups of 2x2 so that there are no ungrouped fragments. After that each small square is divided into 4 equal squares so that group of 2x2 becomes a group of 4x4. As the last action 4 squares in the middle of each group are filled with chocolate. Fyodor does not stop at one fractalization and repeats it N times, even when he has to use a microscope. Illustration below shows the initial cake, first fractalization result, and the cake after the fifth fractalization:

Now Fyodor wants to cut pieces of cake with beautiful patterns for guests, but it is difficult to assess beauty of a piece looking at the whole cake. Fyodor wants a program that will quickly show the pattern of rectangular part of the cake.

Input data

Single line at the input contains five non-negative integers: N, R_1, R_2, C_1, C_2. N – the number of fractalization iterations (N < 20), R_1 and R_2 – first and last rows, C_1 and C_2 – first and last columns of the part. Following restrictions are also met: R_1R_2, C_1C_2; 0R_2 - R_1, C_2 - C_1 < 100; 0R_1, R_2, C_1, C_2 < 2N + 1.

Output data

Output should contain R_2 - R_1 + 1 lines each containing C_2 - C_1 + 1 characters. Each symbol corresponds to a square and should be 1 in case it’s filled with chocolate and 0 otherwise.

Examples

Input example #1
1 0 3 0 3
Output example #1
0000
0110
0110
0000