Covering the Floor

Time limit1sMemory limit1024 MB

Summary

Given an X by Y floor and two rotatable rectangular sheets, find a placement of one or two sheets that covers the floor without cutting or folding, or report that it is impossible.

Level: Medium6 of 10
Topics: Geometry, Implementation, Brute force
Solved: No attempts yet

Problem

Mati is going to paint the ceiling of a room, and he needs to cover the floor so that paint drops do not stain it. For this he has two cardboard sheets. He will need them again later, so he does not want to cut or fold them. If one sheet can cover the whole floor, he does not use the second one.

The room and the sheets are all rectangles. The room is $X \times Y$ cm, the first sheet is $A_1 \times B_1$ cm, and the second sheet is $A_2 \times B_2$ cm.

Check whether the two sheets can cover the entire floor at once. Sheets may be rotated and may partly overlap each other, but they cannot extend past the edge of the floor. If covering is possible, find the placement of the sheets in the XY coordinate system, where the opposite corners of the room are $(0, 0)$ and $(X, Y)$ . If there are several placements, output any one of them.

Input

The first line contains two integers $X$ and $Y$ separated by a space ( $0 < X, Y \le 500$ ). The second line contains $A_1$ and $B_1$ , the dimensions of the first sheet, and the third line contains $A_2$ and $B_2$ , the dimensions of the second sheet, in the same format ( $0 < A_1, B_1, A_2, B_2 \le 500$ ).

Output

If the floor cannot be covered as required, print 'EI SAA' on a single line.

If the solution uses two sheets, print four integers on each of two lines. The first line gives the lower-left corner $X_{1,1}$ , $Y_{1,1}$ and the upper-right corner $X_{1,2}$ , $Y_{1,2}$ of the first sheet. The second line gives the corners $X_{2,1}$ , $Y_{2,1}$ , $X_{2,2}$ , $Y_{2,2}$ of the second sheet.

If only the first sheet is used, print its corner coordinates on the first line and 'Z' on the second line. If only the second sheet is used, print 'Z' on the first line and the corner coordinates of the second sheet on the second line.

Examples3

Example 1

Input

500 200
200 300
250 200

Expected output

0 0 300 200
250 0 500 200

Example 2
Input
```
400 300
200 400
300 400
```
Expected output
```
Z
0 0 400 300
```
Example 3
Input
```
300 400
400 100
300 300
```
Expected output
```
EI SAA
```