Limits 1s, 512 MB

Spider-Man is fighting the Sinister Six. While fighting he was hit in the head But he somehow managed to defeat all six. For the damages he suffered, his stamina is limited. He wants to go home to rest as soon as possible. He is a few blocks far from home.

There lies n\bm n buildings on the path to his way home, ith\bm i^{\bm t \bm h} building from the start has Ai\bm A_{\bm i} unit of height. Spider-Man is initially standing on top of the 1st\bm 1^{\bm s\bm t} building and his home is on top of the nth\bm n^{\bm t\bm h} building. As he is damaged from his fight and cannot use his webs he will climb the buildings.

While climbing,
He loses 1\bm 1 unit of stamina for 1\bm 1 unit of height climbed up.
He gains
1\bm 1 unit of stamina for 1\bm 1 unit of height climbed down.

If he does not have the stamina left to climb up or down at any point before reaching home, he will be stuck and won’t be able to go home.

Now, Spider-man is wondering if he can reach his home if he starts with x\bm x unit of stamina.

Input

The first line will be a single integer n\bm n indicating the number of buildings. In the next line, there will be n\bm n space-separated integers, Ai\bm A_{\bm i} denoting the height of ith\bm i^{\bm t\bm h} building (1in)(1 \leq\bm i \leq n). The next line will have an integer q\bm q. Each of the next q\bm q lines will contain an integer in each line denoting x\bm x, the amount of stamina left after the fight.
1n1051 \leq\bm n \leq 10^5
1Ai1091 \leq\bm A_{\bm i} \leq 10^9
1q1031 \leq \bm q \leq 10^3
0x1090 \leq \bm x \leq 10^9

Output

You have to output qq lines for each query. You have to print “Homecoming” if Spider-Man can reach home, “No way Home”, otherwise.

Samples

InputOutput
7
1 4 3 6 2 3 4
6
3
5
2
10
1
6
No way Home
Homecoming
No way Home
Homecoming
No way Home
Homecoming
InputOutput
5
1 3 4 1 5
2
3
4
No way Home
Homecoming

In the second case the building heights are given in the second line.

1 3 4 1 5

Initially Spider-Man is on the first building.
His home is on the fifth building.

The first query is for initial stamina, x=3.

  • The 2nd building is 2 units higher than the 1st building.
    Stamina needed to climb is 2 unit.
    Spider-Man has 3 unit stamina.
    x becomes 1 unit.

  • The 3rd building is 1 unit higher than the 2nd building.
    Stamina needed to climb is 1 unit.
    Spider-Man has 1 unit stamina.
    x becomes 0 unit.

  • The 4th building is 3 unit lower than the 3rd building.
    Stamina increment after climb is 1 unit.
    Spider-Man has 0 unit stamina.
    x becomes 3 units.

  • The 5th building is 4 unit higher than the 4th building.
    Stamina needed to climb is 4 unit.
    Spider-Man has 3 unit stamina.
    So he can’t reach home.

The second query is for initial stamina, x=4.

  • The 2nd building is 2 units higher than the 1st building.
    Stamina needed to climb is 2 unit.
    Spider-Man has 4 unit stamina.
    x becomes 2 unit.

  • The 3rd building is 1 unit higher than the 2nd building.
    Stamina needed to climb is 1 unit.
    Spider-Man has 2 unit stamina.
    x becomes 1 unit.

  • The 4th building is 3 unit lower than the 3rd building.
    Stamina increment after climb is 1 unit.
    Spider-Man has 1 unit stamina.
    x becomes 4 units.

  • The 5th building is 4 unit higher than the 4th building.
    Stamina needed to climb is 4 unit.
    Spider-Man has 4 unit stamina.
    So he can reach home climbing the fifth building.


Be careful about the newline(‘\n’) at the end.

Submit

Login to submit.

Statistics

75% Solution Ratio
abu_fayeemEarliest, Mar '22
sourov.cseFastest, 0.0s
yeehawLightest, 524 kB
Ismail.093494Shortest, 352B
Toph uses cookies. By continuing you agree to our Cookie Policy.