Make One Square

Interview

Time limit2sMemory limit512 MB

Summary

Given three rectangles that can each be rotated 90 degrees, decide whether they can tile one square exactly with no overlaps or gaps.

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

Problem

You are given three rectangles. Decide whether the three of them can be glued together, without overlapping, so that they fill exactly one square. Each rectangle may be rotated by 90 degrees, but it cannot be cut and it cannot be left out. The three areas together have to equal the area of the square.

For example, rectangles $8 \times 2$ , $1 \times 6$ and $7 \times 6$ fill an $8 \times 8$ square. The $8 \times 2$ piece covers a full row at the top, and the $1 \times 6$ and $7 \times 6$ pieces sit side by side in the remaining $8 \times 6$ region.

Three rectangles filling an 8x8 square

Input

The input consists of three lines.

The first line contains the width $w_1$ and the height $h_1$ of the first rectangle, separated by a space. ( $1 \le w_1, h_1 \le 100$ )

The second line contains the width $w_2$ and the height $h_2$ of the second rectangle. ( $1 \le w_2, h_2 \le 100$ )

The third line contains the width $w_3$ and the height $h_3$ of the third rectangle. ( $1 \le w_3, h_3 \le 100$ )

Output

Print $1$ on one line if the three rectangles can be put together to form a square, and $0$ if they cannot.

Examples6

Example 1
Input
```
8 2
1 6
7 6
```
Expected output
```
1
```
Example 2
Input
```
2 8
6 1
6 7
```
Expected output
```
1
```
Example 3
Input
```
1 1
1 1
1 1
```
Expected output
```
0
```
Example 4
Input
```
1 1
1 1
2 1
```
Expected output
```
1
```
Example 5
Input
```
3 1
3 1
3 1
```
Expected output
```
1
```
Example 6
Input
```
4 2
4 1
4 1
```
Expected output
```
1
```