PROJECTILE - Projectile Motion

Consider a two-dimensional plane. There are N poles standing parallel to y-axis. The ith pole has height Hi and is between y = 0 and y = Hi and at position Xi. The gravity acts along negative y-axis and its value is 10Q projectiles are launched from origin with the jth projectile launched at an angle Aj and with speed Sj. For each projectile, print the index of pole that the projectile hits.

The poles in input are arranged in increasing order of Xi. If a projectile doesn't hit any pole, print -1. Indices of pole starts from 1. The angle is given in degrees and all other units follow SI.

Constraints

1 <= N <= 10^5

1 <= Q <= 10^5

1 <= Xi <= 10^9

1 <= Sj <= 10^9

1 <= Aj <= 89

1 <= Hi <= 100

Input

All values in input are integers.

The first line contains N.

The next N lines containes two space separated integers Xi and Hi. The Xi's are in increasing order and unique.

The next line contains Q.

The next Q line contains two space separated integers Aj and Sj.

Output

Print Q lines each containing the pole index hit by the jth projectile. If a projectile doesn't hit any pole, then print -1.

Example

Input:
4
1 1
2 3
3 7
6 3
8
10 34
45 20
50 12
60 14
70 65
60 34000000
85 12
81 14

Output:
1
1
2
3
-1
3
-1
4

Added by:sonudoo
Date:2019-11-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All
Resource:ACM, Birla Institute of Technology, Mesra

hide comments
2020-01-27 17:05:46 Ahmed Bahnasy
@sagittariusgrl: Aha, I misunderstood the problem statement, Thanks alot for elaboration.
2020-01-27 14:23:08
@Ahmed Bahnasy: They start to count at 1 ("Indices of pole starts from 1.") and they are not referring to the actual x position of the pole but to the k-th pole of all given poles.
2020-01-26 22:05:16 Ahmed Bahnasy
I believe in the given example, in the output, the last index (4) which represents the pole the projticle will hit is not correct, there is no pole at index 4 in the input? right?

Last edit: 2020-01-26 22:06:13
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.