Robots on Grids

#pragma GCC optimize("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC target("avx2,bmi,bmi2,lzcnt,popcnt")
//stupid robot grid

//misaka will carry me to master

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <utility>
#include <cassert>
#include <algorithm>
#include <vector>
#include <functional>
#include <numeric>
#include <set>
#include <map>
#include <queue>
#include <bitset>

#define ll long long
#define lb long double
#define sz(vec) ((int)(vec.size()))
#define all(x) x.begin(), x.end()
#define pb push_back
#define mp make_pair
#define ff first
#define ss second
//probably useful

const lb eps = 1e-9;
const ll mod = 1e9 + 7, ll_max = 1e18;
//const ll mod = (1 << (23)) * 119 +1;
const int MX = 4e5 +10, int_max = 0x3f3f3f3f;
const int SEG = (5e4*4) + (5e4*3 + 1e5 +1)*2 +100;
using namespace std;


struct disc{
    vector<int> vals;
    void add(int x){
        vals.pb(x);
    }
    void norm(){
        sort(all(vals));
        vals.resize(unique(all(vals)) - vals.begin());
    }
    int gind(int x){
        return (lower_bound(all(vals), x) - vals.begin()) +1;
    }
    int zz(){
        return sz(vals);
    }
} xes, yes;
//using namespace disc;
//parallel to x axis is 0
//            y axis is 1
struct segment{
    int dir, pos, l, r;
    int ind;
    segment(){}
    segment(int a, int b, int c, int d){
        dir = a, pos = b, l = c, r = d;
    }
    int left() const{
        return (dir) ? pos : l;
    }
    int down() const{
        return (dir) ? l : pos;
    }
    bool operator < (const segment& b) const{
        if(*this == b) return 0;
        int lhs = left();
        int rhs = b.left();
        if(lhs == rhs){
        if(dir == b.dir){
                if(dir == 0){
                    return (l == b.l) ? (pos < b.pos) : (l < b.l);
                }else{
                    return (pos == b.pos) ? (l < b.l) :(pos < b.pos);
                }
            }else{
                return dir < b.dir;
            }
        }else{
            return lhs < rhs;
        }
    }
    bool operator == (const segment& b) const{
        return dir == b.dir && pos == b.pos && l == b.l && r == b.r;
    }
    void pr(){
        cout << dir << " " << pos << " " << l << " " << r << " " << ind <<  "\n";
    }
} seg[SEG];


const int NN = MX*30; //yes

/** pst **/
int lc[NN], rc[NN];
int IND = 1, sind = 1;
int n, m, K, q, s;
vector<pair<int, int>> adj[SEG];


void dup(int& k){
    IND++;
    lc[IND] = lc[k];
    rc[IND] = rc[k];
    k = IND;
}

void U(int p, int v, int& k, int L, int R){
    //assert(k >= 0);
    if(R <= L || p < L || R <= p) return ;
    dup(k);
    if(L + 1 == R){
        assert(L == p);
        lc[k] = v;
        rc[k] = -1;
        return ;
    }
    int mid = (L + R)/2;
    if(p < mid) U(p, v, lc[k], L, mid);
    else U(p, v, rc[k], mid, R);
    //no pull needed i think
}

void add_edge(int a, int b, int c){
    if(a == 0 || b==0) return;
        adj[a].pb(mp(b, c));
}


void Q(int qL, int qR, int e, int k, int L, int R){
    if(qR <= L || R <= qL || R <= L || qR <= qL || k == 0) return ;
    if(qL <= L && R <= qR){
        //e.pb(k);
        add_edge(e, k, 1);
        return ;
    }
    int mid = (L + R)/2;
    Q(qL, qR, e, lc[k], L, mid);
    Q(qL, qR, e, rc[k], mid, R);
}

/** relevant to problem **/
#define pii pair<int, int>
vector<pii> points, queries;
pii source;

set<int> bl_x[SEG], bl_y[SEG];
int dist[NN];
bitset<NN> vis;
int ans[MX];

const int drow[] = {0, 0, -1, 1};
const int dcol[] = {-1, 1, 0, 0};


segment make(int x, int y, int d){
    if(d == 0){
        int l = *prev(bl_y[y].lower_bound(x)), r = *bl_y[y].lower_bound(x);
        l++, r--;
        return segment(0, y, l, r);
    }else{
        int l = *prev(bl_x[x].lower_bound(y)), r = *bl_x[x].lower_bound(y);
        l++, r--;
        return segment(1, x, l, r);
    }
}

bool cmp(const segment& a, const segment& b){
    int lhs = a.down();
    int rhs = b.down();
    if(lhs == rhs){
        if(a.dir == b.dir){
            if(a.dir == 1){
                return (a.l == b.l) ? (a.pos < b.pos) : (a.l < b.l);
            }else{
                return (a.pos == b.pos) ? (a.l < b.l) :(a.pos < b.pos);
            }
        }else{
            return a.dir > b.dir;
        }
    }else{
        return lhs < rhs;
    }
}
void make_segments(){
    int zx = xes.gind(n)+1, zy = yes.gind(m)+1;

    for(s = 1; s<=max(zx, zy); s*=2);

    for(const auto& e : points){
        bl_x[e.ff].insert(e.ss);
        bl_y[e.ss].insert(e.ff);
    }
    for(int i = 0; i<=zy; i++){
        bl_y[i].insert(0);
        bl_y[i].insert(zx);
    }

    for(int i = 0; i<=zx; i++){
        bl_x[i].insert(0);
        bl_x[i].insert(zy);
    }

    for(const auto& e : points){
        int x = e.ff, y = e.ss;
        for(int i = 0; i<4; i++){
            if(i >= 2){
                int dy = y + dcol[i], dx = x + drow[i];
                segment a = make(dx, dy, 0);
                if(a.l <= a.r && dy > 0 && dy < zy && dx > 0 && dx < zx){
                    seg[sind++] = a;
                }
            }
            else{
                int dx = x + drow[i], dy = y + dcol[i];
                segment a = make(dx, dy, 1);
                if(a.l <= a.r && dy > 0 && dy < zy && dx > 0 && dx < zx){
                    seg[sind++] = a;
                }
            }
        }
    }
    for(int i = 1; i<max(zx, zy); i++){
        if(sz(bl_y[i]) == 2 && i < zy){
            seg[sind++] = segment(0, i, 1, zx-1);
        }
        //paralell to y axis
        if(sz(bl_x[i]) == 2 && i < zx){
            seg[sind++] = segment(1, i, 1, zy-1);

        }
    }
    //cout << "resutls\n";
    sort(seg+1, seg+sind);
    sind = unique(seg+1, seg+sind) - (seg+1);
    for(int i = 1; i<sind+1; i++) seg[i].ind = i;
    IND = sind+1;
    assert(sind <= K*8 +100 + (3*K + q + 1)*2);
}

void sweep(){
    int root = 0;
    sort(seg+1, seg+1+sind, cmp);
    for(int i = 1; i<sind+1; i++){
        if(seg[i].dir == 1){
            U(seg[i].pos, seg[i].ind, root, 0, s);
        }else{
            Q(seg[i].l, seg[i].r+1, seg[i].ind, root, 0, s);
        }
    }
    sort(seg+1, seg+sind+1);
    root= 0;
    for(int i = 1; i<sind+1; i++){
        if(seg[i].dir == 0){
        U(seg[i].pos, seg[i].ind, root, 0, s);
        }else{
            Q(seg[i].l, seg[i].r+1, seg[i].ind, root, 0, s);
        }
    }
}

void bfs(int src){
    queue<int> zero, one;
    int dis = 0;
    memset(dist, 63, sizeof(dist));
    vis.reset();
    dist[src] = 0;
    zero.push(src);
    while(sz(one) || sz(zero)){
        if(sz(zero) == 0){
            swap(zero, one);
        }
        int u = zero.front(); zero.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        if(u <= sind && sz(adj[u])){
            for(const auto& e : adj[u]){
                int v = e.first;
                if(dist[v] > dist[u] + e.second){
                    dist[v] = dist[u] + e.second;
                    if(e.second) one.push(v);
                    else zero.push(v);
                }
            }
        }else{
            int v = lc[u];
            if(v > 0 && dist[v] > dist[u] && rc[u] != -1){
                dist[v] = dist[u];
                //one.push(v);
                zero.push(v);
            }
            v = rc[u];
            if(v > 0 && dist[v] > dist[u] && rc[u] != -1){
                dist[v] = dist[u];
                zero.push(v);
            }
            if(rc[u] == -1){
                v = lc[u];
                if(v && dist[v] > dist[u]){
                    dist[v] = dist[u];
                    zero.push(v);
                }
            }
        }
    }
}

bool cmp2(const pair<int, int>& a, const pair<int, int>& b){
    return (a.second == b.second) ? (a.first < b.first) : (a.second < b.second);
}

int gsind(segment a){
    auto it = lower_bound(seg+1, seg+1+sind, a);
    return it - seg;
}

void answer(){
    memset(ans, 63, sizeof(ans));
    segment spx = make(source.ff, source.ss, 0);
    int ssx = gsind(spx);
    bfs(ssx);
    for(int i = 0; i<q; i++){
        ans[i] = min(ans[i], dist[gsind(make(queries[i].ff, queries[i].ss, 0))]);
        ans[i] = min(ans[i], dist[gsind(make(queries[i].ff, queries[i].ss, 1))]);
    }
    segment spy = make(source.ff, source.ss, 1);
    int ssy = gsind(spy);
    bfs(ssy);
    for(int i = 0; i<q; i++){
        ans[i] = min(ans[i], dist[gsind(make(queries[i].ff, queries[i].ss, 0))]);
        ans[i] = min(ans[i], dist[gsind(make(queries[i].ff, queries[i].ss, 1))]);
    }
    for(int i = 0; i<q; i++){
        if(ans[i] > 1e9) ans[i] = -1;
    }
}


void solve(){
    cin >> n >> m >> K >> q;
    for(int i = 0; i<K; i++){
        int a, b;
        cin >> a >> b;
        points.pb(mp(a, b));
        xes.add(a); yes.add(b);
        if(a < n) xes.add(a+1);
        if(b < m) yes.add(b+1);
    }
    xes.add(n);
    yes.add(m);
    cin >> source.ff >> source.ss;
    xes.add(source.ff);
    yes.add(source.ss);
    for(int i = 0; i<q; i++){
        int a, b;
        cin >> a >> b;
        xes.add(a); yes.add(b);
        queries.pb(mp(a, b));
    }
    xes.norm();
    yes.norm();
    for(int i = 0; i<K; i++){
        points[i] = mp(xes.gind(points[i].ff), yes.gind(points[i].ss));
    }
    for(int i = 0; i<q; i++){
        queries[i] = mp(xes.gind(queries[i].ff), yes.gind(queries[i].ss));
    }
    source = mp(xes.gind(source.ff), yes.gind(source.ss));
    make_segments();
    sweep();
    for(int i = 0; i<SEG; i++){
        sort(all(adj[i]), cmp2);
    }
    answer();
    for(int i = 0; i<q; i++){
        cout << ans[i] << "\n";
    }
}

int main(){
  cin.tie(0) -> sync_with_stdio(0);

  int T = 1;
  //cin >> T;
  while(T--){
        solve();
  }
  return 0;
}