Ур и Ар были странствующими магами, неразлучными друзьями с самого раннего детства. Они приходили в какой-нибудь городок, показывали там всякие фокусы, танцы с бубнами, проводили сеансы телепатии - в общем, по всякому развлекали народ, а взамен получали кров и пищу.
Но в одном городке все пошло не по плану. Оказалось, что горожане поклонялись могучей богине справедливости и правосудия Анасте, и считали любую магию несправедливостью по отношению к суровой реальности. Ур и Ар были схвачены, приведены в храм Анасты и оставлены дожидаться пришествия богини.
И ведь дождались! Ровно в полночь Анаста явилась к напуганным до смерти магам. Она была слепа (как и всякое правосудие), а в руке держала невероятно большие рычажные весы. Когда человек вставал на одну чашу весов, на другой появлялись совершенные им несправедливости.
Ур и Ар не были злодеями, убивавшими детей и грабившими беззащитных стариков, но и в их жизни были мелкие косяки со справедливостью. Косяки никогда не повторялись, ведь друзья всегда хотели попробовать что-нибудь новое. Некоторые вещи они совершали вместе, а что-то Ур (или Ар) делал за двоих, беря на себя двойную ответственность.
Поэтому, когда Ур и Ар встали на разные чаши весов, на чашах появилось ровно 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-ом действии.
Рассмотрим пример:
Перед первым действием 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-го действия, так как наборы уже полностью совпадали.
## Входные Данные
В первой строке вводится число 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-ом действии.
## Пример
Входные данные31 1 22 3 3Выходные данные42 33 33 13 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-го действия, так как наборы уже полностью совпадали.
[samples]
**Definitions**
Let $ n \in \mathbb{Z}^+ $ be the number of distinct injustices, with two copies of each injustice numbered $ 1 $ to $ n $.
Let $ A = (a_1, a_2, \dots, a_n) $ be the sequence of injustices on Ur’s side.
Let $ B = (b_1, b_2, \dots, b_n) $ be the sequence of injustices on Ar’s side.
Each integer $ i \in \{1, \dots, n\} $ appears exactly twice across $ A \cup B $.
**Constraints**
1. $ 1 \leq n \leq 10^5 $
2. $ 1 \leq a_i, b_i \leq n $ for all $ i \in \{1, \dots, n\} $
3. Each value from $ 1 $ to $ n $ appears exactly twice in $ A \cup B $.
4. At most $ 4n $ swaps are allowed.
**Objective**
Find a sequence of swaps $ (f_j, s_j) $ for $ j = 1, \dots, k $ (where $ 0 \leq k \leq 4n $) such that after swapping $ a_{f_j} $ with $ b_{s_j} $ in each step, the final sequences $ A $ and $ B $ are identical.
Each swap exchanges one element from $ A $ with one element from $ B $.