Machine Learning

Home Matchmaker: Five Fair Neighbors

In the housing feed, the total price and total area mislead KNN. Shoppers really compare price per m². To make comparisons feel fair, your recommender should find the five homes whose value-per-space most closely matches a new home.

You are asked to read an initial list of homes, then for each new home, output the indices of the five closest homes from the initial list, ordered from closest to farthest. Closeness is judged by how similar their price per m² values are; if two homes are equally close, list the smaller index first. Homes are indexed starting from 1 in the order they appear.

The first line of the input contains a single integer n (n > 5) representing how many homes are in the initial list. Each of the next n lines contains two floating-point numbers: price and area.

The next line contains a single integer q representing how many new homes to compare. Each of the next q lines contains two floating-point numbers: the new homes’ price and area.

The program should print q lines. Each line should contain five integers - the indices of the five closest homes from the initial list.

Input

Output

6
100000 40
120000 50
150000 60
200000 80
130000 52
156000 60
2
125000 50
180000 60

1 3 4 5 2
6 1 3 4 5

7
90000 30
180000 90
150000 50
210000 70
175000 70
240000 80
195000 65
3
150000 60
240000 100
210000 70

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

8
135000 45
128000 64
99000 66
160000 80
180000 100
144000 48
210000 70
150000 75
1
144000 60

2 4 8 1 5

Constraints

Time limit: 2 seconds

Memory limit: 512 MB

Output limit: 1 MB

To check your solution you need to sign in
Sign in to continue