Checking Causality

Causality is a key idea in distributed systems. If one computer sends a message and another computer receives it, the send event must have happened before the receive event in real time. If every computer shared one global clock, the receive timestamp would always be greater than the send timestamp.

Distributed systems do not have such a clock. Each computer has its own clock, and those clocks may run at different speeds. The only reliable rule is local: on one computer, later events always receive strictly larger timestamps than earlier events. Because the clocks are independent, a message can be sent by one computer at time 50 and received by another computer at time 40, and a reply can still be sent and received in a way that is consistent.

You are given send and receive timestamps for several messages. For each timestamp set, determine whether the message order and the local timestamp order contradict causality. A contradiction exists when following message edges and increasing timestamps on each computer creates a directed cycle.

The input contains several timestamp sets. Each set starts with an integer n, the number of messages. The next n lines each contain four whitespace-separated values: the sending computer, the send time, the receiving computer, and the receive time.

Times are integers measured by the relevant computer's clock. Each computer is identified by one uppercase letter. A line containing the single integer 0 ends the input.

For each timestamp set, print one line. Print OK if there is no causality violation, or Bad if a violation exists.