В состав Галактической империи входит N планет. Между большинством из них существуют гиперканалы. Новый император повелел, чтобы с любой планеты можно было попасть на любую другую, пройдя только через один гиперканал. Каналы устроены так, что позволяют путешествовать только в одну сторону.

Единственный оставшийся прокладчик гиперканалов расположен на базе около планеты с номером A. К сожалению, он не может путешествовать по уже существующим каналам, он всегда прокладывает новый. А наличие двух каналов в одном направлении между двумя планетами существенно осложняет навигацию. Ваша задача — найти такой маршрут для прокладчика, чтобы все необходимые каналы были построены, и не было бы построено лишних. В конце своего маршрута прокладчик должен оказаться на своей родной базе, с которой он начал движение.

В первой строке находится число N ≤ 1000 и число A ≤ N. N следующих строк содержит по N чисел — в i-й строке j-е число равно 1, если есть канал от планеты i к планете j, иначе 0. Известно, что Галактическая империя может удовлетворить свою потребность в гиперканалах прокладкой не более чем 32000 новых каналов.

Выведите последовательность, в которой следует прокладывать каналы. Каждая строка должна содержать два целых числа: номера планет, с какой и на какую следует проложить очередной гиперканал. Гиперканалы следует перечислить в порядке их прокладки. Гарантируется, что решение существует.