가스탱크로 한 바퀴

필요한 만큼 얼마든지 담을 수 있을 만큼 아주 큰 연료 탱크를 가진 자동차가 있다고 하자. 이 자동차는 여러 주유소가 놓인 원형 도로를 달린다. 모든 주유소에 있는 연료를 합치면 원형 도로를 정확히 한 바퀴 도는 데 필요한 양과 같다. 주유소에 도착할 때마다 그 주유소의 연료를 모두 탱크에 넣는다.

빈 탱크로 출발할 때, 한 바퀴를 완주해 출발점으로 돌아올 수 있는 주유소와 방향(시계 방향 또는 반시계 방향)이 항상 적어도 하나는 존재한다.

원형 도로의 길이, 주유소들의 위치, 그리고 각 주유소의 연료로 달릴 수 있는 거리가 주어질 때, 한 바퀴를 완주할 수 있는 모든 (주유소, 방향)을 구하라.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 두 양의 정수 $c$와 $s$가 주어진다. $c$는 원형 도로의 전체 둘레(마일)이고, $s$는 주유소의 개수이다.

이어서 주유소를 나타내는 $s$개의 정수 쌍 $t$와 $m$이 주어진다. $t$($0 \le t \le c-1$)는 원 위의 고정된 기준점에서 시계 방향으로 잰 주유소의 위치이고, $m$은 그 주유소의 연료를 모두 사용해 달릴 수 있는 마일 수이다. 모든 주유소의 위치는 서로 다르며 $c \le 100000$이다.

한 테스트 케이스에서 모든 $m$의 합은 $c$와 같다.

테스트 케이스 목록은 두 개의 0이 적힌 줄로 끝난다.

각 테스트 케이스마다 Case X:를 출력한다. 여기서 $X$는 1부터 시작하는 테스트 케이스 번호이다. 그 뒤에 한 바퀴를 완주할 수 있는 각 주유소에 대해 쌍 i d를 이어서 출력한다. $i$는 주유소의 위치이고 $d$는 다음과 같다.

• 시계 방향으로만 완주할 수 있으면 C
• 반시계 방향으로만 완주할 수 있으면 CC
• 양쪽 방향 모두 완주할 수 있으면 CCC

완주할 수 있는 주유소들을 위치가 증가하는 순서로, 공백으로 구분하여 나열한다.