Tanks a Lot

Imagine a car with a fuel tank large enough to hold any amount of gas you might need. The car travels along a circular route that has several gas stations on it. The total amount of gas across all stations is exactly enough to drive around the circuit once. Whenever you reach a station, you pour all of that station's gas into your tank.

Starting with an empty tank, it can be shown that there is always at least one station and one direction (clockwise or counterclockwise) from which you can complete a full lap and return to where you started.

Given the length of the circuit, the locations of the stations, and how many miles each station's gas lets you drive, determine every station and direction from which a full lap can be completed.

The input contains a sequence of test cases. Each test case begins with a line containing two positive integers $c$ and $s$: the total circumference of the circle in miles and the number of gas stations.

Next come $s$ pairs of integers $t$ and $m$ describing the stations. In each pair, $t$ (with $0 \le t \le c-1$) is the clockwise distance of the station from a fixed reference point on the circle, and $m$ is the number of miles you can drive using all of that station's gas. All station locations are distinct, and $c \le 100000$.

Within a test case, the sum of all $m$ values equals $c$.

The list of test cases ends with a line containing two zeros.

For each test case, print Case X:, where $X$ is the test case number starting from 1. Then, for every station from which a full lap can be completed, append the pair i d, where $i$ is the station's location and $d$ is:

• C if the lap can be completed only in the clockwise direction,
• CC if it can be completed only in the counterclockwise direction,
• CCC if it can be completed in either direction.

List the qualifying stations in order of increasing location, separated by spaces.