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;
}