#include <iostream>
#include <vector>
// #include <map> // map is not used in this version
// Define Point structure using long long for coordinates to handle large values
struct Point {
long long x, y;
};
// Define Dragon structure storing its position and tribe ID
struct Dragon {
Point p;
int tribe;
};
// Function to calculate the orientation of three points (P, Q, R)
// It computes the cross product of vectors PQ and PR.
// Returns a positive value if R is to the left of the directed line PQ.
// Returns a negative value if R is to the right of the directed line PQ.
// Returns zero if P, Q, R are collinear.
// Uses long long arithmetic throughout to avoid overflow issues with large coordinates.
long long orient(Point P, Point Q, Point R) {
// Calculate coordinate differences using long long
long long Qx_Px = Q.x - P.x;
long long Ry_Py = R.y - P.y;
long long Qy_Py = Q.y - P.y;
long long Rx_Px = R.x - P.x;
// Calculate the cross product (determinant).
// The coordinates can be up to 10^9, so differences can be up to 2*10^9.
// The product of two differences can be up to (2*10^9)^2 = 4*10^18.
// This fits within a 64-bit signed long long which has a maximum value of approx 9*10^18.
long long val = Qx_Px * Ry_Py - Qy_Py * Rx_Px;
return val;
}
// Function to check if the ray starting from Ai, passing through Ak, intersects the line segment P1P2.
bool check_intersection(Point Ai, Point Ak, Point P1, Point P2) {
// Calculate necessary orientations. O_ik_1 checks P1 relative to line AiAk. O_ik_2 checks P2 relative to line AiAk.
long long O_ik_1 = orient(Ai, Ak, P1);
long long O_ik_2 = orient(Ai, Ak, P2);
// Condition 1: The line segment P1P2 must cross the line AiAk.
// This happens if P1 and P2 lie on strictly opposite sides of the line AiAk.
// Since the problem states no three points are collinear, orientations O_ik_1 and O_ik_2 will be non-zero.
// Check if their signs are different.
bool cond1;
if ((O_ik_1 > 0 && O_ik_2 < 0) || (O_ik_1 < 0 && O_ik_2 > 0)) {
cond1 = true;
} else {
// If signs are the same, P1 and P2 are on the same side, so segment P1P2 does not cross line AiAk.
cond1 = false;
}
// If Condition 1 is false, the ray cannot intersect the segment.
if (!cond1) {
return false;
}
// Condition 2: The intersection point must lie on the ray starting from Ai and passing through Ak.
// This involves checking the positions of Ai and Ak relative to the line containing the segment P1P2.
// Let O_12_i be orientation of Ai relative to line P1P2.
// Let O_12_k be orientation of Ak relative to line P1P2.
long long O_12_i = orient(P1, P2, Ai);
long long O_12_k = orient(P1, P2, Ak);
// The condition for the intersection point being on the ray Ai -> Ak is mathematically equivalent to:
// O_12_i * (O_12_i - O_12_k) >= 0.
// Since no three points are collinear, Ai and Ak cannot be on the line P1P2, so O_12_i != 0.
// Also, the lines AiAk and P1P2 are not parallel, so O_12_i - O_12_k != 0.
// Therefore, the condition simplifies to O_12_i * (O_12_i - O_12_k) > 0.
bool cond2;
// Calculate the difference O_12_i - O_12_k. This is safe within long long range.
long long diff = O_12_i - O_12_k;
// Check if O_12_i and the difference 'diff' have the same sign.
if ((O_12_i > 0 && diff > 0) || (O_12_i < 0 && diff < 0)) {
cond2 = true;
} else {
cond2 = false;
}
// The ray intersects the segment if and only if both conditions are met.
return cond1 && cond2;
}
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of dragons
int M; // Number of tribes
std::cin >> N >> M;
std::vector<Dragon> dragons(N);
// Store dragon indices grouped by tribe ID for efficient access later.
// dragons_by_tribe[t] will contain a list of indices i such that dragons[i].tribe == t.
std::vector<std::vector<int>> dragons_by_tribe(M + 1);
for (int i = 0; i < N; ++i) {
// Read dragon's position (x, y) and tribe ID
std::cin >> dragons[i].p.x >> dragons[i].p.y >> dragons[i].tribe;
// Add the index 'i' to the list for its tribe
dragons_by_tribe[dragons[i].tribe].push_back(i);
}
Point P1, P2; // Coordinates of the two villages defining the road segment P1P2
std::cin >> P1.x >> P1.y >> P2.x >> P2.y;
int Q; // Number of conflict queries
std::cin >> Q;
// Process each query one by one
for (int j = 0; j < Q; ++j) {
int F, G; // Tribe F becomes hostile to tribe G
std::cin >> F >> G;
// Initialize count of intersecting fireballs for this query
long long count = 0; // Use long long as the count could potentially exceed 32-bit integer max (up to N^2)
// Retrieve the lists of dragon indices for tribes F and G
const auto& tribe_F_indices = dragons_by_tribe[F];
const auto& tribe_G_indices = dragons_by_tribe[G];
// Proceed only if both tribes involved in the conflict actually have dragons
if (!tribe_F_indices.empty() && !tribe_G_indices.empty()) {
// Iterate through every dragon 'i' in tribe F (the attacking tribe)
for (int idx_i : tribe_F_indices) {
// Iterate through every dragon 'k' in tribe G (the target tribe)
for (int idx_k : tribe_G_indices) {
// Since F != G is guaranteed for any query, dragons idx_i and idx_k belong to different tribes.
// Thus, they must be distinct dragons (idx_i != idx_k implicitly).
// Check if the fireball ray launched from dragon i towards dragon k intersects the road segment P1P2
if (check_intersection(dragons[idx_i].p, dragons[idx_k].p, P1, P2)) {
// If it intersects, increment the counter
count++;
}
}
}
}
// Output the total count of intersecting fireballs for the current query
std::cout << count << "\n";
}
return 0;
}
