В столице Берляндии находится единственный кинотеатр в стране, да и к тому же он состоит только из одного зала. Зал разделен на n рядов, каждый из которых состоит из m мест.

В очереди к кассе кинотеатра стоят k человек, каждый из которых хочет купить ровно один билет для себя любимого. Еще до начала продаж каждый нашел самое лучшее с его точки зрения место и запомнил его как пару координат (x_i, y_i), где x_i — номер ряда, а y_i — номер места в этом ряду.

Возможно, что несколько человек облюбовали одно и то же место, тогда те люди, места которых оказались заняты к моменту покупки билета, выберут себе другие места, руководствуясь следующими правилами. Пусть изначально посетитель хотел себе купить билет на место (x₁, y₁), тогда когда он подойдет к кассе, то выберет такое свободное место (x₂, y₂), которое удовлетворяет условиям:

• величина |x₁ - x₂| + |y₁ - y₂| принимает наименьшее значение
• если выбор неоднозначен, то среди мест, удовлетворяющих первому условию, выбирается то, у которого величина x₂ принимает наименьшее значение
• если выбор все еще не однозначен, то среди мест, удовлетворяющих первому и второму условям, выбирается то, у которого величина y₂ принимает наименьшее значение

Ваша задача — найти для каждого человека координаты места, на которое он купит билет.