Волшебник Зейн хочет показать публике фокус с переставлением стаканов.
Есть n стаканов, пронумерованных от 1 до n, расположенных вдоль оси x на столе, на котором имеется m отверстий. Более точно, стакан номер i стоит на столе на позиции x = i.
Игральная кость изначально находится в позиции x = 1. Зейн запутает аудиторию, меняя пару стаканов местами ровно k раз, i-ми по порядку переставляя стаканы на позициях x = ui и x = vi. Если в любой момент времени кость оказывается в позиции, где есть отверстие в столе, она падает в него, и остается на месте до конца фокуса.
Не забудьте, что Зейн волшебник. Поэтому, когда он меняет местами два стакана, он не двигает их по столу, а телепортирует стаканы (вместе с костью, если она внутри какого-то из них) на необходимые позиции. Поэтому, например, при переставлении местами стаканов на местах x = 4 и x = 6, они не окажутся на позиции x = 5 ни в какой момент операции.
Щенок Зейна Инзейн озадачен. Зейн отошел, и Инзейн не может найти свою любимою игральную кость, и будет очень утомительно пытаться открыть все стаканы. Инзейн знает, что сообщество Codeforces уже успешно помогло Зейну, поэтому просит помочь ему тоже. Помогите Инзейну определить финальную позицию кости.
Примечание
В первом примере после каждой из операций кость оказывается на позициях x = 2, x = 5, x = 7, и x = 1, соответственно.
Во втором примере после первой операции кость окажется в позиции x = 2 и упадет в отверстие.