{"trustable":true,"prependHtml":"\u003cstyle type\u003d\u0027text/css\u0027\u003e\n .input, .output {\n border: 1px solid #888888;\n }\n .output {\n margin-bottom: 1em;\n position: relative;\n top: -1px;\n }\n .output pre, .input pre {\n background-color: #EFEFEF;\n line-height: 1.25em;\n margin: 0;\n padding: 0.25em;\n }\n \u003c/style\u003e\n \u003clink rel\u003d\"stylesheet\" href\u003d\"//codeforces.org/s/96598/css/problem-statement.css\" type\u003d\"text/css\" /\u003e\n\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027$$$$$$\u0027, right: \u0027$$$$$$\u0027, display: true},\n {left: \u0027$$$\u0027, right: \u0027$$$\u0027, display: false},\n {left: \u0027$$\u0027, right: \u0027$$\u0027, display: true},\n {left: \u0027$\u0027, right: \u0027$\u0027, display: false}\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePonyville is on its annual math festival! The ponies who are able to overcome this problem would be honored as $$$\\text{Super Gray Pony}$$$. Get yourself prepared for the problem and try your best!\u003c/p\u003e\u003cp\u003eIn this problem, the $$$i$$$-order Gray Code is defined recursively as $$$a^{(i)}$$$ - an array of binary numbers with $$$2^i$$$ elements numbered from $$$0$$$ to $$$2^i-1$$$. Note that in this problem \u003cspan class\u003d\"tex-font-style-bf\"\u003eleading zeros are added\u003c/span\u003e to make each element a strictly $$$i$$$-bit binary number. The specific rules are as follows:\u003c/p\u003e\u003col\u003e \u003cli\u003e For $$$i \u003d 1$$$, $$$a^{(1)}\u003d[0,1]$$$, $$$a^{(1)}[0]\u003d0$$$, $$$a^{(1)}[1]\u003d1$$$. \u003c/li\u003e\u003cli\u003e For $$$i \u0026gt; 1$$$, the first half of $$$a^{(i)}$$$ $$$(a^{(i)}[0], ..., a^{(i)}[2^{i - 1} - 1])$$$ can be obtained by adding a digit $$$0$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$. \u003c/li\u003e\u003cli\u003e For $$$i \u0026gt; 1$$$, the second half of $$$a^{(i)}$$$ $$$(a^{(i)}[2^{i - 1}], ..., a^{(i)}[2^{i} - 1])$$$ can be obtained by adding a digit $$$1$$$ in front of the highest bit of each element in $$$a^{(i-1)}$$$ and then arrange these elements \u003cspan class\u003d\"tex-font-style-bf\"\u003ein a reversed order\u003c/span\u003e. \u003c/li\u003e\u003c/ol\u003e\u003cp\u003eFor example:\u003c/p\u003e\u003cul\u003e \u003cli\u003e $$$a^{(1)}\u003d[0,1]$$$ \u003c/li\u003e\u003cli\u003e $$$a^{(2)}\u003d[00, 01] + \\text{rev}([10, 11])\u003d[00, 01, 11, 10]$$$ \u003c/li\u003e\u003cli\u003e $$$a^{(3)}\u003d[000, 001, 011, 010] + \\text{rev}([100, 101, 111, 110])\u003d[000, 001, 011, 010, 110, 111, 101, 100]$$$ \u003c/li\u003e\u003c/ul\u003e\u003cp\u003eGiven $$$S$$$ and $$$k$$$, $$$S_k$$$ is defined as:\u003c/p\u003e\u003cp\u003e$$$$$$ S_k\u003d\\underbrace{a^{(n)}[a^{(n)}[\\ldots a^{(n)}}_{k \\times a^{(n)}}[S]\\ldots ]] $$$$$$\u003c/p\u003e\u003cp\u003eNow given $$$S$$$ and $$$k$$$, you need to calculate the exact value of $$$S_k$$$. In this problem, $$$S$$$ is given in the form of an $$$n$$$-bit binary number, possibly with leading zeros.\u003c/p\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003eThe first line contains two integers $$$n,k$$$ ($$$1\\le n\\le 3\\times 10^6,1\\le k\\le 10^9$$$).\u003c/p\u003e\u003cp\u003eThe second line contains a binary number $$$S$$$ of length $$$n$$$. \u003cspan class\u003d\"tex-font-style-bf\"\u003eThe highest bit is on the left and the lowest bit is on the right\u003c/span\u003e. \u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003eOutput $$$S_k$$$ in the form of an $$$n$$$-bit binary number in a single line, with \u003cspan class\u003d\"tex-font-style-bf\"\u003eits highest bit on the left and the lowest bit on the right\u003c/span\u003e. \u003c/p\u003e"}},{"title":"Examples","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\u003e3 5\n011\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e010\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n"}},{"title":"Note","value":{"format":"HTML","content":"\u003cp\u003e$$$a^{(3)}\u003d[000, 001, 011, 010, 110, 111, 101, 100]$$$\u003c/p\u003e\u003cp\u003e$$$S_1\u003da^{(3)}[(011)_2]\u003da^{(3)}[3]\u003d010$$$\u003c/p\u003e\u003cp\u003e$$$S_2\u003da^{(3)}[(010)_2]\u003da^{(3)}[2]\u003d011$$$\u003c/p\u003e\u003cp\u003e$$$S_3\u003da^{(3)}[(011)_2]\u003da^{(3)}[3]\u003d010$$$\u003c/p\u003e\u003cp\u003e$$$S_4\u003da^{(3)}[(010)_2]\u003da^{(3)}[2]\u003d011$$$\u003c/p\u003e\u003cp\u003e$$$S_5\u003da^{(3)}[(011)_2]\u003da^{(3)}[3]\u003d010$$$\u003c/p\u003e"}}]}