Solar Lamps

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 2e5 + 5;
int n, id1[N], id0[N], pos[N];
struct Point
{
    ll x, y;
    bool operator<(const Point &a) const
    {
        return x < a.x || (x == a.x && y < a.y);
    }
} s[2], a[N], b[N];
int need[N], ans[N];

struct BIT
{
    int a[N];
    void Update(int p)
    {
        for (; p <= n; p += p & -p)
            ++a[p];
    }
    int Ans(int p)
    {
        int ans = 0;
        for (; p > 0; p -= p & -p)
            ans += a[p];
        return ans;
    }
    int Get(int l, int r)
    {
        return Ans(r) - Ans(l - 1);
    }
    void clear()
    {
        memset(a, 0, sizeof a);
    }
} x;

void Read()
{
    cin >> n;
    cin >> s[0].x >> s[0].y >> s[1].x >> s[1].y;
    if (s[0].x * s[1].y - s[0].y * s[1].x < 0)
        swap(s[0], s[1]);
    for (int i = 1; i <= n; ++i)
    {
        cin >> a[i].x >> a[i].y;
        id0[i] = id1[i] = pos[i] = i;
    }
    for (int i = 1; i <= n; ++i)
    {
        cin >> need[i];
        ans[i] = i;
    }
}

ll dis(int t, int id)
{
    return s[t].y * a[id].x - s[t].x * a[id].y;
}

void DoSort()
{
    if (s[1].y < 0 || (s[1].y == 0 && s[1].x < 0))
    {
        sort(id1 + 1, id1 + n + 1, [&](const int &i, const int &j) {
            return dis(1, i) > dis(1, j);
        });
    }
    else
    {
        sort(id1 + 1, id1 + n + 1, [&](const int &i, const int &j) {
            return dis(1, i) < dis(1, j);
        });
    }
    if (s[0].y < 0 || (s[0].y == 0 && s[0].x < 0))
    {
        sort(id0 + 1, id0 + n + 1, [&](const int &i, const int &j) {
            return dis(0, i) < dis(0, j);
        });
    }
    else
    {
        sort(id0 + 1, id0 + n + 1, [&](const int &i, const int &j) {
            return dis(0, i) > dis(0, j);
        });
    }
}

void Recursive(int l, int r, vector<int> &v)
{
    x.clear();
    if (l == r)
    {
        if (!v.empty())
            for (auto i : v)
                ans[i] = min(ans[i], l);
        return;
    }
    if (v.empty() || l > r)
        return;
    vector<int> left, right;
    sort(v.begin(), v.end(), [&](const int &x, const int &y) {
        return b[x] < b[y];
    });
    int mid = (l + r) / 2, piv = 0;
    for (int i = 1; i <= n; ++i)
    {
        if (piv < v.size() && v[piv] == pos[i])
        {
            if (pos[i] <= mid || x.Get(1, b[pos[i]].y) >= need[pos[i]])
            {
                left.push_back(pos[i]);
                x.Update(b[pos[i]].y);
            }
            else
                right.push_back(pos[i]);
            ++piv;
        }
        else if (pos[i] <= mid)
            x.Update(b[pos[i]].y);
        if (piv >= v.size())
            break;
    }
    v.clear();
    v.shrink_to_fit();
    Recursive(l, mid, left);
    Recursive(mid + 1, r, right);
}

void Solve()
{
    DoSort();
    vector<int> v;
    for (int i = 1; i <= n; ++i)
        v.push_back(i);
    int cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        int j = i;
        ++cnt;
        while (j <= n && dis(0, id0[i]) == dis(0, id0[j]))
        {
            b[id0[j]].x = cnt;
            ++j;
        }
        i = j - 1;
    }
    cnt = 0;
    for (int i = 1; i <= n; ++i)
    {
        int j = i;
        ++cnt;
        while (j <= n && dis(1, id1[i]) == dis(1, id1[j]))
        {
            b[id1[j]].y = cnt;
            ++j;
        }
        i = j - 1;
    }
    sort(pos + 1, pos + n + 1, [&](const int &x, const int &y) {
        return b[x] < b[y];
    });
    Recursive(1, n, v);
    for (int i = 1; i <= n; ++i)
        cout << ans[i] << " ";
}

int32_t main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    Read();
    Solve();
}