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?

You are given array A of N integers. You are given Q queries on the array. In each query there are three integers L, R and K. You need to print YES if there exists a subarray of the array A in which there are at least K distinct integers that appear in the range L to R of the natural numbers.

Could anyone give hints on how to solve this problem?