初始有一个空的集合，和 \(Q\) 个操作。对于每个操作，有两种类型，分别用如下的两种形式表示：

\(1\ u\) ：加入 \(u\) 到集合
\(2\ x\ k\ s\) ：求一个最大的 \(v\) ，使得:

1. \(v+x\leq s\)
2. \(k|gcd(v,x)\)
3. \(x \oplus v\) 最大

如果找不到满足条件的就输出 \(-1\) .

\(2\leq q\leq 10^5,1\leq u,x,k,s\leq 10^5\)

想了很久没有思路的一道题 . 是我 sbsbsb .

\(\oplus\) 想到什么，想到 \(\mathrm{01\ trie}\) 啊 . 这么普遍的套路我都忘了 qwq .

条件 \(2\) 相当于考虑把 \(k|v\) 并且 \(k|x\) . 此时想到对于每个数，从 \(1\) 到 \(10^5\) 都建立一个 \(\mathrm{trie}\) 树，可以在插入 \(u\) 的时候将 \(u\) 插入到每一个因数的 \(\mathrm{trie}\) 树中，然后每个节点还需要维护一个最小值 \(mn(i)\) ，对付询问 \(1\) . 询问的时候在 \(k\) 的 \(\mathrm{trie}\) 树直接可以找到答案 .

时间复杂度 : \(O(q\log^2 n)\)

空间复杂度 : \(O(n\log n)\)

code

#include<bits/stdc++.h>
using namespace std;
char in[100005];
int iiter=0,llen=0;
inline char get(){
	if(iiter==llen)llen=fread(in,1,100000,stdin),iiter=0;
	if(llen==0)return EOF;
	return in[iiter++];
}
inline int rd(){
	char ch=get();while(ch<'0'||ch>'9')ch=get();
	int res=0;while(ch>='0'&&ch<='9')res=(res<<3)+(res<<1)+ch-'0',ch=get();
	return res;
}
inline void pr(int res){
	if(res==0){putchar('0');return;}
	static int out[10];int len=0;
	if(res<0)putchar('-'),res=-res; 
	while(res>0)out[len++]=res%10,res/=10;
	for(int i=len-1;i>=0;i--)putchar(out[i]+'0');
}
#define PB push_back
#define MP make_pair
#define FI first
#define SE second
const int inf=1e9+10;
const int N=1e5+10;
class trie{
public:
	int cnt=0;
	vector<pair<int,int> >t;
	vector<int>mn;
	void init(){
		t.push_back(MP(-1,-1));
		mn.push_back(inf);
		cnt++;
	}
	inline int new_node(){
		t.push_back(MP(-1,-1));
		mn.push_back(inf);
		return cnt++;
	}
	void upd(int val){
		int x=0;
		for(int i=16;i>=0;i--){
			mn[x]=min(mn[x],val);
			if(val&(1<<i)){
				if(t[x].SE==-1){
					int tmp=new_node();
					t[x].SE=tmp;
				}
				x=t[x].SE;
			}else{
				if(t[x].FI==-1){
					int tmp=new_node();
					t[x].FI=tmp;
				}
				x=t[x].FI;
			}
		}
		mn[x]=val;
	}
	int qry(int val,int s){
		int x=0;
		for(int i=16;i>=0;i--){
			if(t[x].FI==-1&&t[x].SE==-1)return -1;
			if(mn[x]+val>s)return -1;
			if(val&(1<<i)){
				if(t[x].FI!=-1&&mn[t[x].FI]+val<=s)x=t[x].FI;
				else x=t[x].SE;
			}else{
				if(t[x].SE!=-1&&mn[t[x].SE]+val<=s)x=t[x].SE;
				else x=t[x].FI;
			}
		}
		return mn[x];
	}
}Trie[N];
void upd(){
	int x=rd();
	for(int i=1;i*i<=x;i++){
		if(x%i==0){
			Trie[i].upd(x);
			Trie[x/i].upd(x);
		}
	}
}
void qry(){
	int x=rd(),k=rd(),s=rd();
	if(x%k!=0){
		putchar('-');
		putchar('1');
		putchar('\n');
		return;
	}
	pr(Trie[k].qry(x,s));
	putchar('\n');
}
int q;
int main(){
	for(int i=1;i<=100000;i++)Trie[i].init();
	q=rd();
	for(int i=0;i<q;i++){
		int t=rd();
		if(t==1)upd();
		else qry();
	}
	return 0;
}