MYQ11 - The Lazy Gamer

In the kingdom of Thuvax, a mobile game called Thuball became very popular. The description of the game is as follows: A mobile phone made in Thuvax has a screen made of X*Y pixels. Thuball is played by throwing a ball (of size 1 pixel) at an angle of 45 degrees from the bottom of the screen. The ball changes its direction if and only if it hits the left/right/top edge of the screen or an obstacle on its way.

There are N fixed obstacles (of size 1 pixel each) on the screen. There are no obstacles in the bottom-most row of the screen. If the moving ball's edge comes in contact with an obstacle's edge, it gets reflected by 90 degrees. If the moving ball's corner comes in contact with an obstacle's corner, it is reflected by 180 degrees. In both reflections the obstacle doesn't move.

There is a reflector of length L pixels placed below the bottom row, which reflects (akin to mirror reflection, i.e. 90 degrees) the ball incident on it. The game finishes only when the ball reaches the bottom row and the reflector is not present below it. The total distance (in pixels) travelled by the ball is the score attained during a round until the game finishes. If the game does not finish, the score is 0.

Gosu, a Thuvaxian was very fond of this game. He had set the highest score in Thuball in his friend Visu's phone. Not happy with the situation where he didn't have the highest score, Visu decided to recruit you to do his dirty work. Visu is lazy and doesn't want to move the reflector after starting the game. But, he wants to ensure that he gets the highest score possible with a reflector of length L when its kept stationary in any position. Help Visu out by telling him the maximum score he can get without moving the reflector for Q different lengths.

Input

  • First line contains two integers X and Y, which are the height and width of the screen. (1 ≤ X, Y ≤ 1000)
  • Second line contains the number of obstacles N followed by N lines with two integers xi and yi, position of each obstacle.
  • Consider the bottom-left corner of the screen as origin and the top-right corner to have the coordinates: (X-1, Y-1).
  • The next line contains Q, for the number of cases (for different lengths of the reflector). (1 ≤ Q ≤ 1000)
  • Followed by Q lines with one positive integer L, representing the length of the reflector.

Output

For each query output the maximum score Visu can achieve without moving the reflector in a single line.

Example

Input:
3 4
1
2 3
1
3

Output:
6

Added by:jack(chakradarraju)
Date:2012-02-16
Time limit:0.100s-1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Bytecode 2012

hide comments
2012-03-17 18:02:13 :D
It's intuitive, but 90 deg. reflections takes priority. So you will have that reflections in this cases (ball marked by 'X' flying up-right):

### ..#
.X. .X#
... ..#

Also this will cause 180 deg. reflection (again flying in up-right direction):

.#.
.X#
...

Also the ball must start at position where the reflector is underneath.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.