All Tracks Math Number Theory Basic Number Theory-2 Problem

Monk and Students
Tag(s):

Easy-Medium, Number Theory, approved

Problem
Editorial
Analytics

Monk went for a picnic on $$X-Y$$ coordinate plane with his students. He found N line segments indexed from $$1$$ to $$N$$, and each one is represented with its $$2$$ endpoints. He knows the fact, that there is a chair on each lattice point of each line segment including the endpoints.

Note: Lattice points on are those points which have both $$x$$ and $$y$$ co-ordinate as an integer.

Now the school's principal Mishki has $$Q$$ batches of students, each having different number of students. She wants to know the best line segment for each batch. All the batches are independent of each other.

Best line segment for one batch is the one having enough chairs, so that each student of that batch gets one chair, and number of chair left vacant after that in the line segment, should be as minimum as possible.
If their are multiple such segments, then the best one is the one which satisfies above conditions and have minimum index.

As Monk is weak in geometry, please help him.

Input:
The first line will consists of one integer $$N$$, denotes the number of line segments.
In next N lines, each line contains $$4$$ space separated integers $$x_1, y_1, x_2, y_2$$ representing the 2 endpoints $$(x_1,y_1) , (x_2, y_2)$$ of a line segment, where $$i^{th}$$ line represents the endpoints of line segment with index $$i$$.
Next line contains one integer $$Q$$, which denotes the number of batches of students.
In next Q lines, $$i^{th}$$ line contains one integer $$X$$ , representing the number of students in $$i^{th}$$ batch.

Output:
For each batch, print the index of the best line segment for that batch. If no best line segment exists, then print $$-1$$.

Constraints:
$$1 \le N \le 10^5$$
$$-10^{10} \le x_1,y_1,x_2,y_2 \le 10^{10}$$
$$1 \le Q \le 10^5$$
$$1 \le X \le 10^9$$

SAMPLE INPUT
3
-26 37 -80 53
-15420 -74219 -16168 -79489
12503 23456 14971 13990
1
2
SAMPLE OUTPUT
1
Explanation

Here there are 2 line segments.
First line segment (with index=1) has endpoints: (-26,37) and (-80,53) and have 3 lattice points including the endpoints.
Second line segment (with index=2) has endpoints: (15420,-74219) and (-16168,-79489) and have 35 lattice points including the endpoints.
Third line segment (with index=3) has endpoints: (12503, 23456) and (14971, 13990) and have 3 lattice points including the endpoints.
Q = 1.
So for batch of students having 2 students in it, the answer will be from first line segment and third line segment as both have same lattice points. The line segment with minimum index is first one. So the answer is 1.

Time Limit: 1.0 sec(s) for each input file.
Memory Limit: 256 MB
Source Limit: 1024 KB
Marking Scheme: Marks are awarded when all the testcases pass.
Allowed Languages: C, C++, Clojure, C#, D, Erlang, F#, Go, Groovy, Haskell, Java, Java 8, JavaScript(Rhino), JavaScript(Node.js), Lisp, Lisp (SBCL), Lua, Objective-C, OCaml, Octave, Pascal, Perl, PHP, Python, Python 3, R(RScript), Racket, Ruby, Rust, Scala, Scala 2.11.8, Swift, Visual Basic

CODE EDITOR

Initializing Code Editor...
Your Rating:

Contributor

This Problem was Asked in

HackerEarth

Challenge Name

CodeMonk (Number Theory Part I)

OTHER PROBLEMS OF THIS CHALLENGE
Notifications
View All Notifications