在字节国（Byteotia）的首都拜陶（Bytau），街道布局非常规整。每条街道要么从北向南延伸，要么从东向西延伸。因此，每一条南北向街道与每一条东西向街道恰好在一个点相交。此外，沿每条街道，相邻交叉路口之间的距离恰好为 $1$ 公里。

拜陶不仅是首都，也是字节国最古老的城市之一。城内共有 $z$ 座历史建筑，每一座都位于某个交叉路口。市议会非常重视对这些建筑的保护，目前正关注火灾风险。因此，他们决定在城内建立两个主要的消防站。每座古迹将由距离最近的消防站负责保护；如果两个消防站距离相等，则由两者共同保护。

拜陶的住房非常密集，因此欧几里得距离并不是首选的度量方式。古迹与消防站之间的距离应定义为它们之间沿街道的最短路径长度。

市议会已经准备了若干个消防站选址方案。你需要针对每一个方案，分别计算出由以下三类情况保护的古迹数量：仅由第一个消防站保护、仅由第二个消防站保护，以及由两个消防站共同保护。

输入格式

输入的第一行包含四个整数 $n, m, z$ 和 $p$（$1 \le n, m \le 1\,000\,000\,000$，$1 \le z, p \le 100\,000$），用空格分隔，分别表示：南北向街道的数量、东西向街道的数量、拜陶内历史建筑的数量，以及市议会提出的方案数量。

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

接下来的 $z$ 行，每行包含两个整数 $x_i$ 和 $y_i$（$1 \le x_i \le n, 1 \le y_i \le m$），用空格分隔，表示第 $i$ 座古迹的坐标。没有两座不同的古迹位于同一个交叉路口。

接下来的 $p$ 行，每行包含一个市议会的方案，由四个整数 $x_{j,1}, y_{j,1}, x_{j,2}, y_{j,2}$ 组成，用空格分隔，$1 \le x_{j,1}, x_{j,2} \le n$，$1 \le y_{j,1}, y_{j,2} \le m$，且 $(x_{j,1}, y_{j,1}) \neq (x_{j,2}, y_{j,2})$。坐标 $(x_{j,1}, y_{j,1})$ 和 $(x_{j,2}, y_{j,2})$ 分别描述了第 $j$ 个方案中两个消防站的选址位置（$1 \le j \le p$）。

输出格式

程序应在标准输出中打印恰好 $p$ 行。第 $j$ 行应包含三个整数，分别表示：在第 $j$ 个方案中，仅由第一个消防站保护的古迹数量、仅由第二个消防站保护的古迹数量，以及由两个消防站共同保护的古迹数量。这些数字之间用空格分隔。

样例

样例输入 1

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

样例输出 1

1 3 2