{"trustable":true,"prependHtml":"\u003cstyle type\u003d\"text/css\"\u003e\n section pre {\n display: block;\n padding: 9.5px;\n margin: 0 0 10px;\n font-size: 13px;\n line-height: 1.42857143;\n word-break: break-all;\n word-wrap: break-word;\n color: #333;\n background: rgba(255, 255, 255, 0.5);\n border: 1px solid #ccc;\n border-radius: 6px;\n }\n\u003c/style\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n {left: \u0027\\\\[\u0027, right: \u0027\\\\]\u0027, display: true}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"Problem Statement","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eTakahashi is playing a board game called Sugoroku.\u003c/p\u003e\r\n\u003cp\u003eOn the board, there are \u003cvar\u003e\\(N + 1\\)\u003c/var\u003e squares numbered \u003cvar\u003e\\(0\\)\u003c/var\u003e to \u003cvar\u003e\\(N\\)\u003c/var\u003e. Takahashi starts at Square \u003cvar\u003e\\(0\\)\u003c/var\u003e, and he has to stop exactly at Square \u003cvar\u003e\\(N\\)\u003c/var\u003e to win the game.\u003c/p\u003e\r\n\u003cp\u003eThe game uses a roulette with the \u003cvar\u003e\\(M\\)\u003c/var\u003e numbers from \u003cvar\u003e\\(1\\)\u003c/var\u003e to \u003cvar\u003e\\(M\\)\u003c/var\u003e. In each turn, Takahashi spins the roulette. If the number \u003cvar\u003e\\(x\\)\u003c/var\u003e comes up when he is at Square \u003cvar\u003e\\(s\\)\u003c/var\u003e, he moves to Square \u003cvar\u003e\\(s+x\\)\u003c/var\u003e. If this makes him go beyond Square \u003cvar\u003e\\(N\\)\u003c/var\u003e, he loses the game.\u003c/p\u003e\r\n\u003cp\u003eAdditionally, some of the squares are Game Over Squares. He also loses the game if he stops at one of those squares. You are given a string \u003cvar\u003e\\(S\\)\u003c/var\u003e of length \u003cvar\u003e\\(N + 1\\)\u003c/var\u003e, representing which squares are Game Over Squares. For each \u003cvar\u003e\\(i\\)\u003c/var\u003e \u003cvar\u003e\\((0 \\leq i \\leq N)\\)\u003c/var\u003e, Square \u003cvar\u003e\\(i\\)\u003c/var\u003e is a Game Over Square if \u003cvar\u003e\\(S[i] \u003d 1\\)\u003c/var\u003e and not if \u003cvar\u003e\\(S[i] \u003d 0\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003cp\u003eFind the sequence of numbers coming up in the roulette in which Takahashi can win the game in the fewest number of turns possible. If there are multiple such sequences, find the lexicographically smallest such sequence. If Takahashi cannot win the game, print \u003cvar\u003e\\(-1\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Constraints","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cul\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq N \\leq 10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(1 \\leq M \\leq 10^5\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(|S| \u003d N + 1\\)\u003c/var\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(S\\)\u003c/var\u003e consists of \u003ccode\u003e0\u003c/code\u003e and \u003ccode\u003e1\u003c/code\u003e.\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(S[0] \u003d\\)\u003c/var\u003e \u003ccode\u003e0\u003c/code\u003e\u003c/li\u003e\r\n\u003cli\u003e\u003cvar\u003e\\(S[N] \u003d\\)\u003c/var\u003e \u003ccode\u003e0\u003c/code\u003e\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Input","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eInput is given from Standard Input in the following format:\u003c/p\u003e\r\n\u003cpre\u003e\u003cvar\u003e\\(N\\)\u003c/var\u003e \u003cvar\u003e\\(M\\)\u003c/var\u003e\r\n\u003cvar\u003e\\(S\\)\u003c/var\u003e\r\n\u003c/pre\u003e\r\n\r\n\u003c/section\u003e\r\n"}},{"title":"Output","value":{"format":"HTML","content":"\r\n\u003csection\u003e\r\n\u003cp\u003eIf Takahashi can win the game, print the lexicographically smallest sequence among the shortest sequences of numbers coming up in the roulette in which Takahashi can win the game, with spaces in between.\u003c/p\u003e\r\n\u003cp\u003eIf Takahashi cannot win the game, print \u003cvar\u003e\\(-1\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\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\u003e9 3\r\n0001000100\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3 2 3\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eIf the numbers \u003cvar\u003e\\(1\\)\u003c/var\u003e, \u003cvar\u003e\\(3\\)\u003c/var\u003e, \u003cvar\u003e\\(2\\)\u003c/var\u003e, \u003cvar\u003e\\(3\\)\u003c/var\u003e come up in this order, Takahashi can reach Square \u003cvar\u003e\\(9\\)\u003c/var\u003e via Square \u003cvar\u003e\\(1\\)\u003c/var\u003e, \u003cvar\u003e\\(4\\)\u003c/var\u003e, and \u003cvar\u003e\\(6\\)\u003c/var\u003e. He cannot reach Square \u003cvar\u003e\\(9\\)\u003c/var\u003e in three or fewer turns, and this is the lexicographically smallest sequence in which he reaches Square \u003cvar\u003e\\(9\\)\u003c/var\u003e in four turns.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 2","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 4\r\n011110\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e-1\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003cp\u003eTakahashi cannot reach Square \u003cvar\u003e\\(5\\)\u003c/var\u003e.\u003c/p\u003e\r\n\u003c/section\u003e\r\n"}},{"title":"Sample 3","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\u003e6 6\r\n0101010\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e6\r\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\r\n\u003csection\u003e\r\n\r\n\r\n\u003c/section\u003e\r\n\r\n\u003csection\u003e\r\n\u003c/section\u003e\r\n"}}]}