GOV-internship 3#5617
Definition. Hamming distance between two strings of equal length is the number of positions in which these strings differ.
Definition. Distance from text to pattern is the sum of all Hamming distances between the pattern and all substrings of text which have length .
You are given text and pattern . 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 distance from text to pattern will be the least possible.
The first line contains the length (1 \le n \le 100000) of the text . The second line contains the text represented as non-negative integers separated by whitespaces. The third line contains one integer : the length of the pattern (1 \le 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. Numbers denoting symbol positions do not exceed . It is guaranteed that if there are lost symbols in text, there are none in pattern and vice versa.
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.
Example 1