В столице Берляндии находится единственный кинотеатр в стране, да и к тому же он состоит только из одного зала. Зал разделен на n рядов, каждый из которых состоит из m мест.
В очереди к кассе кинотеатра стоят k человек, каждый из которых хочет купить ровно один билет для себя любимого. Еще до начала продаж каждый нашел самое лучшее с его точки зрения место и запомнил его как пару координат (xi, yi), где xi — номер ряда, а yi — номер места в этом ряду.
Возможно, что несколько человек облюбовали одно и то же место, тогда те люди, места которых оказались заняты к моменту покупки билета, выберут себе другие места, руководствуясь следующими правилами. Пусть изначально посетитель хотел себе купить билет на место (x1, y1), тогда когда он подойдет к кассе, то выберет такое свободное место (x2, y2), которое удовлетворяет условиям:
- величина |x1 - x2| + |y1 - y2| принимает наименьшее значение
- если выбор неоднозначен, то среди мест, удовлетворяющих первому условию, выбирается то, у которого величина x2 принимает наименьшее значение
- если выбор все еще не однозначен, то среди мест, удовлетворяющих первому и второму условям, выбирается то, у которого величина y2 принимает наименьшее значение
Ваша задача — найти для каждого человека координаты места, на которое он купит билет.
Выходные данные
Выведите в k строках по паре чисел. В i-ой строке выведите xi, yi — координаты места, на которое i-ый в очереди посетитель купит билет.