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) = x2 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) ≤ 109.
Przykład
| Wejście | Wyjście | |
|
|