{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003cp\u003eChef loves palindromes! Chef loves them so much he can see palindromes anywhere! Even in this problem.\u003c/p\u003e\n\n\u003cp\u003eChef has \u003cb\u003eN\u003c/b\u003e sequences of white cells. For each \u003cb\u003ei\u003c/b\u003e (1 ≤ \u003cb\u003ei\u003c/b\u003e ≤ \u003cb\u003eN\u003c/b\u003e), the \u003cb\u003ei\u003c/b\u003e-th sequence is formed by \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e cells; Chef has to paint exactly \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e of these cells black.\u003c/p\u003e\n\n\u003cp\u003eAfter painting those cells, Chef writes down the lengths of all white blocks (maximum contiguous subsequences of white cells) from left to right as a single string of digits.\u003c/p\u003e\n\n\u003cp\u003eFor example, if Chef\u0027s initial sequence of cells is \u003cb\u003e\"wwwwwwwww\"\u003c/b\u003e and he has to paint three cells black, he can get \u003cb\u003e\"bwwbwbwww\"\u003c/b\u003e (\u0027w\u0027 stands for a white cell, \u0027b\u0027 for a black cell). In this case, he will write down the lengths of white blocks 2, 1, 3 as the string \u003cb\u003e\"213\"\u003c/b\u003e. He can also paint it to get \u003cb\u003e\"bbwwwwwbw\"\u003c/b\u003e and write down \u003cb\u003e\"51\"\u003c/b\u003e. He can even paint it to get \u003cb\u003e\"bbbwwwwww\"\u003c/b\u003e and write down \u003cb\u003e\"6\"\u003c/b\u003e. There are many other options as well.\u003c/p\u003e\n\n\u003cp\u003eAfter painting all sequences, Chef will have written down a list of \u003cb\u003eN\u003c/b\u003e strings. Now he can reorder these strings \u003cb\u003ein any way he wants\u003c/b\u003e and concatenate them into one string \u003cb\u003eS\u003c/b\u003e.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s time for palindromes! Chef wants the resulting string \u003cb\u003eS\u003c/b\u003e to be as close to a palindrome as possible. The distance of \u003cb\u003eS\u003c/b\u003e to a palindrome is defined as the minimum number of characters in \u003cb\u003eS\u003c/b\u003e that Chef needs to change to get a palindrome.\u003c/p\u003e\n\n\u003cp\u003eFor example, the string \u003cb\u003e\"123345\"\u003c/b\u003e has distance 2 to a palindrome. Strings \u003cb\u003e\"2\"\u003c/b\u003e and \u003cb\u003e\"1221\"\u003c/b\u003e have distance 0 to a palindrome, since they are already palindromes.\u003c/p\u003e\n\n\u003cp\u003eYou need to find a way to paint some cells, reorder and concatenate the resulting strings to form a string \u003cb\u003eS\u003c/b\u003e with the minimum possible distance to a palindrome.\u003c/p\u003e\n\n\n\u003ch3\u003eInput\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eThe first line of the input contains a single integer \u003cb\u003eN\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eThe second line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003el\u003csub\u003e1\u003c/sub\u003e, l\u003csub\u003e2\u003c/sub\u003e, ..., l\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003eThe third line contains \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003eb\u003csub\u003e1\u003c/sub\u003e, b\u003csub\u003e2\u003c/sub\u003e, ..., b\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n\n\u003ch3\u003eOutput\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eThe first \u003cb\u003eN\u003c/b\u003e lines of the output should describe the sequences of cells obtained after painting some cells black.\u003c/li\u003e\n\u003cli\u003eThe \u003cb\u003ei\u003c/b\u003e-th of these lines should contain a single string of length \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e consisting of letters \u0027b\u0027 and \u0027w\u0027. There should be exactly \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e letters \u0027b\u0027 in this string.\u003c/li\u003e\n\u003cli\u003eThe following line should contain a sequence of \u003cb\u003eN\u003c/b\u003e space-separated integers \u003cb\u003ep\u003csub\u003e1\u003c/sub\u003e, p\u003csub\u003e2\u003c/sub\u003e, ..., p\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e denoting the order of strings written down for each sequence of cells — the \u003cb\u003ei\u003c/b\u003e-th string in the concatenation should be the string written down for the \u003cb\u003ep\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e-th sequence of cells. \u003cb\u003ep\u003csub\u003e1\u003c/sub\u003e, p\u003csub\u003e2\u003c/sub\u003e, ..., p\u003csub\u003eN\u003c/sub\u003e\u003c/b\u003e has to be a permutation of numbers 1 through \u003cb\u003eN\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n\n\u003ch3\u003eConstraints\u003c/h3\u003e\n\u003cul\u003e\n\u003cli\u003e\u003cb\u003eN\u003c/b\u003e \u003d 1000\u003c/li\u003e\n\u003cli\u003e1 ≤ \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e ≤ 1000 for each valid \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\n\u003cli\u003e0 ≤ \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003c \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e for each valid \u003cb\u003ei\u003c/b\u003e\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003ch3\u003eExample\u003c/h3\u003e\n\u003cpre\u003e\u003cb\u003eInput:\u003c/b\u003e\n\n4\n5 10 3 8\n2 2 1 2\n\n\u003cb\u003eOutput:\u003c/b\u003e\n\nwwbbw\nwwwwbbwwww\nwwb\nwwwwbbww\n2 1 3 4\n\u003c/pre\u003e\n\n\u003ch3\u003eExplanation\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eIn the first sequence of cells, painting the third and fourth cell gives \u003cb\u003e\"wwbbw\"\u003c/b\u003e with white blocks of lengths 2 and 1, which gives Chef the string \u003cb\u003e\"21\"\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e\"wwwwbbwwww\"\u003c/b\u003e gives Chef the string \u003cb\u003e\"44\"\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e\"wwb\"\u003c/b\u003e gives Chef \u003cb\u003e\"2\"\u003c/b\u003e.\u003c/li\u003e\n\u003cli\u003e\u003cb\u003e\"wwwwbbww\"\u003c/b\u003e gives Chef \u003cb\u003e\"42\"\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\n\u003c/p\u003e\n\u003cp\u003eAfter reordering the strings \"21\", \"44\", \"2\", \"42\" using the permutation (2, 1, 3, 4), Chef gets strings \"44\", \"21\", \"2\", \"42\" and concatenates them to \u003cb\u003eS\u003c/b\u003e \u003d \u003cb\u003e\"4421242\"\u003c/b\u003e. The distance of this string to a palindrome is 1, as Chef only has to replace the last digit with \u00274\u0027 to get a palindrome.\n\u003c/p\u003e\n\n\n\u003ch3\u003eScoring\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eIf your output is invalid in at least one test case, you will receive WA verdict.\u003c/li\u003e\n\u003cli\u003eYour score for each test case is equal to the distance of the string \u003cb\u003eS\u003c/b\u003e (obtained for your output) to a palindrome plus 1.\u003c/li\u003e\n\u003cli\u003eThe total score for a submission is the sum of scores for all test cases.\u003c/li\u003e\n\u003cli\u003eYour goal is to minimise the total score.\u003c/li\u003e\n\u003cli\u003eDuring the contest, your score will be calculated only for one test case from each of groups 1, 3, 5 and 7 of test cases. After the contest, there will be a rejudge using all test cases from all groups.\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n\n\n\u003ch3\u003eTest generation\u003c/h3\u003e\n\u003cp\u003e\u003cul\u003e\n\u003cli\u003eLet random(\u003cb\u003ex\u003c/b\u003e) denote a uniformly random integer in the range [0, \u003cb\u003ex\u003c/b\u003e].\u003c/li\u003e\n\u003cli\u003eFor each valid \u003cb\u003ei\u003c/b\u003e, \u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(999) + 1.\u003c/li\u003e\n\u003cli\u003eThere will be 8 groups of test cases, groups 1, 3, 5 have 3 test-cases each, and groups 2, 4 have 4 test-cases each, while groups 6, 7, 8 have one test-case each.\u003cul\u003e\n\u003cli\u003eIn group 1, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1)) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 2, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 3, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1)))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 4, \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1))))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 5. \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1)))))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 6. \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1)))))))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\u003cli\u003eIn group 7. \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(random(random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1))))))))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\n\n\u003cli\u003eIn group 8. \u003cb\u003eb\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e \u003d random(random(random(random(random(random(random(random(random(random(\u003cb\u003el\u003csub\u003ei\u003c/sub\u003e\u003c/b\u003e - 1)))))))))) for each valid \u003cb\u003ei\u003c/b\u003e.\u003c/li\u003e\n\u003c/ul\u003e\u003c/li\u003e\n\u003c/ul\u003e\u003c/p\u003e\n"}}]}