Distance Conditions for Four Points

Time limit2sMemory limit128 MB

Summary

Given all pairwise distances among four points as a 4x4 integer matrix, decide if distinct points realizing these distances exist in 3D space.

Level: Medium7 of 10
Topics: Geometry, Math, Implementation
Solved: No attempts yet

Problem

A 4 by 4 matrix gives the distances between four points. Determine whether four distinct points can be placed in three-dimensional Euclidean space so that all of the given distances hold at the same time.

Input

The input consists of 4 lines. Each line contains 4 integers. The j-th integer on the i-th line is the distance between point i and point j.

The i-th integer on the i-th line is always 0, and the j-th integer on the i-th line equals the i-th integer on the j-th line. When i and j are different, the value is a positive integer no greater than 10.

Output

Print YES if the given distances can describe four points, and print NO otherwise.

Hint

If every pairwise distance is 1, the four points can be placed at the vertices of a regular tetrahedron.

Examples5

Example 1
Input
```
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
```
Expected output
```
YES
```
Example 2
Input
```
0 1 2 3
1 0 1 2
2 1 0 1
3 2 1 0
```
Expected output
```
YES
```
Example 3
Input
```
0 1 2 4
1 0 1 2
2 1 0 1
4 2 1 0
```
Expected output
```
NO
```
Example 4
Input
```
0 6 6 3
6 0 4 5
6 4 0 4
3 5 4 0
```
Expected output
```
YES
```
Example 5
Input
```
0 6 6 2
6 0 4 5
6 4 0 4
2 5 4 0
```
Expected output
```
NO
```