TCS CodeVita Previous Year Question | Islands

TCS CodeVita Season 9 Registration is going on Register soon — Click here

Index of all TCS CodeVita Previous year questions.

TCS CodeVita Previous Year Question must be completed before sitting in the actual round of coding.

Want to know more about TCS Codevita?We have covered a great part of the introduction to TCS CodeVita here you must read this: Click here to open.

Islands

Problem Description

In the Indian Ocean, there are several small islands. A war ship is stationed in the ocean and wants to find how many of these islands are within its striking power. For simplicity, the islands are all assumed to have square shapes and again, the curvature of the earth can be ignored. The coordinates of two opposite corners of the islands are given and the position of the ship is also given. You need to find the islands in the increasing sequence of their distances from the ship. The distance is the shortest distance – the distance of the nearest point on the island boundary from the ship. Use Manhattan Distance, i.e. distance between 2 points (x1,y1) and (x2,y2) is |x1-x2| + |y1-y2|.

Constraints

1 <= N <= 100000.

-10^9 <= x1i, y1i, x2i,y2i <= 10^9.

Input Format

First line contains single integer N denoting the number of islands.

Next N lines contain 4 integers separated by space denoting the coordinates of the opposite corners of the islands (x1i, y1i) & (x2i,y2i). (1 <= i <= N)

Islands are numbered 1, 2, …, N.

The final line contains 2 integer separated by space denoting the coordinates of the warship.

Output

N integers separated by space each integer denoting the index of island sorted by distance from warship in non-decreasing order.

If 2 islands are at the same distance from warship, rank them according to their index.

Test Case

Explanation

Example 1

Input

2

0 0 1 1

0 3 1 4

0 0

Output

1 2

Explanation

Example 2

Input

3

1 1 0 0

1 2 2 3

3 0 4 1

0 4

Output

2 1 3

Explanation

Index of all TCS CodeVita Previous year questions.

Spread the word and ask your every friend, junior, senior, batchmate, near and dear ones to Register to CodeVita! Click here to register.

Happy Coding!

We will be posting all the questions of CodeVita and also the Mock Tests.

We might not be able to publish all the questions. Keep sending your CodeVita’s question at circuitandcode@gmail.com