//Info1 fix code (fix 0707 2255)
#pragma GCC optimize("O3")
#pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define all(v) v.begin(), v.end()
#define pb push_back
#define lb lower_bound
#define gibon ios::sync_with_stdio(false); cin.tie(0);
#define fi first
#define se second
#define pii pair<int, int>
#define pll pair<ll, ll>
typedef long long ll;
using namespace std;
const int mxN=200005;
const int mxM=99999;
const int mxK=60;
struct info{
int plu[2], minu[2], notp, notm;
info(){
plu[0]=plu[1]=minu[0]=minu[1]=notp=notm=0;
}
};
struct segtree{
int seg[4*mxN]={};
int typ;
int f(int a, int b){
if(a==0 || b==0) return a+b;
if(typ==1) return max(a, b);
if(typ==2) return min(a, b);
// warning 방지용
return 0;
}
void init(int n, int t){
for(int i=0;i<4*n;i++) seg[i]=0;
typ=t;
}
void upd(int idx, int s, int e, int pos, int x){
if(s==e){
seg[idx]=x;
return;
}
int mid=(s+e)/2;
if(pos<=mid) upd(2*idx, s, mid, pos, x);
else upd(2*idx+1, mid+1, e, pos, x);
seg[idx]=f(seg[2*idx], seg[2*idx+1]);
}
int solv(int idx, int s1, int e1, int s2, int e2){
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2) return seg[idx];
int mid=(s1+e1)/2;
return f(solv(2*idx, s1, mid, s2, e2), solv(2*idx+1, mid+1, e1, s2, e2));
}
int bin_search1l(int idx, int s1, int e1, int s2, int e2, int x){
if(s1==e1){
return (f(seg[idx], x)==seg[idx] ? s1 : 0);
}
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2){
if(f(seg[idx], x)==seg[idx]){
int mid=(s1+e1)/2;
int lres=bin_search1l(2*idx, s1, mid, s2, e2, x);
if(lres!=0) return lres;
return bin_search1l(2*idx+1, mid+1, e1, s2, e2, x);
}
else return 0;
}
int mid=(s1+e1)/2;
if(s2<=mid){
int lres=bin_search1l(2*idx, s1, mid, s2, e2, x);
if(lres!=0) return lres;
}
return bin_search1l(2*idx+1, mid+1, e1, s2, e2, x);
}
int bin_search1r(int idx, int s1, int e1, int s2, int e2, int x){
if(s1==e1){
return (f(seg[idx], x)==seg[idx] ? s1 : 0);
}
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2){
if(f(seg[idx], x)==seg[idx]){
int mid=(s1+e1)/2;
int rres=bin_search1r(2*idx+1, mid+1, e1, s2, e2, x);
if(rres!=0) return rres;
return bin_search1r(2*idx, s1, mid, s2, e2, x);
}
else return 0;
}
int mid=(s1+e1)/2;
if(s2<=mid){
int lres=bin_search1r(2*idx+1, mid+1, e1, s2, e2, x);
if(lres!=0) return lres;
}
return bin_search1r(2*idx, s1, mid, s2, e2, x);
}
int bin_search2l(segtree &Tp, int idx, int s1, int e1, int s2, int e2, int x1, int x2){
if(s1==e1){
return ((f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]) ? s1 : 0);
}
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2){
if(f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]){
int mid=(s1+e1)/2;
int lres=bin_search2l(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
if(lres!=0) return lres;
return bin_search2l(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
}
else return 0;
}
int mid=(s1+e1)/2;
if(s2<=mid){
int lres=bin_search2l(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
if(lres!=0) return lres;
}
return bin_search2l(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
}
int bin_search2r(segtree &Tp, int idx, int s1, int e1, int s2, int e2, int x1, int x2){
if(s1==e1){
return ((f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]) ? s1 : 0);
}
if(s2>e1 || s1>e2) return 0;
if(s2<=s1 && e1<=e2){
if(f(seg[idx], x1)==seg[idx] || Tp.f(Tp.seg[idx], x2)==Tp.seg[idx]){
int mid=(s1+e1)/2;
int rres=bin_search2r(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
if(rres!=0) return rres;
return bin_search2r(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
}
else return 0;
}
int mid=(s1+e1)/2;
if(s2<=mid){
int rres=bin_search2r(Tp, 2*idx+1, mid+1, e1, s2, e2, x1, x2);
if(rres!=0) return rres;
}
return bin_search2r(Tp, 2*idx, s1, mid, s2, e2, x1, x2);
}
};
segtree Tp, Tm, Tmax1, Tmin1, Tmax2, Tmin2;
int N, Q;
pii A[mxN];
pii qry[mxN];
vector <array<int, 3>> v1;
vector <array<int, 3>> ct1;
info I[mxN][2]; // left info, right info
int lim[mxN][2][3]; // left limit, right limit, 각각 plu/ minu/ neutral
int zero[mxN][2][3][4];
// zero[i][j][k][l] = i번째 쿼리에 대해, (j=0: 왼쪽, j=1: 오른쪽)에서 봤을 때 (k=0: left, k=1: right, k=2: neutral limit의 오른쪽/왼쪽)에 (l=0: 0+, l=1: 0-, l=2: +0, l=3: -0)를 만족하는 가장 (왼쪽/오른쪽) 위치
int ans[mxN];
bool cmpp(pii a, pii b){return (a.fi<=b.fi && a.se>=b.se);} // a.fi<=b.fi인 a의 max(a.se)를 관리
bool cmpm(pii a, pii b){return (a.fi>=b.fi && a.se<=b.se);} // a.fi>=b.fi인 a의 min(a.se)를 관리
bool cmpnp(pii a, pii b){return (a.fi>=b.fi || a.se<=b.se);}// max(a.fi), min(a.se)를 관리
bool cmpnm(pii a, pii b){return (a.fi<=b.fi || a.se>=b.se);}// min(a.fi), max(a.se)를 관리
bool chkdir(pii a, pii b, int typ){
if(typ==0 && a.fi==b.fi && a.se>=b.se) return true;
if(typ==1 && a.fi==b.fi && a.se<=b.se) return true;
if(typ==2 && a.fi>=b.fi && a.se==b.se) return true;
if(typ==3 && a.fi<=b.fi && a.se==b.se) return true;
return false;
}
void input(){
cin >> N >> Q;
for(int i=1;i<=N;i++) cin >> A[i].fi >> A[i].se;
for(int i=1;i<=Q;i++) cin >> qry[i].fi >> qry[i].se;
}
void make_cr(){
vector <int> cx, cy;
for(int i=1;i<=N;i++) cx.push_back(A[i].fi), cy.push_back(A[i].se);
sort(all(cx)), sort(all(cy));
cx.erase(unique(all(cx)), cx.end());
cy.erase(unique(all(cy)), cy.end());
for(int i=1;i<=N;i++) A[i].fi=lower_bound(all(cx), A[i].fi)-cx.begin()+1, A[i].se=lower_bound(all(cy), A[i].se)-cy.begin()+1;
for(int i=1;i<=Q;i++){
int i1=lower_bound(all(cx), qry[i].fi)-cx.begin(), i2=lower_bound(all(cy), qry[i].se)-cy.begin();
if(i1==cx.size() || i2==cy.size() || cx[i1]!=qry[i].fi || cy[i2]!=qry[i].se) qry[i]=pii(N+1, N+1);
else qry[i]=pii(i1+1, i2+1);
}
}
void make_segtree(){
Tmin1.init(N, 2); Tmax1.init(N, 1); Tmin2.init(N, 2); Tmax2.init(N, 1);
for(int i=1;i<=N;i++){
Tmin1.upd(1, 1, N, i, A[i].fi);
Tmax1.upd(1, 1, N, i, A[i].fi);
Tmax2.upd(1, 1, N, i, A[i].se);
Tmin2.upd(1, 1, N, i, A[i].se);
}
}
void make_ct1(){
for(int i=1;i<=N;i++) v1.push_back({A[i].fi, A[i].se, i});
for(int i=1;i<=Q;i++) ct1.push_back({qry[i].fi, qry[i].se, i});
sort(all(v1), [](array<int, 3> a, array<int, 3> b){return a[0]<b[0];});
}
int bin_search1(segtree &T, int l, int r, int val, bool lr){
int allres=T.solv(1, 1, N, l, r);
if(T.f(allres, val)!=allres) return 0;
if(lr) return T.bin_search1l(1, 1, N, l, r, val);
else return T.bin_search1r(1, 1, N, l, r, val);
}
int bin_search2(segtree &T1, segtree &T2, int l, int r, pii val, bool lr){ // left면 lr이 true
pii allres=pii(T1.solv(1, 1, N, l, r), T2.solv(1, 1, N, l, r));
if(T1.f(allres.fi, val.fi)!=allres.fi && T2.f(allres.se, val.se)!=allres.se) return 0;
if(lr) return T1.bin_search2l(T2, 1, 1, N, l, r, val.fi, val.se);
else return T1.bin_search2r(T2, 1, 1, N, l, r, val.fi, val.se);
}
void make_info1(){
int vi;
sort(all(ct1), [](array<int, 3> a, array<int, 3> b){return a[0]<b[0];});
vi=0;
Tp.init(N, 1), Tm.init(N, 2);
for(auto [val1, val2, idx] : ct1){
while(vi!=v1.size() && v1[vi][0]<=val1){
Tp.upd(1, 1, N, v1[vi][2], v1[vi][1]);
vi++;
}
I[idx][0].plu[0]=bin_search1(Tp, 1, N, val2, 1);
if(I[idx][0].plu[0]!=0 && I[idx][0].plu[0]!=N) I[idx][0].plu[1]=bin_search1(Tp, I[idx][0].plu[0]+1, N, val2, 1);
I[idx][0].notp=bin_search2(Tmax1, Tmin2, 1, N, pii(val1, val2), 1);
I[idx][0].notm=bin_search2(Tmin1, Tmax2, 1, N, pii(val1, val2), 1);
I[idx][1].plu[0]=bin_search1(Tp, 1, N, val2, 0);
if(I[idx][1].plu[0]!=0 && I[idx][1].plu[0]!=1) I[idx][1].plu[1]=bin_search1(Tp, 1, I[idx][0].plu[0]-1, val2, 0);
I[idx][1].notp=bin_search2(Tmax1, Tmin2, 1, N, pii(val1, val2), 0);
I[idx][1].notm=bin_search2(Tmin1, Tmax2, 1, N, pii(val1, val2), 0);
}
reverse(all(ct1));
vi=N-1;
for(auto [val1, val2, idx] : ct1){
while(vi!=-1 && v1[vi][0]>=val1){
Tm.upd(1, 1, N, v1[vi][2], v1[vi][1]);
vi--;
}
I[idx][0].minu[0]=bin_search1(Tm, 1, N, val2, 1);
if(I[idx][0].minu[0]!=0 && I[idx][0].minu[0]!=N) I[idx][0].minu[1]=bin_search1(Tm, I[idx][0].minu[0]+1, N, val2, 1);
I[idx][1].minu[0]=bin_search1(Tm, 1, N, val2, 0);
if(I[idx][1].minu[0]!=0 && I[idx][1].minu[0]!=1) I[idx][1].minu[1]=bin_search1(Tm, 1, I[idx][0].minu[0]-1, val2, 0);
}
}
void make_lim(){
for(int i=1;i<=Q;i++){
info li=I[i][0], ri=I[i][1];
//-- left limit
if(li.plu[0]!=0 && (li.plu[0]==1 || (li.notm!=0 && li.plu[0]>li.notm))) lim[i][0][0]=li.plu[0];
else if(li.plu[1]!=0) lim[i][0][0]=li.plu[1];
if(li.minu[0]!=0 && (li.minu[0]==1 || (li.notp!=0 && li.minu[0]>li.notp))) lim[i][0][1]=li.minu[0];
else if(li.minu[1]!=0) lim[i][0][1]=li.minu[1];
if(li.notp!=0 && li.notm!=0) lim[i][0][2]=max(li.notp, li.notm);
//-- right limit
if(ri.plu[0]!=0 && (ri.plu[0]==N || (ri.notm!=0 && ri.plu[0]<ri.notm))) lim[i][1][0]=ri.plu[0];
else if(ri.plu[1]!=0) lim[i][1][0]=ri.plu[1];
if(ri.minu[0]!=0 && (ri.minu[0]==N || (ri.notp!=0 && ri.minu[0]<ri.notp))) lim[i][1][1]=ri.minu[0];
else if(ri.minu[1]!=0) lim[i][1][1]=ri.minu[1];
if(ri.notp!=0 && ri.notm!=0) lim[i][1][2]=min(ri.notp, ri.notm);
}
}
vector <pii> v2[2][mxN];
vector <array<int, 4>> ct2[2][2][mxN];
segtree T0max, T0min;
// ct2[i][j][k]: (a[0], N] /i/ [1, a[0])에 있는 값들 중 (k, a[1]+), (k, a[1]-) /j/ (a[1]+, k), (a[1]-, k)인 값 찾아서 zero[a[2]][j][a[3]]에 넣기 (ct2[0]: left, ct2[1]: right)
void make_zero(){
T0max.init(N, 1), T0min.init(N, 2);
for(int i=1;i<=N;i++) v2[0][A[i].fi].emplace_back(A[i].se, i), v2[1][A[i].se].emplace_back(A[i].fi, i);
for(int i=1;i<=Q;i++){
for(int j=0;j<2;j++) for(int k=0;k<3;k++) if(lim[i][j][k]!=0){
ct2[j][0][qry[i].fi].push_back({lim[i][j][k], qry[i].se, i, k});
ct2[j][1][qry[i].se].push_back({lim[i][j][k], qry[i].fi, i, k});
}
}
for(int i=1;i<=N;i++){
for(int j=0;j<2;j++){
for(auto [y, idx] : v2[j][i]){
T0max.upd(1, 1, N, idx, y);
T0min.upd(1, 1, N, idx, y);
}
for(int dir=0;dir<=1;dir++){
for(auto [pos, val, idx1, idx2] : ct2[dir][j][i]){
if(j==0 && dir==0 && pos!=N) zero[idx1][dir][idx2][0]=bin_search1(T0max, pos+1, N, val, 1);
if(j==0 && dir==1 && pos!=1) zero[idx1][dir][idx2][0]=bin_search1(T0max, 1, pos-1, val, 0);
if(j==0 && dir==0 && pos!=N) zero[idx1][dir][idx2][1]=bin_search1(T0min, pos+1, N, val, 1);
if(j==0 && dir==1 && pos!=1) zero[idx1][dir][idx2][1]=bin_search1(T0min, 1, pos-1, val, 0);
if(j==1 && dir==0 && pos!=N) zero[idx1][dir][idx2][2]=bin_search1(T0max, pos+1, N, val, 1);
if(j==1 && dir==1 && pos!=1) zero[idx1][dir][idx2][2]=bin_search1(T0max, 1, pos-1, val, 0);
if(j==1 && dir==0 && pos!=N) zero[idx1][dir][idx2][3]=bin_search1(T0min, pos+1, N, val, 1);
if(j==1 && dir==1 && pos!=1) zero[idx1][dir][idx2][3]=bin_search1(T0min, 1, pos-1, val, 0);
}
}
for(auto [y, idx] : v2[j][i]){
T0max.upd(1, 1, N, idx, 0);
T0min.upd(1, 1, N, idx, 0);
}
}
}
}
vector <pair<pii, int>> v00, vq;
segtree T3max, T3min;
bool possible(array<bool, 3> lcond, array<bool, 3> rcond, array<bool, 3> mcond, bool dir1, bool dir2){ // dir: (0+) or (-0), cond: + - 0
if(mcond[0] && mcond[1]) return true;
bool lp=(lcond[0] || (dir1 && lcond[2])), lm=(lcond[1] || (!dir1 && lcond[2]));
bool rp=(rcond[0] || (dir2 && rcond[2])), rm=(rcond[1] || (!dir2 && rcond[2]));
if(mcond[0] && (lm || rm)) return true;
if(mcond[1] && (lp || rp)) return true;
if((lp && rm) || (rp && lm)) return true;
return false;
}
bool f(int idx, int lpos, int rpos, bool dir1, bool dir2){
if(lpos==0 || rpos==0 || lpos>=rpos) return false;
array<bool, 3> lcond, rcond, mcond={0, 0, 1};
for(int j=0;j<3;j++) lcond[j]=(lim[idx][0][j]!=0 && lpos>lim[idx][0][j]);
for(int j=0;j<3;j++) rcond[j]=(lim[idx][1][j]!=0 && rpos<lim[idx][1][j]);
if(lpos==1) lcond[2]=1;
if(rpos==N) rcond[2]=1;
if(lpos==rpos-1){
mcond[0]=mcond[1]=0;
}
else{
int resp=T3max.solv(1, 1, N, lpos+1, rpos-1);
mcond[0]=(resp!=0 && resp>=qry[idx].se);
int resm=T3min.solv(1, 1, N, lpos+1, rpos-1);
mcond[1]=(resm!=0 && resm<=qry[idx].se);
}
return possible(lcond, rcond, mcond, dir1, dir2);
}
void solv(){ // 나중에 sweeping으로 교체
for(int i=1;i<=N;i++) v00.emplace_back(A[i], i);
for(int i=1;i<=Q;i++) vq.emplace_back(qry[i], i);
sort(all(v00)), sort(all(vq));
T3max.init(N, 1), T3min.init(N, 2);
int ulc=0, urc=0;
for(int i=1;i<=N;i++) T3min.upd(1, 1, N, i, A[i].se);
pii lqry[16], rqry[16];
int lqi, rqi;
int lc=0, rc=0;
for(auto [qval, i] : vq){
//-- segtree upd
while(ulc!=N && v00[ulc].fi.fi<qval.fi){
T3min.upd(1, 1, N, v00[ulc].se, 0);
ulc++;
}
while(urc!=N && v00[urc].fi.fi<=qval.fi){
T3max.upd(1, 1, N, v00[urc].se, v00[urc].fi.se);
urc++;
}
// -- 00 case
while(lc!=N && v00[lc].fi<qval) lc++;
while(rc!=N && (v00[rc].fi<qval || v00[rc].fi==qval)) rc++;
if(rc>=lc+3){
ans[i]=1;
continue;
}
for(int j=lc;j<rc;j++){
int pos=v00[j].se;
bool lnotp=(I[i][0].notp!=0 && I[i][0].notp<pos), lnotm=(I[i][0].notm!=0 && I[i][0].notm<pos);
bool rnotp=(I[i][1].notp!=0 && I[i][1].notp>pos), rnotm=(I[i][1].notm!=0 && I[i][1].notm>pos);
if(pos==1) lnotp=true, lnotm=true;
if(pos==N) rnotp=true, rnotm=true;
if(lnotp && lnotm && rnotp && rnotm) ans[i]=1;
}
if(ans[i]==1) continue;
//-- 0x, x0 case
for(int j=0;j<16;j++) lqry[j]=rqry[j]=pii();
lqi=0, rqi=0;
for(int llvl=0;llvl<3;llvl++) for(int dir1=0;dir1<4;dir1++){
int lpos=zero[i][0][llvl][dir1];
if(lpos!=0) lqry[lqi++]={lpos, dir1};
}
if(A[1].fi==qry[i].fi || A[1].se==qry[i].se){
for(int j=0;j<4;j++) if(chkdir(A[1], qry[i], j)){
lqry[lqi++]={1, j};
}
}
for(int rlvl=0;rlvl<3;rlvl++) for(int dir2=0;dir2<4;dir2++){
int rpos=zero[i][1][rlvl][dir2];
if(rpos!=0) rqry[rqi++]={rpos, dir2};
}
if(A[N].fi==qry[i].fi || A[N].se==qry[i].se){
for(int j=0;j<4;j++) if(chkdir(A[N], qry[i], j)){
rqry[rqi++]={N, j};
}
}
for(int j=0;j<lqi;j++) for(int k=0;k<rqi;k++){
if(ans[i]==1) break;
auto [lpos, dir1]=lqry[j];
auto [rpos, dir2]=rqry[k];
if((dir1<2 && dir2<2) || (dir1>=2 && dir2>=2)) continue;
if(f(i, lpos, rpos, (dir1==0 || dir1==3), (dir2==0 || dir2==3))) ans[i]=1;
}
}
}
int main(){
gibon
input();
make_cr();
make_segtree();
make_ct1();
make_info1();
make_lim();
make_zero();
solv();
for(int i=1;i<=Q;i++) if(ans[i]) cout << i << " ";
}
