分析

首先想到的一个优化就是考虑去掉一些没用的点。怎么做呢？

我们可以把满足：

• $x,y$ 在所有点中出现次数 $\le 2$。
• $(x,y)$ 没有访问过。

这些条件的点存储起来，构造集合 $S$，查询时只需要找这些点。

证明

现在我们要证明：若 $|S|\ge 5$，对于任意一个 $t(x,y)$，$S$ 中存在 $p(x_p,y_p)$，满足 $x_p≠x,y_p≠y$。

设 $A=\{q\in S|x_q=x\}$。

设 $B=\{q\in S|y_q=y\}$。

根据定义，$|A|\le 2,|B|\le 2$，所以 $|A\cup B|\le|A|+|B|\le 4<|S|$。

所以必定存在。

对于 $|S|\le 4$：

如果有解，必然 $x_p≠x,y_p≠y$，在 $S$ 中。

如果无解，必然不存在 $x_p≠x,y_p≠y$，$S$ 中不存在。

解释

解释为什么限制 $x,y$ 的出现为 $2$ 不是 $1$：

if(mx[qp.x]<=2&&my[qp.y]<=2&&!vis[qp]){
	++mx[qp.x];
	++my[qp.y];
	vis[qp]=1;
	p.emplace_back((node){qp,i});
}

这是因为可能存在 $1$ 个点是被摧毁的，且 $mx_x=1$，必须限制为 $2$，才能找到没有被摧毁的那一个点。

时间复杂度

与 $t$ 共享 $x$ 或 $y$ 坐标的点最多有 $4$ 个（$x$ 相同的最多 $2$ 个，$y$ 相同的最多 $2$ 个）。

$O(n\log n+q)$，主要是使用了 map。

//SPJ:???
// #include<bits/stdc++.h>
#include<bits/extc++.h>
#define gp __gnu_pbds::gp_hash_table
#define endl '\n'
#define hh puts("")
//#define int long long
#define uap unordered_map
#define uet unordered_set
#define sr() srand(time(NULL))
#define rando(cntmax,istart,rng) for(int i=istart,cnt=0;cnt<=cntmax;cnt++,i=(rand()%rng))
#define lrfor(l,r) for(int cnt=1,i=l,j=r,forid=i;i<j&&l<=i&&i<=r&&l<=j&&j<=r;i+=cnt%2,j-=cnt%2,forid=(cnt%2?j:i),++cnt)
#define lrfor2(l,r) for(size_t cnt=1,i=l,j=r,forid=i;i<j&&l<=i&&i<=r&&l<=j&&j<=r;i+=cnt%2,j-=cnt%2,forid=(cnt%2?j:i),++cnt)
#define IAKIOI ios::sync_with_stdio(0);cin.tie(0);cout.tie(0)
#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,mn,stdin),p1==p2)?EOF:*p1++)
namespace IO{
	const int mn=1e6+100;
	char buf[mn],*p1=buf,*p2=buf;
	inline int read(){
		int x=0,f=1;char ch=getchar();
		while (ch<'0'||ch>'9'){if (ch=='-')f=-1;ch=getchar();}
		while (ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+ch-48;ch=getchar();}
		return x*f;
	}
	inline void write(int x){
		if(x<0){putchar('-');x=-x;}
		if(x>9)write(x/10);
		putchar(x%10+'0');
	}
}using namespace IO;
const int N=1e6+10;
using namespace std;
struct point{
	int x,y;
	friend inline bool operator<(point aa,point bb){return(aa.x!=bb.x?aa.x<bb.x:aa.y<bb.y);}
//	friend inline bool operator==(point aa,point bb){return aa.x==bb.x&&aa.y==bb.y;}
};
struct node{
	point dot;
	int id;
};
gp<int,int> mx,my;
map<point,bool> vis;
vector<node> p;
inline bool check(point che,point man){
	return man.x!=che.x&&man.y!=che.y;
}
signed main(){
	int n,q;
	n=read();
	q=read();
	for(int i=1;i<=n;++i){
		point qp;
		qp.x=read();
		qp.y=read();
		if(mx[qp.x]<=2&&my[qp.y]<=2&&!vis[qp]){
			++mx[qp.x];
			++my[qp.y];
			vis[qp]=1;
			p.emplace_back((node){qp,i});
		}
	}
	while(q--){
		point t;
		t.x=read();
		t.y=read();
		bool flag=0;
		for(int i=1;i<p.size();i++){
			point q=p[i].dot;
			if(check(t,q)){
				write(p[i].id);
				hh;
				flag=1;
				break;
			}
		}
		if(!flag)write(-1),hh;
	}
	return 0;
}

考虑依次选取以下 $7$ 个「关键营地」（需要指出的是，这 $7$ 个「关键营地」不一定都存在）：

• $0$ 号「关键营地」为输入的第一个营地。
• $1$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标相同，$y$ 坐标不同的营地。
• $2$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标相同的营地。
• $3$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同的营地。
• $4$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标相同，$y$ 坐标不同的营地。
• $5$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标不同，$y$ 坐标相同的营地。
• $6$ 号「关键营地」为输入的第一个与 $0$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同，与 $3$ 号「关键营地」$x$ 坐标不同，$y$ 坐标不同的营地。

可以证明，如果某个询问有解，则这 $7$ 个「关键营地」中必有一个是该询问的合法解，证明此处从略。

最终的时间复杂度为 $O(n + q)$，空间复杂度为 $O(1)$。

#include <bits/stdc++.h>
using namespace std;
inline int read()
{
	int x = 0;
	char c = getchar_unlocked();
	while (c < '0') c = getchar_unlocked();
	while (c >= '0')
	{
		x = x * 10 + c - '0';
		c = getchar_unlocked();
	}
	return x;
}
void write(int x)
{
	if (x <= 9)
	{
		putchar_unlocked(x + '0');
		return;
	}
	write(x / 10);
	putchar_unlocked(x % 10 + '0');
}
inline void write_solution(int x)
{
	write(x);
	putchar_unlocked('\n');
}
inline void write_no_solution()
{
	putchar_unlocked('-');
	putchar_unlocked('1');
	putchar_unlocked('\n');
}
struct Point
{
	int x, y, i;
};
Point p[7];
int main()
{
	freopen("laser.in", "r", stdin);
	freopen("laser.out", "w", stdout);
	int n = read(), q = read();
	p[0] = (Point) {read(), read(), 1};
	for (int i = 2; i <= n; i++)
	{
		int x = read(), y = read();
		if (x == p[0].x && y != p[0].y) p[1] = (Point) {x, y, i};
		if (x != p[0].x && y == p[0].y) p[2] = (Point) {x, y, i};
		if (x != p[0].x && y != p[0].y)
		{
			if (!p[3].i)
			{
				p[3] = (Point) {x, y, i};
				continue;
			}
			if (x == p[3].x && y != p[3].y) p[4] = (Point) {x, y, i};
			if (x != p[3].x && y == p[3].y) p[5] = (Point) {x, y, i};
			if (x != p[3].x && y != p[3].y) p[6] = (Point) {x, y, i};
		}
			
	}
	while (q--)
	{
		int x = read(), y = read();
		for (int i = 0; i <= 7; i++)
		{
			if (i == 7)
			{
				write_no_solution();
				break;
			}
			if (x != p[i].x && y != p[i].y && p[i].i)
			{
				write_solution(p[i].i);
				break;
			}
		}
	}
	return 0;
}