#include<bits/stdc++.h>
#define For(i,a,b) for(int i=(a);i<=(b);++i)
#define Rep(i,a,b) for(int i=(a);i>=(b);--i)
#define ll long long
using namespace std;
inline int read()
{
	char c=getchar();int x=0;bool f=0;
	for(;!isdigit(c);c=getchar())f^=!(c^45);
	for(;isdigit(c);c=getchar())x=(x<<1)+(x<<3)+(c^48);
	if(f)x=-x;return x;
}

#define fi first
#define se second
#define pb push_back
#define mkp make_pair
typedef pair<int,int>pii;
typedef vector<int>vi;

#define maxn 500005
#define inf 0x3f3f3f3f

/*
10110101101
11100101101
  /\
 /  \  /
/    \/
*/

int solve(int n,int k,int s){
	int mn=0,c=0,id=0;
	For(i,0,n-1){
		if(s>>i&1)++c;
		else --c;
		if(c>mn) mn=c,id=i;
	}
//	cout<<"id "<<id<<endl;
	return s^(1<<id);
}

//signed main(){
//	int n=6,k=4;
//	For(i,0,(1<<n)-1)
//		if(__builtin_popcount(i)==k){
//			int t=solve(n,k,i);
//			if(__builtin_popcount(t)!=k-1)puts("wa");
//			cout<<i<<" "<<t<<"\n";
//		}
//}

/*
111110

101110
011110

*/