def getValidWord(s, dictionary):
    def isSubSequence(word, string):
        it = iter(string)
        return all(c in it for c in word)
    
    validWords = [word for word in dictionary if isSubSequence(word, s)]
    
    if not validWords:
        return "-1"
    
    return min(validWords, key=lambda x: (len(x), x))

long equalize(vector<long> power){
    sort(power.begin(), power.end());
    int n = power.size();
    long mid = power[n/2];
    long res = 0;

    for(int i=0;i<n;i++){
        res += abs(power[i] - mid);
    }
    return res;
}

#include <bits/stdc++.h>
using namespace std;
void aa(vector<vector<char>>& board) {
    int rows = board.size();
    int cols = board[0].size();
    for (int i = 0; i < rows; ++i) {
        int rightmost = cols - 1;
        for (int j = cols - 1; j >= 0; --j) {
            if (board[i][j] == '*') {
                rightmost = j - 1;
            } else if (board[i][j] == '#') {
                if (j != rightmost) {
                    board[i][rightmost] = '#';
                    board[i][j] = '-';
                }
                rightmost--;
            }
        }
    }
}

void bb(vector<vector<char>>& board) {
    int rows = board.size();
    int cols = board[0].size();

    for (int j = 0; j < cols; ++j) {
        int bottommost = rows - 1;
        for (int i = rows - 1; i >= 0; --i) {
            if (board[i][j] == '*') {
                bottommost = i - 1;
            } else if (board[i][j] == '#') {
                if (i != bottommost) {
                    board[bottommost][j] = '#';
                    board[i][j] = '-';
                }
                bottommost--;
            }
        }
    }
}
void pushBoxes(vector<vector<char>>& board) {
    aa(board);
    bb(board);
}

#include <bits/stdc++.h>
using namespace std;
int solve(long numberToFind) {
    if (numberToFind <= 0) {
        return 0;
    }
    int cnt = 0;
    bool done = false;
    for (int i = 0; i < 33; ++i) {
        if (numberToFind < pow(2, i)) {
            long result = 0;
            long previous = 0;
            for (int j = i - 1; j >= 0; --j) {
                result = numberToFind - previous - pow(2, j);
                if (result == 0) {
                    cnt++;
                    done = true;
                    break;
                }
                if (result == 1) {
                    cnt += 2;
                    done = true;
                    break;
                }
                if (result > 0) {
                    cnt++;
                    previous += pow(2, j);
                }
                if (j == 0) {
                    done = true;
                    break;
                }
            }
        }
        if (done) {
            break;
        }
    }

    return cnt % 3;
}

def findNthDigit(n):
    length = 1
    while length <= n:
        length *= 2
    
    def gd(index, length):
        if length == 1:
            return '0'
        
        hl = length // 2
        if index < hl:
            return gd(index, hl)
        else:
            si = index - hl
            bd = gd(si, hl)
            if bd == '0':
                return '1'
            elif bd == '1':
                return '2'
            else:
                return '0'

    return int(gd(n, length))