1973번 - 버스 노선 스페셜 저지

당신이 한 버스 정거장에 아침 9시에 도착했다. 그리고 9시부터 9시 59분까지 그 곳에 있었다. 그 동안 노선이 다른 여러 버스들이 이 정거장에 섰는데, 당신은 그 버스들이 도착하는 시각을 주의 깊게 관찰하였다.

노선이 같은 버스는 9시 정각부터 9분까지 같은 시간 간격으로 규칙성 있게 도착한다. 버스를 관찰한 시간은 0부터 59분까지이다. 각 노선을 달리는 버스는 그 동안 적어도 두 번은 정거장에 서며, 시간은 정수 시간만을 계산한다. (최소 단위는 1분)

노선이 다르더라도 어떤 버스 노선의 시간 스케줄은 최초 도착 시간이나 시간 간격 중 하나 이상이 다른 노선의 스케줄과 일치할 수 있다. 그런 이유로, 같은 시각에 노선이 다른 버스가 두 대 이상 도착하면 그 시각은 온 버스 수만큼 중복 기록한다. 즉, 만약 최초 도착 시간과 오는 간격이 완전히 같은 두 노선이 있더라도 그 노선을 다니는 버스들이 온 시각은 구분되어 따로 입력 파일에 기록된다는 뜻이다.

버스가 도착한 시간 기록을 입력 받아서 이 간격대로 있을 수 있는 서로 다른 버스 노선들을 구해 이들의 시간 스케줄을 출력하는 프로그램을 작성하라. 그리고 찾아낸 버스 노선마다 그 노선의 첫 도착 시간과 다음 간격을 출력하라. 그러한 경우가 많다면, 버스 노선의 수가 가장 적은 경우를 찾아야 한다. (버스의 수는 25를 넘지 않는다)

첫째 줄에 버스가 선 횟수 n(2≤n≤300)이 주어진다. 다음 줄에는 버스가 온 시각 n개가 주어진다. 각각의 시각은 정수라 가정하자. 시각은 분 단위만 기록하며, 0이상 59이하의 값을 갖는다. 입력의 중간에는 공백 대신 엔터가 주어질 수도 있다.

첫째 줄에 버스 노선의 최소 개수 X를 출력한다. 다음 X개의 줄에는 각 노선의 첫 도착 시각과 간격을 출력한다. 최적해가 여러 개인 경우에는 임의의 하나만 출력하면 되며, 출력 순서는 상관이 없다.

0 13    ← 0 . . 13  .  . 26  .  .  . 39  .  . 52  . (5번)
3 12    ← . 3 .  . 15  .  . 27  .  . 39  . 51  .  . (5번)
5 8     ← . . 5 13  . 21  .  . 29 37  . 45  .  . 53 (7번)