Авиакомпания Oceanic Airlines объявила, что с нового года у всех пассажиров трансатлантических рейсов будет возможность попробовать во время полёта знаменитые уральские бифштексы. В отличие от стандартных обедов, эти бифштексы будут готовиться прямо во время полёта, а значит, будут свежими, горячими и вкусными.

Каждый пассажир во время регистрации на рейс может указать точное время, когда ему нужно подать готовый бифштекс. Чтобы приготовить один бифштекс, нужно непрерывно жарить каждую из двух его сторон на сковороде в течение одной минуты. При этом бифштекс нельзя начать готовить раньше, чем за x минут до того, как он должен быть подан, — иначе он уже не будет таким вкусным.

К сожалению, в самолётах Oceanic Airlines есть всего одна электрическая плита и одна сковорода, на которой одновременно можно готовить не более k бифштексов. Пока на плите ничего не готовится, её можно выключить. Повар хочет выполнить заказы всех пассажиров вовремя, минимизировав время, в течение которого включена плита. Помогите ему в этом.

В первой строке записаны целые числа x и k (2 ≤ x ≤ 1 000; 1 ≤ k ≤ 50). Во второй строке записано целое число n — количество заказанных бифштексов (1 ≤ n ≤ 50). В третьей строке записаны целые числа t₁, …, t_n, задающие моменты времени, когда должны быть поданы бифштексы (2 ≤ t_i ≤ 1 000). Моменты времени упорядочены по неубыванию и отсчитываются от начала полёта.

Если повару удастся выполнить все заказы вовремя, выведите в первой строке минимальное количество минут, которое должна работать электроплита. В i-й из следующих n строк выведите два неотрицательных целых числа — моменты времени, когда нужно положить i-й бифштекс на сковороду первой и второй стороной соответственно. Бифштексы следует описывать в том же порядке, в котором они даны на входе. Если возможных ответов несколько, выведите любой из них. Если выполнить все заказы вовремя невозможно, выведите «-1».