Candy Shop Vouchers

Byteasar’s candy shop sells caramel candy in packages, where each positive integer represents a unique package count. To promote his sweets, Byteasar plants m vouchers (for an annual supply of chocolate) into some packages (at most one per package). The carnival runs for n days; on day k there are a_k guests. On the morning of day k, each guest buys, in order, the smallest available package whose candy count is divisible by a_k (i.e. the package’s candy count is a multiple of a_k).

After the n days the following happens: among all sold packages, the m packages with the smallest candy counts are precisely those containing vouchers. Your task is to determine exactly which customer obtained a voucher‐package. A customer is identified by the day number (1-indexed) and the order in which they bought the package on that day (also 1-indexed).

Example: Suppose m=3, n=2 with a₁=4 and a₂=2. Then:

• On day 1, the 4 guests buy packages with candy counts: 4, 8, 12, 16 (in that order).
• On day 2, the 2 guests buy packages with candy counts: 2 and 6.

Collecting all sold packages, we have counts: 2, 4, 6, 8, 12, 16. The m=3 packages with the smallest counts are 2, 4, and 6. Thus, the voucher recipients are:

• Package 2: Day 2, 1^st customer.
• Package 4: Day 1, 1^st customer.
• Package 6: Day 2, 2^nd customer.

Your program should output the day and order (within that day) of the customer receiving each voucher, listed in order of increasing candy package count.

inputFormat

The first line contains two integers m and n (1 ≤ m ≤ total sold packages, 1 ≤ n). The second line contains n space‐separated positive integers, where the k-th integer a_k denotes the number of guests on day k.

Note: It is guaranteed that the total number of packages sold (i.e. sum(ak) over all days) is at least m.

outputFormat

Output m lines. Each line should contain two integers: the day number and the order of the customer (in that day) who purchased the package with a voucher. The vouchers should be reported in order of increasing candy package count.

sample

3 2
4 2

2 1
1 1
2 2