You are playing some computer game. One of its levels puts you in a maze consisting of n lines, each of which contains m cells. Each cell either is free or is occupied by an obstacle. The starting cell is in the row r and column c. In one step you can move one square up, left, down or right, if the target cell is not occupied by an obstacle. You can't move beyond the boundaries of the labyrinth.

Unfortunately, your keyboard is about to break, so you can move left no more than x times and move right no more than y times. There are no restrictions on the number of moves up and down since the keys used to move up and down are in perfect condition.

Now you would like to determine for each cell whether there exists a sequence of moves that will put you from the starting cell to this particular one. How many cells of the board have this property?

Input

The first line contains two integers n, m (1 ≤ n, m ≤ 2000) — the number of rows and the number columns in the labyrinth respectively.

The second line contains two integers r, c (1 ≤ r ≤ n, 1 ≤ c ≤ m) — index of the row and index of the column that define the starting cell.

The third line contains two integers x, y (0 ≤ x, y ≤ 109) — the maximum allowed number of movements to the left and to the right respectively.

The next n lines describe the labyrinth. Each of them has length of m and consists only of symbols '.' and '*'. The j-th character of the i-th line corresponds to the cell of labyrinth at row i and column j. Symbol '.' denotes the free cell, while symbol '*' denotes the cell with an obstacle.

It is guaranteed, that the starting cell contains no obstacles.

Output

Print exactly one integer — the number of cells in the labyrinth, which are reachable from starting cell, including the starting cell itself.

Examples

Input

4 5
3 2
1 2
.....
.***.
...**
*....


Output

10


Input

4 4
2 2
0 1
....
..*.
....
....


Output

7

Note

Cells, reachable in the corresponding example, are marked with '+'.

First example: 
    
    
      
    +++..  
    +***.  
    +++**  
    *+++.  
    

Second example: 
    
    
      
    .++.  
    .+*.  
    .++.  
    .++.

Difficulty: MEDIUM_HARD
Tags: Graph algorithms

Shortest paths

Starter code:

Solutions:
import sys
from collections import deque
from math import inf

def rint():
	return map(int, sys.stdin.readline().split())

def bfs(sr, sc):
	global ans
	q = deque()
	q.append((x, y, sr, sc))
	visit[sr][sc] = 1
	ans += 1
	while q:
		(ll, rr, r, c) = q.popleft()
		nadj = []
		if r + 1 < n and maze[r + 1][c] == '.':
			nadj.append([r + 1, c])
		if r - 1 >= 0 and maze[r - 1][c] == '.':
			nadj.append([r - 1, c])
		if c + 1 < m and maze[r][c + 1] == '.':
			nadj.append([r, c + 1])
		if c - 1 >= 0 and maze[r][c - 1] == '.':
			nadj.append([r, c - 1])
		for (adr, adc) in nadj:
			if visit[adr][adc] == 1:
				continue
			if c == adc:
				visit[adr][adc] = 1
				ans += 1
				q.appendleft([ll, rr, adr, adc])
			elif adc < c:
				if ll - 1 >= 0:
					visit[adr][adc] = 1
					ans += 1
					q.append([ll - 1, rr, adr, adc])
			elif rr - 1 >= 0:
				visit[adr][adc] = 1
				ans += 1
				q.append([ll, rr - 1, adr, adc])
(n, m) = rint()
(sr, sc) = rint()
(x, y) = rint()
sr -= 1
sc -= 1
maze = []
for i in range(n):
	maze.append(input())
visit = [[0 for i in range(m)] for j in range(n)]
ans = 0
bfs(sr, sc)
print(ans)


from collections import deque
(n, m) = map(int, input().split())
(sx, sy) = map(int, input().split())
(tl, tr) = map(int, input().split())
g = [input() for i in range(n)]
sx -= 1
sy -= 1
dis = [[-1 for j in range(m)] for i in range(n)]
q = deque()

def go(x, y, s, left=False):
	if 0 <= x < n and 0 <= y < m:
		if g[x][y] == '.' and dis[x][y] == -1:
			dis[x][y] = s
			if left:
				q.appendleft((x, y))
			else:
				q.append((x, y))
go(sx, sy, 0)
ans = 0
while q:
	(x, y) = q.popleft()
	s = dis[x][y]
	ans += s + y - sy <= tr * 2 and s - y + sy <= tl * 2
	go(x - 1, y, s, left=True)
	go(x + 1, y, s, left=True)
	go(x, y - 1, s + 1)
	go(x, y + 1, s + 1)
print(ans)


from collections import deque
(n, m) = map(int, input().split())
(r, c) = map(int, input().split())
r -= 1
c -= 1
(x, y) = map(int, input().split())
grid = []
for i in range(n):
	s = input()
	grid.append(s)
visited = []
for i in range(n):
	visited.append([0] * m)
visited[r][c] = 1
stack = deque([(r, c, 0)])
stack2 = []
ans = 0
while stack or stack2:
	if not stack:
		for (i, j, k) in stack2:
			stack.append((i, j, k))
		stack2 = []
	(i, j, val) = stack.popleft()
	if visited[i][j] != val + 1:
		continue
	ans += 1
	visited[i][j] = 1
	if i > 0 and grid[i - 1][j] == '.' and (not visited[i - 1][j] or visited[i - 1][j] > val + 1):
		stack.append((i - 1, j, val))
		visited[i - 1][j] = val + 1
	if i < n - 1 and grid[i + 1][j] == '.' and (not visited[i + 1][j] or visited[i + 1][j] > val + 1):
		stack.append((i + 1, j, val))
		visited[i + 1][j] = val + 1
	if j > 0 and grid[i][j - 1] == '.' and (not (val + 1 > x or j - 1 + val + 1 - c > y)) and (not visited[i][j - 1] or visited[i][j - 1] > val + 2):
		stack2.append((i, j - 1, val + 1))
		visited[i][j - 1] = val + 2
	if j < m - 1 and grid[i][j + 1] == '.' and (not (val > x or j + 1 + val - c > y)) and (not visited[i][j + 1] or visited[i][j + 1] > val + 1):
		stack.append((i, j + 1, val))
		visited[i][j + 1] = val + 1
print(ans)


(n, m) = map(int, input().split())
(r, c) = map(int, input().split())
(r, c) = (r - 1, c - 1)
(X, Y) = map(int, input().split())
S = [input() for i in range(n)]
L = [[-1] * m for i in range(n)]
R = [[-1] * m for i in range(n)]
from collections import deque
q = deque([])
q.append((r, c))
L[r][c] = 0
R[r][c] = 0
while q:
	(y, x) = q.popleft()
	for dy in (-1, 1):
		(ny, x) = (y + dy, x)
		if 0 <= ny < n:
			if S[ny][x] == '*':
				continue
			if L[ny][x] == -1 and R[ny][x] == -1:
				q.appendleft((ny, x))
				L[ny][x] = L[y][x]
				R[ny][x] = R[y][x]
			if L[ny][x] > L[y][x]:
				L[ny][x] = L[y][x]
			if R[ny][x] > R[y][x]:
				R[ny][x] = R[y][x]
	for dx in (-1, 1):
		(y, nx) = (y, x + dx)
		if 0 <= nx < m:
			if S[y][nx] == '*':
				continue
			if L[y][nx] == -1 and R[y][nx] == -1:
				q.append((y, nx))
				if dx == 1:
					R[y][nx] = R[y][x] + 1
					L[y][nx] = L[y][x]
				else:
					L[y][nx] = L[y][x] + 1
					R[y][nx] = R[y][x]
			if L[y][nx] > L[y][x] + 1:
				L[y][nx] = L[y][x] + 1
			if R[y][nx] > R[y][x] + 1:
				R[y][nx] = R[y][x] + 1
ans = 0
for i in range(n):
	for j in range(m):
		if L[i][j] == -1 or R[i][j] == -1:
			continue
		if L[i][j] <= X and R[i][j] <= Y:
			ans += 1
print(ans)


from collections import deque
(n, m) = map(int, input().split())
(r, c) = map(int, input().split())
(x, y) = map(int, input().split())
gr = []
vd = [[0] * m for i in range(n)]
r -= 1
c -= 1
ans = 0
for i in range(n):
	gr.append(input())
to_visit = deque()
to_visit.append((r, c, x, y))
while to_visit:
	(ri, ci, xi, yi) = to_visit.popleft()
	ru = ri
	while ru >= 0 and gr[ru][ci] == '.' and (not vd[ru][ci]):
		vd[ru][ci] = 1
		ans += 1
		if xi > 0 and ci - 1 >= 0 and (gr[ru][ci - 1] == '.') and (not vd[ru][ci - 1]):
			to_visit.append((ru, ci - 1, xi - 1, yi))
		if yi > 0 and ci + 1 < m and (gr[ru][ci + 1] == '.') and (not vd[ru][ci + 1]):
			to_visit.append((ru, ci + 1, xi, yi - 1))
		ru -= 1
	rd = ri + 1
	while rd < n and gr[rd][ci] == '.' and (not vd[rd][ci]):
		vd[rd][ci] = 1
		ans += 1
		if xi > 0 and ci - 1 >= 0 and (gr[rd][ci - 1] == '.') and (not vd[rd][ci - 1]):
			to_visit.append((rd, ci - 1, xi - 1, yi))
		if yi > 0 and ci + 1 < m and (gr[rd][ci + 1] == '.') and (not vd[rd][ci + 1]):
			to_visit.append((rd, ci + 1, xi, yi - 1))
		rd += 1
print(ans)


from collections import deque

def move(tx, ty, s, left=False):
	if 0 <= tx < n and 0 <= ty < m:
		if smap[tx][ty] == '.' and mp[tx][ty] == -1:
			mp[tx][ty] = s
			if left:
				q.appendleft((tx, ty))
			else:
				q.append((tx, ty))
[n, m] = map(int, input().split())
[sx, sy] = map(int, input().split())
[ll, rr] = map(int, input().split())
smap = [input() for i in range(n)]
q = deque()
mp = [[-1] * m for i in range(n)]
(sx, sy) = (sx - 1, sy - 1)
mp[sx][sy] = 0
ans = 0
q.append((sx, sy))
while q:
	(px, py) = q.popleft()
	s = mp[px][py]
	ans += s + py - sy <= rr * 2 and s - py + sy <= ll * 2
	move(px + 1, py, s, left=True)
	move(px - 1, py, s, left=True)
	move(px, py - 1, s + 1)
	move(px, py + 1, s + 1)
print(ans)


import queue
import collections
(n, m) = list(map(int, input().split()))
(x, y) = list(map(int, input().split()))
(l, r) = list(map(int, input().split()))
maze = []
for _ in range(n):
	maze.append(list(input()))
cost = [[float('inf')] * m for _ in range(n)]

def bfs(start_x, start_y):
	cost[start_x][start_y] = 0
	q = collections.deque([(start_x, start_y)])
	while q:
		(x, y) = q.popleft()
		if 0 < x and maze[x - 1][y] == '.' and (cost[x][y] < cost[x - 1][y]):
			q.append((x - 1, y))
			cost[x - 1][y] = cost[x][y]
		if x < n - 1 and maze[x + 1][y] == '.' and (cost[x][y] < cost[x + 1][y]):
			q.append((x + 1, y))
			cost[x + 1][y] = cost[x][y]
		if l > 0 and 0 < y and (maze[x][y - 1] == '.') and (cost[x][y] < cost[x][y - 1]):
			q.append((x, y - 1))
			cost[x][y - 1] = cost[x][y]
		if r > 0 and y < m - 1 and (maze[x][y + 1] == '.') and (cost[x][y] + 1 < cost[x][y + 1]) and (cost[x][y] < r):
			q.append((x, y + 1))
			cost[x][y + 1] = cost[x][y] + 1
bfs(x - 1, y - 1)
v = 0
for i in range(n):
	for j in range(m):
		if cost[i][j] + (y - 1) - j <= l:
			v += 1
print(v)


import collections
(n, m) = map(int, input().split())
(r, c) = map(int, input().split())
(x, y) = map(int, input().split())
arr = []
for i in range(n):
	arr.append(input())
que = collections.deque([(r - 1, c - 1)])
dist = [[float('inf')] * m for i in range(n)]
dist[r - 1][c - 1] = 0
while que:
	v = que.popleft()
	if v[0] > 0 and arr[v[0] - 1][v[1]] != '*' and (dist[v[0] - 1][v[1]] > dist[v[0]][v[1]]):
		dist[v[0] - 1][v[1]] = dist[v[0]][v[1]]
		que.appendleft((v[0] - 1, v[1]))
	if v[0] < n - 1 and arr[v[0] + 1][v[1]] != '*' and (dist[v[0] + 1][v[1]] > dist[v[0]][v[1]]):
		dist[v[0] + 1][v[1]] = dist[v[0]][v[1]]
		que.appendleft((v[0] + 1, v[1]))
	if v[1] < m - 1 and arr[v[0]][v[1] + 1] != '*' and (dist[v[0]][v[1] + 1] > dist[v[0]][v[1]]):
		dist[v[0]][v[1] + 1] = dist[v[0]][v[1]]
		que.appendleft((v[0], v[1] + 1))
	if v[1] > 0 and arr[v[0]][v[1] - 1] != '*' and (dist[v[0]][v[1] - 1] > dist[v[0]][v[1]] + 1):
		dist[v[0]][v[1] - 1] = dist[v[0]][v[1]] + 1
		que.append((v[0], v[1] - 1))
count = 0
for i in range(n):
	for e in range(m):
		if dist[i][e] <= x and e - (c - 1) + dist[i][e] <= y:
			count += 1
print(count)