{"trustable":true,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cimg src\u003d\"CDN_BASE_URL/eab802b2391d497899757ea921ed9e1b?v\u003d1714350912\" border\u003d\"0\" alt\u003d\"Problem illustration\" align\u003d\"RIGHT\" class\u003d\"problem_raimage\"\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eRecently Vadik had to say goodbye to yet another member of Team.GOV. Vadik \r\nhad to find the new team member to participate in the Ural Championship. \r\nSuddenly Vadik thought that mixed teams are allowed, and he had a \r\ngood Chinese friend\u0026nbsp;— Xiaohong Hao, a participant of the ACM ICPC World \r\nFinals. A perfect choice! \r\nAnd Vadik is now sitting in front of a computer and is typing a letter.\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eHey!\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eI need a team member for the Ural Championship. Would you like to \r\nplay in Team.GOV? If interested, send me a solution of the test task by \r\ntomorrow. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eA Hamming distance between two strings of equal lengths is the number of \r\ncharacters that are not same in these two strings. Let\u0027s say that distance \r\nbetween \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 \r\n\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. \r\nWe\u0027ll call a string to be partial one if it may contain a character “?” \r\napart from alphabet characters. Two partial strings are given. You\u0027re \r\nasked to replace question marks with alphabet characters in such a way \r\nthat distance between transformed strings is minimal. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYou have to solve this problem for the case when the first string is cyclical.\r\nBest of luck!\u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eP.S. Oh, the string is called to be cyclical one if except for regular \r\nsubstrings is also has the substrings that are a concatenation of a suffix and a \r\nprefix. For instance, a regular string “abcd” has two \r\nsubstrings of length 3: “abc” and “bcd”. A cyclical string “abcd” in \r\naddition to those two ones has two more substrings of length 3: “cd” + \r\n“a” \u003d “cda”, “d” + “ab” \u003d “dab”. \u003c/div\u003e\u003c/div\u003e\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eSpecially for Xiaohong Vadik made tests with hieroglyphs instead of \r\nLatin letters in both strings.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eThe input data consist of two blocks two lines each. The first block \r\ndescribes the cyclical string \u003ci\u003es\u003c/i\u003e and the second block describes the \r\nstring \u003ci\u003et\u003c/i\u003e. In the first line of each block you are given the number \u003ci\u003en\u003c/i\u003e \r\nthat is a length of string (1 ≤ \u003ci\u003en\u003c/i\u003e ≤ 100\u0026nbsp;000). In the second line \r\nof the block you are given \u003ci\u003en\u003c/i\u003e non-negative integers separated with a \r\nspace. Positive integers denote hieroglyphs and zero denotes the question \r\nmark. Numbers denoting hieroglyphs don\u0027t exceed 100\u0026nbsp;000.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eReplace question marks in \u003ci\u003es\u003c/i\u003e and in \u003ci\u003et\u003c/i\u003e with hieroglyphs in such a way \r\nthat distance between the strings that are obtained by replacement is \r\nminimal. Output the resulting distance.\u003c/div\u003e\u003c/div\u003e"}},{"title":"Sample","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":"\u003cdiv class\u003d\"problem_par\"\u003e\u003cdiv class\u003d\"problem_par_normal\"\u003eYou need replace the question mark in \u003ci\u003es\u003c/i\u003e with the third hieroglyph, and\r\nquestion marks in \u003ci\u003et\u003c/i\u003e with the first and the second hieroglyphs respectively.\r\nCyclical string “21132” has substrings “2113”, “1132”, “1322”, \r\n“3221” and “2211”. Hamming distance from string “3132” to these \r\nsubstrings is equal to three, one, three, three, four respectively. The sum \r\nof these distances is equal to fourteen.\u003c/div\u003e\u003c/div\u003e"}}]}