Minimum Bus Route Schedule

A man arrives at a bus stop exactly at 12:00 and waits until 12:59. Several bus routes operate at this stop. Each bus route has a fixed schedule: starting at a certain minute s and then arriving at a fixed interval d minutes. That is, if a route is defined by s and d, then its arrival times are given by $$s,\; s+d,\; s+2d,\; \dots$$ in the period 0 to 59 minutes (inclusive). Each bus route makes at least 2 stops (i.e. the second arrival $$s+d\le 59$$).

The observed arrival times (in whole minutes from 0 to 59) are recorded. Note that:

• Buses on the same route arrive exactly at the times of their arithmetic progression.
• Buses from different routes may arrive at the same time.
• Several bus routes might share the same starting time and/or the same interval; if so, they are considered distinct routes.

Your task is to determine a schedule with the fewest number of bus routes such that the union (with multiplicities) of the arrival times produced exactly matches the input. In other words, if the observed arrival times have a count c(t) for each time t (from 0 to 59), then for each route with starting time s and interval d, its complete arithmetic sequence in [0, 59] (i.e. $$\{s, s+d, s+2d, \dots\}$$ with $$s+k\cdot d\le59$$) is required to be present in the input, and each appearance counts toward covering the observations. Output the starting time and interval for each bus route in your chosen schedule.

Note: It is guaranteed that the minimum number of bus routes needed in the test cases is at most 17.

inputFormat

The input begins with an integer n (the total number of bus arrivals recorded). The next line contains n space-separated integers, each representing an arrival time in minutes (from 0 to 59).

You may assume that 2 ≤ n ≤ 60.

outputFormat

For each bus route in the schedule, output a line containing two space-separated integers: the starting time s and the interval d.

The number of lines should equal the minimum number of bus routes required to exactly cover the input arrival times.

sample

6
0 10 20 30 40 50

0 10