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

Суть фокуса в том, чтобы обмануть внимание человека. Изначально перед испытуемым в ряд выкладывают n пластиковых стаканчиков, далее фокусник кладет под один из стаканчиков маленький шарик, далее перемешивает стаканчики. После чего человек должен угадать, под каким стаканом находится шарик.

Но главного программиста компании F обмануть не так-то просто. Увидев фокус, он заметил несколько важных фактов:

• на каждом из стаканчиков есть пометка — число от 1 до n; причем все пометки на стаканчиках различны;
• фокусник перемешивает стаканчики за m операций, каждая операция имеет следующий вид: взять стаканчик с пометкой x_i, который в данный момент стоит на позиции y_i в ряду стаканчиков (позиции нумеруются слева, начиная от 1), и переместить его в самое начало ряда стаканчиков (на первую позицию).

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