Navigation

Unmatched technology in location-based services

Hyundai AutoEver's navigation software delivers safe and convenient travel. It is used in more than 70 countries and leads the global infotainment market.

Its navigation software offers a wide range of content and services, giving customers a richer mobility experience and new value.

Built on GIS and LBS technology, precise map data, and route search algorithms, its advanced navigation solutions help automakers expand overseas and lead the global market.

Customer first

Vehicle navigation

Hyundai AutoEver helps customers around the world drive to their destinations quickly and safely. Putting customers first is its core value.

Based on center communication, the system tracks the user's current position in real time and provides road traffic conditions, closed sections, and other information that affects traffic flow.

ICPC Sinchon was asked by Hyundai AutoEver to test vehicle navigation. The staff compared the performance of Hyundai AutoEver's OEM navigation with the other $N-1$ navigation systems from other companies. They confirmed that the OEM navigation finds a more efficient optimal route to the destination.

The team plans to send this experimental data to Hyundai AutoEver after SUAPC 2022 Summer ends. The data contains the following information.

• The start point $(s\_x, s\_y)$ and the end point $(e\_x, e\_y)$
• For each navigation, the intermediate points that must be visited in order to go from $(s\_x, s\_y)$ to $(e\_x, e\_y)$

The distance between two points is the Manhattan distance. That is, the distance between $(a,b)$ and $(c,d)$ is $|a-c|+|b-d|$. The optimal route distances computed by the navigation systems are all different.

However, on the day of SUAPC 2022 Summer, a sudden computer failure mixed up the experimental values of the navigation systems. Before the contest ends, you are given the data for each navigation. Find which data belongs to the OEM navigation.

The first line contains a positive integer $N$, the number of navigation systems used in the experiment. ($2 \le N \le 1\,000$)

The second line contains four integers $s\_x$, $s\_y$, $e\_x$, $e\_y$, separated by spaces, which are the coordinates of the start point and the end point. ($-10^9 \le s\_x, s\_y, e\_x, e\_y \le 10^9$)

The following lines give the data for navigation 1 through navigation $N$, in order. The input for each navigation is as follows.

• The first line contains $M\_i$, the number of intermediate points that must be visited in order. ($1 \le M\_i \le 100$)
• The next $M\_i$ lines each contain two integers separated by a space, the $x$ and $y$ coordinates of the $j$-th intermediate point $(x\_{i,j}, y\_{i,j})$. ($-10^9 \le x\_{i,j}, y\_{i,j} \le 10^9$)

Print the number of the data set that belongs to the OEM navigation.