{"trustable":true,"sections":[{"title":"题目描述","value":{"format":"MD","content":"通常,人们习惯将所有 $n$ 位二进制串按照字典序排列,例如所有 $2$ 位二进制串按字典序从小到大排列为:$00$,$01$,$10$,$11$。\r\n\r\n格雷码(Gray Code)是一种特殊的 $n$ 位二进制串排列法,它要求相邻的两个二进制串间**恰好**有一位**不同**,特别地,第一个串与最后一个串也算作相邻。\r\n\r\n所有 $2$ 位二进制串按格雷码排列的一个例子为:$00$,$01$,$11$,$10$。\r\n\r\n$n$ 位格雷码不止一种,下面给出其中一种格雷码的生成算法:\r\n1. $1$ 位格雷码由两个 $1$ 位二进制串组成,顺序为:$0$,$1$。\r\n2. $n + 1$ 位格雷码的前 $2^n$ 个二进制串,可以由依此算法生成的 $n$ 位格雷码(总共 $2^n$ 个 $n$ 位二进制串)按**顺序**排列,再在每个串前加一个前缀 $0$ 构成。\r\n3. $n + 1$ 位格雷码的后 $2^n$ 个二进制串,可以由依此算法生成的 $n$ 位格雷码(总共 $2^n$ 个 $n$ 位二进制串)按**逆序**排列,再在每个串前加一个前缀 $1$ 构成。\r\n\r\n综上,$n + 1$ 位格雷码,由 $n$ 位格雷码的 $2^n$ 个二进制串按顺序排列再加前缀 $0$,和按逆序排列再加前缀 $1$ 构成,共 $2^{n+1}$ 个二进制串。另外,对于 $n$ 位格雷码中的 $2^n$ 个二进制串,我们按上述算法得到的排列顺序将它们从 $0 \\sim 2^n - 1$ 编号。\r\n\r\n按该算法,$2$ 位格雷码可以这样推出:\r\n1. 已知 $1$ 位格雷码为 $0$,$1$。\r\n2. 前两个格雷码为 $00$,$01$。后两个格雷码为 $11$,$10$。合并得到 $00$,$01$,$11$,$10$,编号依次为 $0 \\sim 3$。\r\n\r\n同理,$3$ 位格雷码可以这样推出:\r\n1. 已知 $2$ 位格雷码为:$00$,$01$,$11$,$10$。\r\n2. 前四个格雷码为:$000$,$001$,$011$,$010$。后四个格雷码为:$110$,$111$,$101$,$100$。合并得到:$000$,$001$,$011$,$010$,$110$,$111$,$101$,$100$,编号依次为 $0 \\sim 7$。\r\n\r\n现在给出 $n, k$,请你求出按上述算法生成的 $n$ 位格雷码中的 $k$ 号二进制串。"}},{"title":"输入格式","value":{"format":"MD","content":"从文件 `code.in` 中读入数据。\r\n\r\n仅一行两个整数 $n, k$,意义见题目描述。"}},{"title":"输出格式","value":{"format":"MD","content":"输出到文件 `code.out` 中。\r\n\r\n仅一行一个 $n$ 位二进制串表示答案。"}},{"title":"样例 1","value":{"format":"MD","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\u003e2 3\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e10\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n$2$ 位格雷码为:$00$,$01$,$11$,$10$,编号从 $0 \\sim 3$,因此 $3$ 号串是 $10$。"}},{"title":"样例 2","value":{"format":"MD","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\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e111\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n$3$ 位格雷码为:$000$,$001$,$011$,$010$,$110$,$111$,$101$,$100$,编号从 $0 \\sim 7$,因此 $5$ 号串是 $111$。\n\n\n\n详见附加文件 `code3.in/ans`"}},{"title":"数据范围与提示","value":{"format":"MD","content":"对于 $50\\%$ 的数据:$n \\le 10$;\r\n\r\n对于 $80\\%$ 的数据:$k \\le 5 \\times 10^6$;\r\n\r\n对于 $95\\%$ 的数据:$k \\le 2^{63} − 1$;\r\n\r\n对于 $100\\%$ 的数据:$1 \\le n \\le 64 , 0 \\le k \u003c 2^n$。"}}]}