struct SegBase
{
using ll = long long;
bool zero; // 判断线性基中有无0出现
// maxsiz = log2(值域上边界)
#define maxsiz 64
vector<ll> segbase; // 线性基本身
vector<ll> newbase; // 重构后的线性基
// 初始化线性基大小
SegBase(int n = maxsiz)
{
segbase = vector<ll>(n);
}
// 构建线性基
void insert(ll x)
{
if(x == 0) return ;
int k = log2(x);
if(!segbase[k]) return segbase[k] = x, void();
insert(segbase[k] ^ x);
}
// 查询一个元素是否可以被异或出来
int ask(ll x)
{
for(int i = maxsiz - 1; i >= 0; i--)
if(x >> i & 1) x ^= segbase[i];
return x == 0;
}
// 查询异或最大值
ll askmax()
{
ll res = 0;
for(int i =maxsiz - 1; i >= 0; i--)
if(res ^ segbase[i] > res) res ^= segbase[i];
return res;
}
// 查询异或最小值，（一般来说就是线性基里的最小元素）
ll askmin()
{
if(zero) return 0;
for(int i = 0; i < maxsiz; i++)
if(segbase[i]) return segbase[i];
}
// 查询异或第k小
void rebuild()
{// 重构线性基使得segbase[i]只留下第i位的1，使得他们互不影响
int cnt = 0, top = 0;
for(int i = maxsiz - 1; i >= 0; i--)
{
for(int j = i - 1; j >= 0; j--)
{
if(segbase[i] >> j & 1)
segbase[i] ^= segbase[j];
}
}
for(int i = 0; i < maxsiz; i++)
if(segbase[i])
newbase.push_back(segbase[i]);
}
ll kth(int k)
{// 互不影响之后就可以根据k的二进制选值了，注意线性基是否含0
if(k >= (1 << newbase.size())) return -1;
ll res = 0;
for(int i = maxsiz - 1; i >= 0; i--)
if(k >> i & 1)
res ^= newbase[i];
}
int rank(ll x)
{// kth函数的逆操作
int res = 0;
for(int i = maxsiz - 1; i >= 0; i--)
if(x >= newbase[i])
res |= 1 << i,
x ^= newbase[i];
return res;
}
} ;