#include <bits/stdc++.h> #define ll __int128 #define int long long using namespace std; inline ll read() { ll x = 0, f = 1; char c = getchar(); while (c < '0' || '9' < c) { if (c == '-') f = -1; c = getchar(); } while ('0' <= c && c <= '9') { x = x * 10 + (ll)(c - '0'); c = getchar(); } return x * f; } inline void write(ll x) { if (x < 0) { putchar('-'); x = -x; } if (x > 9) write(x / 10); putchar(x % 10 + '0'); } const int N = 500005, M = 12000005; const ll INF = ((ll)1) << ((ll)120); int n, m, k; int b[N], ch[M][2], tot, sumb[M]; ll a[N], mina[M], mainans; inline int add() { tot++; ch[tot][0] = ch[tot][1] = 0; mina[tot] = (ll)1 << k; sumb[tot] = 0; return tot; } inline void insert(ll a, int b) { int pos = 1, c; mina[pos] = min(mina[pos], a); sumb[pos] += b; for (int i = k - 1; ~i; i--) { c = a >> i & 1; if (ch[pos][c] == 0) ch[pos][c] = add(); pos = ch[pos][c]; mina[pos] = min(mina[pos], a); sumb[pos] += b; } } inline void solve(int pos, int dep, ll amin, int bsum, ll x, ll ans) { if (dep == -1) { mainans = max(mainans, ans); return; } ll base = (ll)1 << dep, all = base - 1; if (!pos) { mainans = max(mainans, amin + (x | all | base)); return; } } inline void work() { scanf("%lld %lld %lld", &n, &m, &k); ll maxa = (ll)1 << k; for (int i = 1; i <= n; i++) { a[i] = read(); } for (int i = 1; i <= n; i++) { scanf("%lld", &b[i]); } mainans = 0; tot = 0; add(); mina[0] = maxa; for (int i = 1; i <= n; i++) insert(a[i], b[i]); if (sumb[1] <= m) { // special test write(mina[1] + maxa - 1); putchar('\n'); return; } solve(1, k - 1, maxa, 0, 0, 0); write(mainans); putchar('\n'); } signed main() { }

#include<bits/stdc++.h> #define ll __int128 #define inf 4e36 #define N 150005 using namespace std; ll read(){ ll x=0,f=1;char ch=getchar(); while(ch<'0' || ch>'9')f=(ch=='-'?-1:f),ch=getchar(); while(ch>='0' && ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); return xf; } void write(ll x){ if(x<0)x=-x,putchar('-'); if(x/10)write(x/10); putchar(x%10+'0'); } ll n,m; ll a[N],tot=1,minn[N121]; ll ans; int ch[N121][2]; long long cost[N121],b[N]; ll maxc(ll x,ll y){ return (x>y?x:y); } void solve(int p,ll k,ll minplus,ll res,long long rescos,ll opr){ if(!p && minplus<inf)return ans=maxc(ans,minplus+(((__int128)1)<<(k+1))-1+opr),void(); else if(!p)return; if(k==-1)return ans=maxc(ans,res),void(); int ls=ch[p][0],rs=ch[p][1],flag=0; if(cost[ls]<=rescos && opr+min(minplus,minn[ls])+((__int128)1<<k)-1>=((__int128)1<<k)+res){ solve(rs,k-1,min(minplus,minn[ls]),res|((__int128)1<<k),rescos-cost[ls],opr); flag=1; } if(cost[rs]<=rescos && opr+min(minplus,minn[rs])+((__int128)1<<k)-1>=res){ solve(ls,k-1,min(minplus,minn[rs]),res|((__int128)1<<k),rescos-cost[rs],opr|((__int128)1<<k)); flag=1; } if(flag)return; solve(ls,k-1,minplus,res,rescos,opr); solve(rs,k-1,minplus,res,rescos,opr|((__int128)1<<k)); } void solve(){ n=read(),m=read();ll k=read();ans=0;minn[0]=inf; for(ll i=1;i<=tot;i++)minn[i]=inf,cost[i]=ch[i][0]=ch[i][1]=0;tot=1; for(ll i=1;i<=n;i++)a[i]=read(); for(ll i=1;i<=n;i++)b[i]=read(); for(ll i=1;i<=n;i++){ ll p=1; minn[p]=min(minn[p],a[i]); cost[p]+=b[i]; for(ll j=k-1;j>=0;j--){ ll it=((a[i]&((__int128)1<<j))?1:0); if(!ch[p][it])ch[p][it]=++tot; p=ch[p][it];minn[p]=min(minn[p],a[i]); cost[p]+=b[i]; } } if(cost[1]<=m){write(minn[1]+((__int128)1<<k)-1);putchar('\n');return;} solve(1,k-1,inf,0,m,0);write(ans);putchar('\n'); } int main(){ memset(minn,0x3f,sizeof(minn)); ll c=read(),T=read();while(T--)solve(); return 0; }