UnuDoi

#include <bits/stdc++.h>
using namespace std;

char invert(char digit)
{
    if(digit=='1')
        return '2';
    else
        return '1';
}

char _getDigit(int index,int k,string base)
{
    if(k==1)
        return base[index-1];
    const int subSequenceLength=pow(4.0,k-1);
    int repetition=index/subSequenceLength ;
    int innerI;
    if(index%subSequenceLength==0)
        innerI=4;
    else
    {
        innerI=index%subSequenceLength;
        ++repetition;
    }
    char result=_getDigit(innerI,k-1,base);
    if(repetition==2||repetition==3)
        return invert(result);
    return result;
}

char getDigit(int index,string base)
{
    int k=1;
    for(int i=4;i<index;++k,i*=4)
        ;
    return _getDigit(index,k,base);
}

int main()
{
    int digitIndex;
    cin>>digitIndex;
    cout<<getDigit(digitIndex,"1221")<<'\n';
    return 0;
}