시간 제한메모리 제한제출정답맞힌 사람정답 비율
1 초 128 MB111100.000%

문제

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.

입력

Single line at the input contains five non-negative integers: NR1R2C1C2N – the number of fractalization iterations (N < 20), R1 and R2 – first and last rows, C1 and C2 – first and last columns of the part. Following restrictions are also met: R1 ≤ R2C1 ≤ C20 ≤ R2 - R1C2 - C1 < 1000 ≤ R1R2C1C2 < 2N + 1.

출력

Output should contain R2 - R1 + 1 lines each containing C2 - C1 + 1 characters. Each symbol corresponds to a square and should be 1 in case it’s filled with chocolate and 0 otherwise.

예제 입력 1

1 0 3 0 3

예제 출력 1

0000
0110
0110
0000

예제 입력 2

2 0 3 0 3

예제 출력 2

0000
0110
0111
0011

예제 입력 3

13 50 55 95 100

예제 출력 3

101111
100111
100111
101111
101101
100001