Under construction

Still being built. Things may change

Farmer John's View

Time limit1sMemory limit1024 MB

Summary
Given N arcs on a 360-degree circle, each written in degrees, minutes, and seconds, find the total arc-seconds covered by at least one arc.
Level

Medium4 of 10

Topics
Intervals, Sorting, Prefix sum
Solved
No attempts yet

Problem

Farmer John wants to leave the dull scenery beside his old farm. He has decided to move from the Wisconsin plains to a new location near the mountains. From there, he looks around in all 360 degrees. Some directions show mountains and others show none. He wants to know what fraction of his view is mountains.

N mountain ranges (1≤N≤10001 \le N \le 1000) surround the new location. Each range appears as a contiguous arc. Think of the view as a circle split into 360 small arcs of 1 degree each. Each degree splits into 60 arc-minutes, and each arc-minute splits into 60 arc-seconds. To record the exact span of each range, Farmer John writes down its starting and ending angles. For example:

Range #34 starts at 45 degrees, 2 minutes, 59 seconds, and ends at 120 degrees, 10 minutes, and 0 seconds.

This description does not say whether the range curves clockwise or counterclockwise. However, no range covers 180 degrees or more, so the direction is unambiguous. The sample range above therefore covers 270,421 arc-seconds. Ranges may overlap. Farmer John wants the total number of arc-seconds in his view that are occupied by mountains.

Input

The first line contains a single integer N.

Each of the next N lines contains 6 space-separated integers. The first three are the degree, minute, and second of the starting angle. The last three are the degree, minute, and second of the ending angle.

Output

Print a single integer: the total number of arc-seconds in the view that are occupied by mountains.

Hint

The first two ranges overlap slightly and cover a combined 270421 arc-seconds. The third range covers 3600 arc-seconds.

Examples1

  1. Example 1

    Input
    3
    45 2 59 60 30 30
    50 10 2 120 10 0
    355 0 0 356 0 0
    
    Expected output
    274021