/*
JOI17_dragon2 - Dragon 2
assume that |i|<|j| in the queries. notice that if you spend |i| per query,
then you get a O(n sqrt n) complexity
- if |i| less than sqrt n, then it's ok
- otherwise we have that both |i| (and |j|) are greater than sqrt n. there are
at most sqrt(n) j that are possible due to |j| so this amortizes to O(n sqrt n)
so for the geo part, we can write that the line crosses the village as a form
of two inequalities (one for p and one for q).
you can use a 2d segtree (pst + binary search) to deal with this.
complexity is O(n sqrt n log n).
*/
#include <bits/stdc++.h>
using namespace std;
template<class T>
pair<T, T> _minmax(const T& a, const T& b) {
if (a < b)
return make_pair(a, b);
else
return make_pair(b, a);
}
typedef __int128 i128;
const int N = 30000, Q = 100000;
const i128 PI = (i128) 1e36 * acosl(-1);
i128 acos2_128(int x, int y) {
return (i128) 1e36 * atan2l(y, x);
}
i128 opposite(const i128& x) {
return x < 0 ? x + PI : x - PI;
}
struct point {
int x, y;
i128 ang_a, ang_b;
point() {}
point(int x, int y) : x(x), y(y) {}
i128 angle(const point& p) const {
return acos2_128(p.x - x, p.y - y);
}
} A, B;
int ans[Q];
namespace pst {
const int M = N * 15 * 2;
int sum[M], ll[M], rr[M], _;
void clear() {
_ = 0;
}
int node(int k = 0) {
++_;
sum[_] = sum[k];
ll[_] = ll[k], rr[_] = rr[k];
return _;
}
int build(int l, int r) {
int v = node(), m;
if (l < r) {
m = (l + r) / 2;
ll[v] = build(l, m);
rr[v] = build(m + 1, r);
}
return v;
}
int update(int v, int l, int r, int i, int x) {
int v_ = node(v), m;
sum[v_] += x;
if (l < r) {
m = (l + r) / 2;
if (i <= m)
ll[v_] = update(ll[v_], l, m, i, x);
else
rr[v_] = update(rr[v_], m + 1, r, i, x);
}
return v_;
}
int query(int v, int l, int r, int ql, int qr) {
int m;
if (qr < l || ql > r)
return 0;
if (ql <= l && qr >= r)
return sum[v];
m = (l + r) / 2;
return query(ll[v], l, m, ql, qr) + query(rr[v], m + 1, r, ql, qr);
}
}
struct group {
vector<int> vv;
vector<i128> xx, yy;
vector<point> pp;
int n;
int size() {
return n;
}
void add(const point& p) {
pp.push_back(p), n++;
}
void add_query(const i128& lx, const i128& rx, const i128& ly, const i128& ry, int h) {
short l = lower_bound(yy.begin(), yy.end(), ly) - yy.begin();
short r = upper_bound(yy.begin(), yy.end(), ry) - yy.begin() - 1;
short l_ = lower_bound(xx.begin(), xx.end(), lx - 1) - xx.begin();
short r_ = upper_bound(xx.begin(), xx.end(), rx) - xx.begin() - 1;
ans[h] += pst::query(vv[r_ + 1], 0, yy.size() - 1, l, r) - pst::query(vv[l_], 0, yy.size() - 1, l, r);
}
void add1(const point& q, int h) {
auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
bool side_a = l_a <= B.ang_a && B.ang_a <= r_a;
auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
bool side_b = l_b <= A.ang_b && A.ang_b <= r_b;
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
}
void add2(const point& q, int h) {
auto [l_a, r_a] = _minmax(q.ang_a, opposite(q.ang_a));
bool side_a = !(l_a <= B.ang_a && B.ang_a <= r_a);
auto [l_b, r_b] = _minmax(q.ang_b, opposite(q.ang_b));
bool side_b = !(l_b <= A.ang_b && A.ang_b <= r_b);
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
tie(l_a, r_a) = _minmax(opposite(q.ang_a), B.ang_a);
side_a = !(l_a <= q.ang_a && q.ang_a <= r_a);
tie(l_b, r_b) = _minmax(opposite(q.ang_b), A.ang_b);
side_b = !(l_b <= q.ang_b && q.ang_b <= r_b);
if (side_a == 1) {
if (side_b == 1)
add_query(l_a, r_a, l_b, r_b, h);
else {
add_query(l_a, r_a, -PI, l_b - 1, h);
add_query(l_a, r_a, r_b + 1, PI, h);
}
} else {
if (side_b == 1) {
add_query(-PI, l_a - 1, l_b, r_b, h);
add_query(r_a + 1, PI, l_b, r_b, h);
} else {
add_query(-PI, l_a - 1, -PI, l_b - 1, h);
add_query(r_a + 1, PI, -PI, l_b - 1, h);
add_query(-PI, l_a - 1, r_b + 1, PI, h);
add_query(r_a + 1, PI, r_b + 1, PI, h);
}
}
}
void build() {
for (const point& p : pp) {
xx.push_back(p.ang_a);
yy.push_back(p.ang_b);
}
sort(xx.begin(), xx.end());
sort(yy.begin(), yy.end());
sort(pp.begin(), pp.end(), [&](const point& p, const point& q) {
return p.ang_a < q.ang_a;
});
pst::clear();
vv.push_back(pst::build(0, yy.size() - 1));
for (const point& p : pp) {
int i = lower_bound(yy.begin(), yy.end(), p.ang_b) - yy.begin();
vv.push_back(pst::update(vv.back(), 0, yy.size() - 1, i, +1));
}
}
void clear() {
xx.clear();
yy.clear();
}
} gr[N];
int main() {
#ifndef LOCAL
ios::sync_with_stdio(false);
cin.tie(NULL);
#endif
static vector<tuple<int, int, bool>> todo[N];
vector<pair<point, int>> pp;
int n, m, q;
cin >> n >> m;
pp.resize(n);
for (auto &[p, c] : pp)
cin >> p.x >> p.y >> c, c--;
cin >> A.x >> A.y >> B.x >> B.y;
A.ang_a = A.angle(A);
A.ang_b = B.angle(A);
B.ang_a = A.angle(B);
B.ang_b = B.angle(B);
for (auto &[p, c] : pp) {
p.ang_a = A.angle(p);
p.ang_b = B.angle(p);
gr[c].add(p);
}
pp.clear();
cin >> q;
for (int h = 0; h < q; h++) {
int c1, c2;
cin >> c1 >> c2, c1--, c2--;
if (gr[c1].size() < gr[c2].size())
todo[c2].push_back({c1, h, 0});
else
todo[c1].push_back({c2, h, 1});
}
for (int c = 0; c < m; c++) {
gr[c].build();
for (auto [c_, h, t] : todo[c])
for (const point& p : gr[c_].pp)
if (t == 0)
gr[c].add1(p, h);
else
gr[c].add2(p, h);
gr[c].clear();
todo[c].clear();
}
for (int h = 0; h < q; h++)
cout << ans[h] << '\n';
return 0;
}
