题目描述

在规划新城区 $M$ 时，决定让街道形成一个规整的矩形网格，也就是说，所有街道都分为两种：南北向和东西向。每条平行街道间隔一公里，每个街区正好是 $1$ 公里 $\times1$ 公里的方块。这样，整个道路系统就像一个均匀的格子。

每条路都允许双向通行。

但建成后发现，这样的规划并不总是方便。因为建大型工厂或公园时，单个街区不够用。于是市政府决定给每个大型项目分配一个由若干相邻街区组成的矩形区域。遗憾的是，这些区域内的道路将全部封闭，禁止通行，但区域边界的道路仍可通行。两个区域相邻接触时，边界道路仍然开放，不会封闭。

当市长拿到这些大型项目区域分布图时，他想知道从市政府大楼到他未来家的路线难不难走。市政府位于新区中心，坐标是南北向的 $0$ 号街和东西向的 $0$ 号街的交叉口。市长还没决定最终住哪儿，他有 $k$ 个备选位置。每个位置在第 $x_i$ 条南北街和第 $y_i$ 条东西街的交叉口（$x>0$ 表示东边，$x<0$ 表示西边；$y>0$ 表示北边，$y<0$ 表示南边）。

市长觉得，如果从市政府到家的路上转弯超过两次（无论左转还是右转），那条路就太复杂了。他的车在每个路口最多只能转一次（不能掉头）。路线长度无所谓，车可以从任何方向驶入家门。车起始时面朝北，可以立刻左转或右转，但不能直接掉头。

请写程序，根据封闭的街区信息和市长家的备选位置，找出每个备选位置是否存在不复杂的路线（转弯次数不超过 $2$ 次）从市政府到家。如果有，找出其中最短的路线；如果没有，输出不存在。无需最小化转弯次数。

输入格式

第一行包含两个整数 $n$ 和 $k\ (0 \le n \le 100\,000,1 \le k \le 10)$，分别表示被划为大型项目的街区数量和市长家备选位置数量。

接下来 $n$ 行，每行四个整数 $u_1,v_1,u_2,v_2\ (-10^9 \le u_1 < u_2 \le 10^9,-10^9 \le v_1 < v_2 \le 10^9)$，表示被封闭的街区矩形两个对角的街道编号。

最后 $k$ 行，每行两个整数 $x_i$ 和 $y_i\ (|x_i| \le 10^9,|y_i| \le 10^9)$，且 $x_i \ne 0$ 或 $y_i \ne 0$，表示市长家的备选位置。

市政府和所有备选位置都不在封闭街区内，但封闭街区之间可能重叠。

输出格式

对于每个备选位置，按输入顺序输出是否存在不复杂路线。

若不存在，输出一行 NO。

若存在，第一行输出 YES；第二行输出转弯次数 $t\ (0 \le t \le 2)$；接下来 $t$ 行，每行三个整数 $x, y, d$，表示转弯的路口坐标和转弯方向（$d = -1$ 表示左转，$d = 1$ 表示右转）。转弯路口坐标不超过 $10^9$。若有多条最短不复杂路线，输出任意一条。

2 1
0 2 2 4
1 0 4 2
3 3

YES
2
0 2 1
3 2 -1

0 2
0 -1
0 1

NO
YES
0

提示

下面是第二个样例的示意图。

评分

对于 $30$ 分的数据，坐标小于 $100$ 且 $n\le 50$。

对于 $60$ 分的数据，$n\le 50$。

翻译来源：GPT 4.1 mini。