Problem:


Problem D: Clock Hands

We have an analog clock whose three hands (the second hand, the minute hand and the hour hand) rotate quite smoothly. You can measure two angles between the second hand and two other hands.

Write a program to find the time at which "No two hands overlap each other" and "Two angles between the second hand and two other hands are equal" for the first time on or after a given time.

Figure D.1. Angles between the second hand and two other hands

Clocks are not limited to 12-hour clocks. The hour hand of an H-hour clock goes around once in H hours. The minute hand still goes around once every hour, and the second hand goes around once every minute. At 0:0:0 (midnight), all the hands are at the upright position.

Input

The input consists of multiple datasets. Each of the dataset has four integers H, h, m and s in one line, separated by a space. H means that the clock is an H-hour clock. h, m and s mean hour, minute and second of the specified time, respectively.

You may assume 2 ≤ H ≤ 100, 0 ≤ h < H, 0 ≤ m < 60, and 0 ≤ s < 60.

The end of the input is indicated by a line containing four zeros.

Figure D.2. Examples of H-hour clock (6-hour clock and 15-hour clock)

Output

Output the time T at which "No two hands overlap each other" and "Two angles between the second hand and two other hands are equal" for the first time on and after the specified time.

For T being ho:mo:so (so seconds past mo minutes past ho o'clock), output four non-negative integers ho, mo, n, and d in one line, separated by a space, where n/d is the irreducible fraction representing so. For integer so including 0, let d be 1.

The time should be expressed in the remainder of H hours. In other words, one second after
(H − 1):59:59 is 0:0:0, not H:0:0.

Sample Input

12 0 0 0
12 11 59 59
12 1 56 0
12 1 56 3
12 1 56 34
12 3 9 43
12 3 10 14
12 7 17 58
12 7 18 28
12 7 23 0
12 7 23 31
2 0 38 29
2 0 39 0
2 0 39 30
2 1 6 20
2 1 20 1
2 1 20 31
3 2 15 0
3 2 59 30
4 0 28 48
5 1 5 40
5 1 6 10
5 1 7 41
11 0 55 0
0 0 0 0

Output for the Sample Input

0 0 43200 1427
0 0 43200 1427
1 56 4080 1427
1 56 47280 1427
1 57 4860 1427
3 10 18600 1427
3 10 61800 1427
7 18 39240 1427
7 18 82440 1427
7 23 43140 1427
7 24 720 1427
0 38 4680 79
0 39 2340 79
0 40 0 1
1 6 3960 79
1 20 2400 79
1 21 60 79
2 15 0 1
0 0 2700 89
0 28 48 1
1 6 320 33
1 6 40 1
1 8 120 11
0 55 0 1



Sample input:
12 0 0 0
12 11 59 59
12 1 56 0
12 1 56 3
12 1 56 34
12 3 9 43
12 3 10 14
12 7 17 58
12 7 18 28
12 7 23 0
12 7 23 31
2 0 38 29
2 0 39 0
2 0 39 30
2 1 6 20
2 1 20 1
2 1 20 31
3 2 15 0
3 2 59 30
4 0 28 48
5 1 5 40
5 1 6 10
5 1 7 41
11 0 55 0
0 0 0 0


Sample output:
0 0 43200 1427
0 0 43200 1427
1 56 4080 1427
1 56 47280 1427
1 57 4860 1427
3 10 18600 1427
3 10 61800 1427
7 18 39240 1427
7 18 82440 1427
7 23 43140 1427
7 24 720 1427
0 38 4680 79
0 39 2340 79
0 40 0 1
1 6 3960 79
1 20 2400 79
1 21 60 79
2 15 0 1
0 0 2700 89
0 28 48 1
1 6 320 33
1 6 40 1
1 8 120 11
0 55 0 1

Submission status: Accepted

Solution code:
import sys
def gcd(m, n):
    while n:
        m, n = n, m % n
    return m
readline = sys.stdin.readline
write = sys.stdout.write
def solve():
    f = lambda h, m, s: 3600*h + 60*m + s
    H, h, m, s = map(int, readline().split())
    if H == 0:
        return False
    d0 = f(h, m, s)
    M = f(H, 0, 0)
    res = []
    for h0 in range(H):
        for m0 in range(60):
            p = 3600*h0 + 60*m0 + 60*H*m0; q = 119*H-1
            for d in [-3600*H, 0, 3600*H]:
                p1 = p + d; q1 = q
                g = gcd(p1, q); p1 //= g; q1 //= g
                if 0 <= p1 < 60*q1:
                    if H*(60*m0*q1 + p1) != q1*(3600*h0 + 60*m0) + p1:
                        res.append((f(h0, m0, 0) + p1/q1, h0, m0, p1, q1))
    res.sort(key = lambda x: (x[0] - d0) % M)
    _, h, m, p, q = res[0]
    write("%d %d %d %d\n" % (h, m, p, q))
    return True
while solve():
    ...