{"code":"kthistr2","name":"Xâu lý thú 2","description":"Khánh Dung có một dãy số nguyên không âm $\\delta=(\\delta_0, \\delta_1,...,\\delta_{n-1})$ thỏa mãn $|\\delta_i-\\delta_{i-1}|\\leq 1$ với mọi $1\\leq i < n$ và một số nguyên dương $m$. Trong bài toán này, Khánh Dung chỉ quan tâm đến các xâu ký tự chỉ gồm các ký tự trong số $m$ ký tự đầu tiên trong bảng chữ cái in thường.\r\n\r\nDung gọi một xâu $\\sigma=\\sigma_0\\sigma_1...\\sigma_{n-1}$ là *xâu lý thú* khi và chỉ khi: với mọi $i, j$ $(0\\leq i, j < n)$ mà $0 < |i-j|\\leq \\delta_i$ thì $\\sigma_i\\ne \\sigma_j$. Với mỗi xâu lý thú $\\sigma$, cô ấy gọi $\\text{rank}(\\sigma)$ là số lượng xâu lý thú có cùng độ dài với xâu $\\sigma$ và có thứ tự từ điển nhỏ hơn hẳn $\\sigma$.\r\n\r\nVới hai xâu thú vị $\\alpha$ và $\\beta$ có cùng độ dài $n$, Dung muốn tìm xâu thú vị $\\gamma$ có cùng độ dài $n$ thỏa mãn $\\text{rank}(\\gamma)=\\text{rank}(\\alpha)+\\text{rank}(\\beta)$ hoặc kết luận không tồn tại xâu ký tự nào như vậy.\r\n\r\nCho biết giá trị $n$, $m$, dãy $\\delta$, và hai xâu $\\alpha$, $\\beta$, bạn hãy lập trình giúp Dung xác định xâu $\\gamma$ nhé!\r\n \r\n#### Input:\r\n - Dòng đầu chứa hai số nguyên dương $n$, $m$ $\\left(1\\leq n\\leq 10^5, 1\\leq m\\leq 5\\right)$.\r\n - Dòng tiếp theo chứa $n$ số nguyên không âm $\\delta_0, \\delta_1,...,\\delta_{n-1}$.\r\n - Dòng tiếp theo chứa xâu $\\alpha$ độ dài $n$.\r\n - Dòng tiếp theo chứa xâu $\\beta$ độ dài $n$.\r\n\r\n#### Output: \r\n- Gồm một xâu lý thú $\\gamma$ độ dài $n$ thỏa mãn $\\text{rank}(\\gamma)=\\text{rank}(\\alpha)+\\text{rank}(\\beta)$. Nếu không tồn tại xâu thỏa mãn thì in ra $-1$.\r\n\r\n!!! question \"Test 1\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        3 5\r\n        1 2 3\r\n        bed\r\n        cad\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        eab\r\n        ```\r\n    ???+ warning \"Note\"\r\n        Xâu lý thú $\\gamma$ cần tìm gồm có $3$ ký tự đôi một khác nhau, đồng thời $\\text{rank}(\\gamma)=\\text{rank}(\\alpha)+\\text{rank}(\\beta)=23+25=48$.  \r\n                \r\n!!! question \"Test 2\"\r\n    ???+ \"Input\"\r\n        ```sample\r\n        4 5\r\n        1 0 0 1\r\n        cacb\r\n        adbc\r\n        ```\r\n    ???+ success \"Output\"\r\n        ```sample\r\n        cddc\r\n        ```\r\n    ???+ warning \"Note\"\r\n        Xâu lý thú $\\gamma$ cần tìm có dạng $\\sigma_0\\sigma_1\\sigma_2\\sigma_3$ với $\\sigma_0\\ne \\sigma_1$ và $\\sigma_2\\ne \\sigma_3$, đồng thời $\\text{rank}(\\gamma)=\\text{rank}(\\alpha)+\\text{rank}(\\beta)=169+45=214$.","points":500.0,"partial":true,"time_limit":1.0,"memory_limit":524288,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}