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

int solve(int n, int k, int S){
	int mn = 0, p = 0, now = 0;
	for(int i = 1; i <= n; ++ i){
		if((S >> (n - i)) & 1){
			now ++;
		}
		else{
			now --;
		}
		if(now <= mn){
			mn = now;
			p = i;
		}
	}
	// int ans = 0;
	// for(int i = 1; i <= n; ++ i){
	// 	if(i - 1 == p){
	// 		// ans += (1 << (n - i));
	// 		continue;
	// 	}
	// 	else if((S >> (n - i) & 1)){
	// 		ans += (1 << (n - i));
	// 	}
	// }
	// return ans;
	return S ^ (1 << (n - p - 1));
}