the-clock-game

There are n clocks in the Pradnya Planet which beep after different time periods.
The clocks are represented as C1, C2, ... Cn and their respective time periods 
by T1, T2, T3, ... Tn.
Each clock beeps with the intensity of 1. If k clocks beep at the same time, it 
is counted as one beep of intensity k.
There are p aliens in the pradnya world who are sleeping at time t=0.
These p aliens are denoted by A1, A2, ... Ap.
All the aliens are insomniac but all in a different way. 
An alien wakes up at time t, either if the number of beeps completed before or at the time t exceeds a particular value(Beep Value), or if the intensity of any beep before or at time t exceeds a particular value(Intensity Value).
Now, the aliens go to their "Big Boss" with a time t.
The "Big Boss" then tells whether the alien will wake up till that time t.
Since the queries(q) of the aliens are too large, help the "Big Boss" to answer the queries.

Note: A clock Ci with time period Ti beeps at time: Ti, 2Ti, 3Ti, ... so on.

Input Format:
The first line contains an integer n denoting the number of clocks.

The next line contains n space separated integers denoting the time periods of the n respective clocks.

The next line contains p denoting the number of aliens.

The next p lines contain two space separated integers b and i, denoting the Beep Value and Intensity Value of the respective aliens

The next line contains q denoting the number of queries.

The next q lines contain two space separated integers in and t, denoting the alien  Ain and the time t respectively.

Output Format:
For each of the q lines, output "Awake" if the alien Ain will awake before time t, 
else output "Asleep", if the alien does not wake up before time t. 

Constraints:
1 ≤ n ≤ 10^5
1 ≤ time period of any clock ≤ 10^3
1 ≤ p ≤ 10^3
1 ≤ q ≤ 10^5
1 ≤ i ≤ n
1 ≤ t ≤ 10^5
1 ≤ b ≤ tSAMPLE INPUT
3
1 2 3
3
3 3
3 1
4 2
3
1 3
2 3
3 2

SAMPLE OUTPUT
Asleep
Awake
Asleep

Explanation

At time t = 1, no of beeps = 1 and maximum intensity value is 1

At time t=2, no of beeps = 2 and maximum intensity value is 2

At time t=3, no of beeps = 3 and maximum intensity value is 3.

For the 1st query, the alien A1 will be asleep at t=3, because the no of  beeps(3) do not exceed 3 and maximum intensity does not exceed 3.

For the 2nd query, the alien A2 will wake up at t=3, because the maximum intensity(2) exceeds 1.

For the 3rd query, the alien A3 will be asleep at t=2, because the no of beeps(2) do not exceed 4 and maximum intensity(2) does not exceed 2.

Source: hackerearth | Difficulty: MEDIUM


Solutions: