After riding her bike for a couple hours, Mary always uploads her route information into her public online social network service through her smartphone. This is great for Jake, Mary’s personal trainer, because he can assess the performance of Mary from the commodity of his own home. But, can he really?

At a regular time interval, the app takes a sample of the current latitude and longitude, translates it to a simplified three-dimensional cartesian coordinate system and finally stores these coordinates. In this simplified system, x represents a horizontal plane, y a vertical (height) plane, and z a depth plane. After reading k samples in order, Jake can have a pretty good idea of what the route Mary rode looked like.

Mary just uploaded her last route information. Today, Mary was supposed to do a Wavy route (look at the image below for reference). That is, she  was supposed to ride uphill (non-decreasingly) until some height, and then go downhill, never going up again (non-increasingly). Jake says this will strengthen her legs. After going through some samples of her route, Jake lost track. Help him! Write a program that given k samples of Mary’s last route, outputs whether she rode as she was supposed to.

Input

The input contains k + 1 lines. The first line contains k (1 <= k <= 100), the number of samples the app took. Then follow k lines. The i-th line contains three integers xi, yi, and zi (-500 <= xi, yi, zi <= 500), the three-dimensional cartesian coordinates.

Output

If Mary did a Wavy Route, output “YES SHE DID”. If she did not, output “NO SHE DID NOT”. In any case, do not include quotes (“) in your output.

Example

Input:
5
1 1 1
1 2 2
1 3 3
1 2 4
1 1 5

Output:
YES SHE DID

Input:
5
1 1 1
1 2 2
1 3 3
1 4 4
1 5 5

Output:
NO SHE DID NOT