I. Сколько весит карма?
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

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

Но в одном городке все пошло не по плану. Оказалось, что горожане поклонялись могучей богине справедливости и правосудия Анасте, и считали любую магию несправедливостью по отношению к суровой реальности. Ур и Ар были схвачены, приведены в храм Анасты и оставлены дожидаться пришествия богини.

И ведь дождались! Ровно в полночь Анаста явилась к напуганным до смерти магам. Она была слепа (как и всякое правосудие), а в руке держала невероятно большие рычажные весы. Когда человек вставал на одну чашу весов, на другой появлялись совершенные им несправедливости.

Ур и Ар не были злодеями, убивавшими детей и грабившими беззащитных стариков, но и в их жизни были мелкие косяки со справедливостью. Косяки никогда не повторялись, ведь друзья всегда хотели попробовать что-нибудь новое. Некоторые вещи они совершали вместе, а что-то Ур (или Ар) делал за двоих, беря на себя двойную ответственность.

Поэтому, когда Ур и Ар встали на разные чаши весов, на чашах появилось ровно 2N несправедливостей (по N на каждой чаше), занумерованных от 1 до n (каждая несправедливость встречается ровно 2 раза).

Анаста заявила, что когда весы придут в равновесие, она решит их судьбу. Ур и Ар подумали, что пока весы колеблются, они могут незаметно сделать набор несправедливостей и даже порядок расположения несправедливостей в наборах на чашах полностью одинаковым. Тогда Анасте придется выбрать им полностью одинаковую судьбу, и друзья смогут и дальше продолжить свои приключения вместе.

Весы оказались довольно неустойчивы, поэтому за одно действие Ур может перекинуть только одну несправедливость Ару, а Ар одновременно перекинуть несправедливость со своей чаши Уру.

На кону судьба их дружбы, поэтому Ур и Ар просят помочь вас и подсказать им возможный порядок перекидывания несправедливостей между чашами. Помните, что весы Анасты скоро придут в равновесие, поэтому маги успеют сделать не более 4n перекидываний.

Входные данные

В первой строке вводится число n (1 ≤ n ≤ 105) - количество несправедливостей на каждой из чаш весов.

В следующей строке вводятся n чисел ai (1 ≤ ai ≤ n) - порядок номеров несправедливостей на чаше весов с Уром.

В последней строке вводятся n чисел bi (1 ≤ bi ≤ n) - порядок номеров несправедливостей на чаше весов с Аром.

Гарантируется, что среди чисел ai и bi есть ровно два числа 1, два числа 2, ..., два числа n.

Выходные данные

В первой строке выведите k (0 ≤ k ≤ 4n)- количество действий магов, которое приведет к совпадению итоговых наборов несправедливостей и порядка расположения несправедливостей в наборах.

В каждой из следуюших k строк выведите по два числа fi и si - позиции несправедливостей на чаше Ура и Ара соответственно, которые необходимо поменять местами в i-ом действии.

Пример
Входные данные
3
1 1 2
2 3 3
Выходные данные
4
2 3
3 3
3 1
3 3
Примечание

Рассмотрим пример:

Перед первым действием a = [1, 1, 2], b = [2, 3, 3].

1) f1 = 2, s1 = 3 - меняются местами a2 и b3 - a = [1, 3, 2], b = [2, 3, 1];

2) f2 = 3, s2 = 3 - меняются местами a3 и b3 - a = [1, 3, 1], b = [2, 3, 2];

3) f3 = 3, s3 = 1 - меняются местами a3 и b1 - a = [1, 3, 2], b = [1, 3, 2];

4) f4 = 3, s4 = 3 - меняются местами a3 и b3 - a = [1, 3, 2], b = [1, 3, 2].

Обратите внимание, что маги имели право остановиться уже после 3-го действия, так как наборы уже полностью совпадали.