The Oceanic Airlines company has announced that starting from the new year all passengers of transoceanic flights will be able to taste the famous Ural steaks during the flight. Unlike the standard meals, the steaks will be fresh, hot, and incredibly delicious because they will be cooked right on board.

Each passenger can specify at check-in the exact time when she wants her steak to be served. A steak is cooked by frying each of its sides on a frying pan continuously for one minute. If a steak is cooked too early, it won't be delicious enough, so the cooking must start no earlier than x minutes before the steak is served.

Unfortunately, each Oceanic Airlines plane is equipped with only one electric stove and one frying pan. No more than k steaks can be cooked on the frying pan simultaneously. The stove can be switched off when nothing is cooked. The chef wants to serve the orders of all the passengers on time while minimizing the time during which the stove is switched on. Help the chef.

The first line contains the integers x and k (2 ≤ x ≤ 1 000; 1 ≤ k ≤ 50). In the second line you are given the number n of ordered steaks (1 ≤ n ≤ 50). In the third line there are integers t₁, …, t_n, which define the times when the steaks should be served (2 ≤ t_i ≤ 1 000). The times are given in nondecreasing order and are counted from the moment of departure.

If the chef can cook the ordered steaks on time, output in the first line the minimum number of minutes during which the electric stove will be working. In the ith of the following n lines output two nonnegative integers, which are the times when the ith steak should be put on the frying pan on one side and on the other side, respectively. The steaks must be described in the same order in which they are given in the input. If there are several possible answers, output any of them. If it is impossible to serve all the orders on time, output “-1”.