Заметьте, что девушки в стране Arpa действительно привлекательные.
Arpa любит ночные вечеринки. В середине одной из них неожинанно пришел Mehrdad. Он увидел n пар друзей сидящих вокруг стола. i-я пара состояла из молодого человека, сидящего на ai-м стуле, и его девушки, сидящей на bi-м стуле. Стулья пронумерованы от 1 до 2n по часовой стрелке. На каждом стуле сидел ровно один человек.
На вечеринке было два вида еды: Kooft и Zahre-mar. Сейчас Mehrdad задумался, можно ли было подать еду для гостей таким образом, что:
- Каждый человек получил бы ровно один вид еды,
- Ни один молодой человек не получил бы тот же вид еды, что и его девушка,
- Среди каждых трех гостей, сидящих на последовательных стульях, нашлись бы два, получившие разный вид еды. Заметим, что стулья 2n и 1 также считаются последовательными.
Найдите ответ на вопрос Mehrdad. Если такое было возможно, то найдите распределение видов еды, удовлетворяющее всем условиям.
Выходные данные
Если решения не существует, выведите -1.
Иначе выведите n строк, i-я из них должна содержать два целых числа, описывающие виды еды, поданной для i-й пары. Первое число в этой строке это вид еды, поданной молодому человеку, а второе — тип еды, поданной его девушке. Если человеку подали Kooft, выведите 1, иначе выведите 2.
Если существует несколько решений, выведите любое из них.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3
1 4
2 5
3 6
|
1 2
2 1
1 2
|