Bob is living in a city in which houses are arranged in N*M blocks The city is denoted by N strings having M characters such that '.' denotes house while '#' denotes forests. Bob has to pay a certain amount LCost, RCost, UCost, DCost to move 1 step accross left, right, up or down respectively. Bob lives in a house having coordinates (Stx, Sty)(1-Based indexing). You are given Q tasks contains an integer X each. In each task, you have to find number of unique houses (including his house) can be travelled using the amount X.

Constraints 1<=N,M<=1000 1<=LCost,RCost,UCost,DCost<=10^9 1<=Q<=10^5 0<=X<=10^18 Time limit 1 second

Sample input

3 4 (N, M)

..#.

#...

..#.

1 2 3 4 (LCost, RCost,UCost, DCost)

2 3 (Stx, Sty)

3 (Q)

2 (X)

5 (X)

10 (X)

Output 3 7 9 Could anyone give hint on how to solve this problem?