#include <iostream>
using namespace std;
 
class Solution {
public:
    string util(string str, int currLevel, int finalLevel) {
        if(currLevel==finalLevel) return str;
 
        string newString="";
        for(char& each: str) {
            if(each=='0')
                newString+="01";
            if(each=='1')
                newString+="10";
        }
 
        return util(newString, currLevel+1, finalLevel);
    }
 
    int kthGrammar(int N, int K) {
        string ans = util("0", 1, N);
 
        return ans[K-1]-'0';
    }
};
 
int main() {
	// your code goes here
	cout<<kthGrammar(2, 2);
	return 0;
}

I2luY2x1ZGUgPGlvc3RyZWFtPgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY2xhc3MgU29sdXRpb24gewpwdWJsaWM6CiAgICBzdHJpbmcgdXRpbChzdHJpbmcgc3RyLCBpbnQgY3VyckxldmVsLCBpbnQgZmluYWxMZXZlbCkgewogICAgICAgIGlmKGN1cnJMZXZlbD09ZmluYWxMZXZlbCkgcmV0dXJuIHN0cjsKICAgICAgICAKICAgICAgICBzdHJpbmcgbmV3U3RyaW5nPSIiOwogICAgICAgIGZvcihjaGFyJiBlYWNoOiBzdHIpIHsKICAgICAgICAgICAgaWYoZWFjaD09JzAnKQogICAgICAgICAgICAgICAgbmV3U3RyaW5nKz0iMDEiOwogICAgICAgICAgICBpZihlYWNoPT0nMScpCiAgICAgICAgICAgICAgICBuZXdTdHJpbmcrPSIxMCI7CiAgICAgICAgfQogICAgICAgIAogICAgICAgIHJldHVybiB1dGlsKG5ld1N0cmluZywgY3VyckxldmVsKzEsIGZpbmFsTGV2ZWwpOwogICAgfQogICAgCiAgICBpbnQga3RoR3JhbW1hcihpbnQgTiwgaW50IEspIHsKICAgICAgICBzdHJpbmcgYW5zID0gdXRpbCgiMCIsIDEsIE4pOwogICAgICAgIAogICAgICAgIHJldHVybiBhbnNbSy0xXS0nMCc7CiAgICB9Cn07CgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWNvdXQ8PGt0aEdyYW1tYXIoMiwgMik7CglyZXR1cm4gMDsKfQ==