Problem description

Jasio, na przedmiocie Logika dla informatyków, dowiedział się ostatnio o istnieniu takiego tworu jak funkcje różnowartościowe. Są to funkcje, które dla dowolnych dwóch różnych argumentów z dziedziny zwracają różne wartości. Przykładowo funkcja f : ℝ → ℝ, zadana wzorem f(x) = 2x + 1 jest różnowartościowa, ale gdyby była zadana wzorem f(x) = x² to już nie byłaby różnowartościowa (bo f(1) = f(−1) = 1, czyli są dwa różne argumenty dla których wartość funkcji jest taka sama).

Jasio dostał właśnie w prezencie (na dzień chłopaka) funkcję różnowartościową f : {1, 2, …, N} → ℕ₊. Samo to, że funkcja jest różnowartościowa mu się oczywiście bardzo podoba, ale wartości funkcji w niektórych (no dobra, w niektórych testach może być nawet tak, że we wszystkich) punktach go irytują i chciałby je zmienić na inne. Dla każdego argumentu x ∈ {1, 2, …, N} podał swoją idealną wartość g(x), jaką chciałby, żeby przyjęła jego funkcja f. Możliwe, że dla niektórych argumentów x zachodzi f(x) = g(x).

Jasio chciałby wymienić wartości f(x) na g(x) dla jak największej liczby argumentów x, pozostawiając wartości dla pozostałych argumentów niezmienione. Chce przy tym, żeby jego powstała funkcja była różnowartościowa. No a niestety nikt nie powiedział, że Jasio ma trochę oleju w głowie i że g jest różnowartościowa. Oczywiście, jak to zwykle w takich przypadkach bywa, Jasio prosi Cię o pomoc w tym arcyważnym zadaniu.

Napisz program, który: wczyta rozmiar N dziedziny funkcji różnowartościowej f, bieżące wartości tej funkcji f(x) we wszystkich punktach z dziedziny oraz oczekiwane przez Jasia wartości g(x) tej funkcji we wszystkich punktach z dziedziny, wyznaczy optymalny sposób zmiany funkcji na funkcję różnowartościową f′ (aby dla jak największej liczby argumentów jej wartość była zgodna z g) według zasad opisanych powyżej i wypisze wynik na standardowe wyjście.

Wejście

W pierwszym wierszu wejścia znajduje się jedna liczba naturalna N określająca rozmiar dziedziny funkcji f. W drugim wierszu wejścia znajduje się ciąg N liczb naturalnych f(i), pooddzielanych pojedynczymi odstępami. Są to wartości funkcji f w kolejnych punktach 1, 2, …, N. W trzecim (ostatnim) wierszu wejścia znajduje się ciąg N liczb naturalnych g(i) pooddzielanych pojedynczymi odstępami. Są to oczekiwane wartości g w kolejnych punktach 1, 2, …, N.

Wyjście

W pierwszym wierszu wyjścia powinna się znaleźć jedna nieujemna liczba całkowita – największa liczba argumentów x, dla których f′(x) = g(x).

W drugim (ostatnim) wierszu wyjścia powinien się znaleźć ciąg N liczb naturalnych pooddzielanych pojedynczymi odstępami – wartości f′(1), f′(2), …, f′(N).

Jeżeli istnieje wiele rozwiązań, Twój program może wypisać dowolne z nich.

Ograniczenia

1 ≤ N ≤ 500 000, 1 ≤ f(x), g(x) ≤ 10⁹.

Przykład

9
5 8 3 10 7 20 4 6 12
8 5 7 7 3 20 6 9 6

7
8 5 7 10 3 20 6 9 12