Problem Description

When planning the new district $M$, it was decided that the streets should form a regular rectangular grid. That is, all streets are of two types: north-south and east-west. Any two parallel streets are $1$ kilometer apart, and each block is exactly a $1$ km $\times 1$ km square. Thus, the whole road system looks like a uniform grid.

All roads allow traffic in both directions.

However, after construction, it turned out that this plan is not always convenient, because when building large factories or parks, a single block is not enough. Therefore, the city hall decided to allocate each large project a rectangular area consisting of several adjacent blocks. Unfortunately, all roads inside such an area will be closed and impassable, while the roads on the boundary of the area are still passable. If two areas touch each other, the boundary roads are still open and will not be closed.

When the mayor received the map of these large project areas, he wanted to know whether it would be difficult to travel from the city hall building to his future home. The city hall is located at the center of the new district, at the intersection of north-south street $0$ and east-west street $0$. The mayor has not decided where to live yet, and he has $k$ candidate locations. Each location is at the intersection of north-south street $x_i$ and east-west street $y_i$ ($x>0$ means east, $x<0$ means west; $y>0$ means north, $y<0$ means south).

The mayor thinks that if a route from the city hall to home requires more than two turns (either left or right), then the route is too complicated. At each intersection, his car can make at most one turn (U-turns are not allowed). The route length does not matter, and the car may arrive at home from any direction. Initially, the car faces north; it may turn left or right immediately, but it cannot make a direct U-turn.

Write a program that, given the closed block information and the mayor’s candidate home locations, determines for each candidate whether there exists a not-complicated route (with at most $2$ turns) from the city hall to that location. If such a route exists, output the shortest one among them; otherwise, report that it does not exist. You do not need to minimize the number of turns.

Input Format

The first line contains two integers $n$ and $k\ (0 \le n \le 100\,000,1 \le k \le 10)$, representing the number of blocks assigned to large projects and the number of candidate home locations.

The next $n$ lines each contain four integers $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)$, describing two opposite corners of a closed rectangular area in terms of street indices.

The last $k$ lines each contain two integers $x_i$ and $y_i\ (|x_i| \le 10^9,|y_i| \le 10^9)$, with $x_i \ne 0$ or $y_i \ne 0$, representing a candidate home location.

The city hall and all candidate locations are not inside any closed area, but closed areas may overlap.

Output Format

For each candidate location, output whether a not-complicated route exists, in the input order.

If it does not exist, output one line NO.

If it exists, output YES on the first line; on the second line output the number of turns $t\ (0 \le t \le 2)$; then output $t$ lines, each containing three integers $x, y, d$, describing the intersection coordinates where a turn occurs and the turning direction ($d = -1$ means a left turn, $d = 1$ means a right turn). The coordinates of turning intersections do not exceed $10^9$. If there are multiple shortest not-complicated routes, output any one.

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

Hint

The following is an illustration of the second sample.

Scoring

For the $30$-point testdata, coordinates are less than $100$ and $n \le 50$.

For the $60$-point testdata, $n \le 50$.

Translation source: GPT 4.1 mini.

Translated by ChatGPT 5