ENG  RUSTimus Online Judge
Online Judge
Problems
Authors
Online contests
About Online Judge
Frequently asked questions
Site news
Webboard
Links
Problem set
Submit solution
Judge status
Guide
Register
Update your info
Authors ranklist
Current contest
Scheduled contests
Past contests
Rules

Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013

About     Problems     Submit solution     Judge status     Standings
Contest is over

I. GOV-internship 3

Time limit: 1.0 second
Memory limit: 64 MB
Definition. Hamming distance between two strings of equal length is the number of positions in which these strings differ.
Definition. Distance from text s to pattern p is the sum of all Hamming distances between the pattern and all substrings of text which have length |p|.
You are given text s and pattern p. Either text or pattern, but not both, can be damaged (some symbols are lost). Your task is to reconstruct the damaged string so that the Hamming distance between the text and the pattern will be the least possible.

Input

The first line contains one integer n: the length of the text s (1 ≤ n ≤ 100 000). The second line contains the text represented as n integer numbers ti separated by whitespaces (0 ≤ ti ≤ 100 000). The third line contains one integer m: the length of the pattern p (1 ≤ m < n). The fourth line contains the pattern in the same format. Positive numbers denote the number of the symbol in the alphabet, while zero denotes a lost symbol. It is guaranteed that if there are lost symbols in text, there are none it pattern and vice versa.

Output

Output the text and the pattern separated with a line break. All lost symbols must be reconstructed. If there are several ways to reconstruct symbols optimally, output any one of them.

Sample

inputoutput
5
1 2 3 1 2
3
1 2 0
1 2 3 1 2
1 2 1
Problem Author: Mikhail Rubinchik (prepared by Bulat Zaynullin)
Problem Source: Ural FU contest. Kontur Cup. Petrozavodsk training camp. Winter 2013
To submit the solution for this problem go to the Problem set: 1959. GOV-internship 3