{"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\u003e小马镇正在举办一年一度的数学节!能够解决这个问题的小马将被尊为$$$\\text{Super Gray Pony}$$$。准备好迎接挑战,尽你最大的努力吧!\u003c/p\u003e\u003cp\u003e在这个问题中,$$$i$$$阶格雷码被递归定义为$$$a^{(i)}$$$ - 一个由$$$2^i$$$个元素组成的二进制数数组,这些元素从$$$0$$$到$$$2^i-1$$$编号。请注意,在这个问题中,\u003cspan class\u003d\"tex-font-style-bf\"\u003e会添加前导零\u003c/span\u003e,以确保每个元素都是一个严格$$$i$$$位的二进制数。具体规则如下:\u003c/p\u003e\u003col\u003e \u003cli\u003e 对于$$$i \u003d 1$$$,$$$a^{(1)}\u003d[0,1]$$$,$$$a^{(1)}[0]\u003d0$$$,$$$a^{(1)}[1]\u003d1$$$。 \u003c/li\u003e\u003cli\u003e 对于$$$i \u0026gt; 1$$$,$$$a^{(i)}$$$的前一半可以通过在$$$a^{(i-1)}$$$中每个元素的最高位前面添加一个$$$0$$$来获得。 \u003c/li\u003e\u003cli\u003e 对于$$$i \u0026gt; 1$$$,$$$a^{(i)}$$$的后一半可以通过在$$$a^{(i-1)}$$$中每个元素的最高位前面添加一个$$$1$$$,然后将这些元素\u003cspan class\u003d\"tex-font-style-bf\"\u003e按照相反的顺序\u003c/span\u003e排列得到。 \u003c/li\u003e\u003c/ol\u003e\u003cp\u003e例如:\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\u003e给定$$$S$$$和$$$k$$$,$$$S_k$$$被定义为:\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\u003e现在给定$$$S$$$和$$$k$$$,你需要计算出$$$S_k$$$的确切值。在这个问题中,$$$S$$$以一个可能带有前导零的$$$n$$$位二进制数的形式给出。\u003c/p\u003e"}},{"title":"输入","value":{"format":"HTML","content":"\u003cp\u003e第一行包含两个整数$$$n,k$$$($$$1\\le n\\le 3\\times 10^6,1\\le k\\le 10^9$$$)。\u003c/p\u003e\u003cp\u003e第二行包含一个长度为$$$n$$$的二进制数$$$S$$$。\u003cspan class\u003d\"tex-font-style-bf\"\u003e最高位在左边,最低位在右边\u003c/span\u003e。\u003c/p\u003e"}},{"title":"输出","value":{"format":"HTML","content":"\u003cp\u003e以一行输出$$$n$$$位二进制数的形式输出$$$S_k$$$,\u003cspan class\u003d\"tex-font-style-bf\"\u003e最高位在左边,最低位在右边\u003c/span\u003e。\u003c/p\u003e"}},{"title":"示例","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"}},{"title":"注意事项","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"}}]}