题目描述

题目译自 XVI OI Olimpiada Informatyczna – I etap Straż pożarna

拜托城首都拜塔维的街道布局井然有序，所有街道要么南北向，要么东西向。每条南北向街道与每条东西向街道恰好相交于一点，且沿每条街道，相邻交叉口间距均为 $1$ 公里。

城中有 $z$ 座历史建筑，每座位于一个交叉口。市议会高度重视这些独特文物，决定在城中兴建两座大型消防站。每座历史建筑由距离最近的消防站保护；若与两站距离相等，则由两者共同保护。

拜塔维建筑密集，因此不能按直线距离计算消防站到历史建筑的距离，而应取沿街道的最短路径长度。

市议会提出了若干消防站选址方案。你需为每个方案计算：仅由第一消防站保护的历史建筑数，仅由第二消防站保护的历史建筑数，以及由两站共同保护的建筑数。

输入格式

第一行包含四个整数 $n, m, z, p$ $(1 \leq n, m \leq 1000000000, 1 \leq z, p \leq 100000)$，分别表示南北向街道数、东西向街道数、历史建筑数和市议会提出的方案数。

南北向街道从西向东编号为 $1$ 至 $n$，东西向街道从北向南编号为 $1$ 至 $m$。第 $x$ 条南北向街道与第 $y$ 条东西向街道的交叉口坐标为 $(x, y)$。

接下来的 $z$ 行，每行包含两个整数 $x_i, y_i$ $(1 \leq x_i \leq n, 1 \leq y_i \leq m)$，表示第 $i$ 座历史建筑的坐标。任意两座历史建筑不在同一交叉口。

接下来的 $p$ 行，每行包含四个整数 $x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$ $(1 \leq x_{j,1}, x_{j,2} \leq n, 1 \leq y_{j,1}, y_{j,2} \leq m, (x_{j,1}, y_{j,1}) \neq (x_{j,2}, y_{j,2}))$，表示第 $j$ 个方案中两消防站的坐标 $(x_{j,1}, y_{j,1})$ 和 $(x_{j,2}, y_{j,2})$。

输出格式

输出 $p$ 行，第 $j$ 行包含三个整数，分别表示第 $j$ 个方案中仅由第一消防站保护、仅由第二消防站保护、以及由两站共同保护的历史建筑数，数字间用单空格分隔。

6 5 6 1
1 2
6 5
5 1
3 3
3 4
4 1
2 3 4 3

1 3 2

图中虚线表示街道，圆圈表示历史建筑位置，叉号表示拟建消防站位置。白色圆圈表示仅由第一消防站保护的历史建筑，黑色圆圈表示仅由第二消防站保护，灰色圆圈表示由两站共同保护。