Recently Vadik had to say goodbye to yet another member of Team.GOV. Vadik had to find the new team member to participate in the Ural Championship. Suddenly Vadik thought that mixed teams are allowed, and he had a good Chinese friend — Xiaohong Hao, a participant of the ACM ICPC World Finals. A perfect choice! And Vadik is now sitting in front of a computer and is typing a letter.

Hey!

I need a team member for the Ural Championship. Would you like to play in Team.GOV? If interested, send me a solution of the test task by tomorrow.

A Hamming distance between two strings of equal lengths is the number of characters that are not same in these two strings. Let's say that distance between s₁ and a shorter s₂ is the sum of Hamming distances between s₂ and all substrings of s₁ with length equal to the length of s₂. We'll call a string to be partial one if it may contain a character “?” apart from alphabet characters. Two partial strings are given. You're asked to replace question marks with alphabet characters in such a way that distance between transformed strings is minimal.

You have to solve this problem for the case when the first string is cyclical. Best of luck!

P.S. Oh, the string is called to be cyclical one if except for regular substrings is also has the substrings that are a concatenation of a suffix and a prefix. For instance, a regular string “abcd” has two substrings of length 3: “abc” and “bcd”. A cyclical string “abcd” in addition to those two ones has two more substrings of length 3: “cd” + “a” = “cda”, “d” + “ab” = “dab”.

Specially for Xiaohong Vadik made tests with hieroglyphs instead of Latin letters in both strings.

The input data consist of two blocks two lines each. The first block describes the cyclical string s and the second block describes the string t. In the first line of each block you are given the number n that is a length of string (1 ≤ n ≤ 100 000). In the second line of the block you are given n non-negative integers separated with a space. Positive integers denote hieroglyphs and zero denotes the question mark. Numbers denoting hieroglyphs don't exceed 100 000.

Replace question marks in s and in t with hieroglyphs in such a way that distance between the strings that are obtained by replacement is minimal. Output the resulting distance.

You need replace the question mark in s with the third hieroglyph, and question marks in t with the first and the second hieroglyphs respectively. Cyclical string “21132” has substrings “2113”, “1132”, “1322”, “3221” and “2211”. Hamming distance from string “3132” to these substrings is equal to three, one, three, three, four respectively. The sum of these distances is equal to fourteen.