Animals

Interview

Time limit1sMemory limit1024 MB

Summary

Given N active time intervals, find whether they share a common moment and, if so, the longest interval when all animals are active.

Level: Easy3 of 10
Topics: Intervals, Implementation, Sorting, Greedy
Solved: No attempts yet

Problem

Lukas is interested in nature and knows at which time of day each animal and bird is active. He is organizing a hike with his classmates and wants to see $N$ animals. An animal can only be seen during the observable part of the day (from 9:00 to 20:59) while it is active. The hikers want to watch all the animals at the same time, that is, at a moment when every animal is active.

Help Lukas decide when it is best to go on the hike so that they see all the desired animals.

For each animal you are given the time interval of the day during which that animal is active (i.e. when it can be observed). Determine whether there is a time when all $N$ animals are active, and find the longest such interval. If two intervals are such that one begins exactly when the other ends, the intervals are considered not to overlap.

Input

The first line contains the number of animals $N$ that the students want to observe.

Each of the next $N$ lines contains four integers $h_s$ , $m_s$ , $h_e$ , $m_e$ describing an animal's active period during the day in hours and minutes: the start hour and minute, and the end hour and minute.

Each given interval is at least 1 minute long.

Output

If there is a time of day when all animals are active, print TAIP on the first line and, on the second line, the longest interval — from the earliest possible start to the latest possible end — during which all animals can be seen. The interval is given as four integers in the same format as the input.

If there is no common time when all animals are active, print NE.

Constraints

$1 \le N \le 1000$
$9 \le h_s, h_e \le 20$ , $0 \le m_s, m_e \le 59$

Examples2

Example 1

Input

3
10 15 20 15
9 10 13 34
12 0 13 35

Expected output

TAIP
12 0 13 34

Example 2
Input
```
2
12 15 20 10
20 10 20 50
```
Expected output
```
NE
```