{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\n \u003cimg src\u003d\"CDN_BASE_URL/eab802b2391d497899757ea921ed9e1b?v\u003d1675310697\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n 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\u0026nbsp;— 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.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n Hey!\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n 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.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n A Hamming distance between two strings of equal lengths is the number of characters that are not same in these two strings. Let\u0027s say that distance between \u003ci\u003es\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e and a shorter \u003ci\u003es\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e is the sum of Hamming distances between \u003ci\u003es\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e and all substrings of \u003ci\u003es\u003c/i\u003e\u003csub\u003e1\u003c/sub\u003e with length equal to the length of \u003ci\u003es\u003c/i\u003e\u003csub\u003e2\u003c/sub\u003e. We\u0027ll call a string to be partial one if it may contain a character “?” apart from alphabet characters. Two partial strings are given. You\u0027re asked to replace question marks with alphabet characters in such a way that distance between transformed strings is minimal.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n You have to solve this problem for the case when the first string is cyclical. Best of luck!\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n 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” \u003d “cda”, “d” + “ab” \u003d “dab”.\n \u003c/div\u003e\n \u003c/div\u003e\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n Specially for Xiaohong Vadik made tests with hieroglyphs instead of Latin letters in both strings.\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Input","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n The input data consist of two blocks two lines each. The first block describes the cyclical string \u003ci\u003es\u003c/i\u003e and the second block describes the string \u003ci\u003et\u003c/i\u003e. In the first line of each block you are given the number \u003ci\u003en\u003c/i\u003e that is a length of string (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100\u0026nbsp;000). In the second line of the block you are given \u003ci\u003en\u003c/i\u003e non-negative integers separated with a space. Positive integers denote hieroglyphs and zero denotes the question mark. Numbers denoting hieroglyphs don\u0027t exceed 100\u0026nbsp;000.\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Output","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n Replace question marks in \u003ci\u003es\u003c/i\u003e and in \u003ci\u003et\u003c/i\u003e with hieroglyphs in such a way that distance between the strings that are obtained by replacement is minimal. Output the resulting distance.\n \u003c/div\u003e\n \u003c/div\u003e\n "}},{"title":"Sample 1","value":{"format":"HTML","content":"\u003ctable class\u003d\u0027vjudge_sample\u0027\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e5\r\n2 1 1 0 2\r\n4\r\n3 0 3 0\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e14\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Notes","value":{"format":"HTML","content":"\n \u003cdiv class\u003d\"problem_par\"\u003e\n \u003cdiv class\u003d\"problem_par_normal\"\u003e\n You need replace the question mark in \u003ci\u003es\u003c/i\u003e with the third hieroglyph, and question marks in \u003ci\u003et\u003c/i\u003e 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.\n \u003c/div\u003e\n \u003c/div\u003e\n "}}]}