John the tractorist is driving his tractor around the fields of his native village.
The field he is currently located on can be described by an $$$n \cdot m$$$ matrix, each cell of which is assigned one of the following characters: '$$$p$$$'-simple dirt, '$$$s$$$'-highway and '$$$a$$$'-arable land.
John must move his tractor from the cell located at the intersection of row $$$y_1, 1\leq y_1 \leq n$$$ and column $$$x_1, 1\leq x_1 \leq m$$$, to the cell $$$y_2, x_2$$$.
It takes John 1 unit of time to pass through a cell with the character '$$$s$$$' assigned to it, 2 units of time to pass through a cell '$$$p$$$' and 3 units of time to pass through a cell '$$$a$$$'.
Driving this far can take a lot of time, so the mayor of the village promised to help John. The mayor can transform at most $$$k$$$ cells of type '$$$p$$$' to cells of type '$$$s$$$'.
Now, John has given you a very important task. You must find the minimal possible time needed for John to drive from cell $$$y_1, x_1$$$ to cell $$$y_2, x_2$$$, considering that the mayor changes the cells in an optimal way.
***Notice that passing the starting cell consumes John's time, and arriving at the destination cell also consumes some of John's time, according to the type of the destination cell.
***Notice that the mayor can change the values of the beginning and destination cells if any of these cells have the value '$$$p$$$' associated with them.
The first line consists of three integers $$$n, m, k ( 1\leq n\cdot m\cdot k \leq 10^{6}) $$$ — the number of rows of the matrix, the number of columns of the matrix and the maximal number of cells of type '$$$p$$$' that can be transformed to cells of type '$$$s$$$'.
The next line of input contains the numbers $$$y_1, x_1, y_2, x_2 (1\leq y_1 \leq n, 1\leq x_1 \leq m , 1\leq y_2 \leq n, 1\leq x_2 \leq m)$$$, describing the starting cell and the destination cell of the tractor's walk.
Each line $$$i$$$ of the next $$$n$$$ lines, contains $$$m$$$ characters $$$a_{i,1}a_{i,2}...a_{i,m-1}a_{i,m}$$$ ($$$a_{i,j}$$$='$$$a$$$' or $$$a_{i,j}$$$='$$$p$$$' or $$$a_{i,j}$$$='$$$s$$$')
Print a single integer $$$x$$$ — the minimum possible amount of time needed for the tractor to achieve the destination cell from the starting cell, if the cells of type '$$$p$$$' are transformed into cells of type '$$$s$$$' in an optimal, admissible way.
4 4 2 4 1 1 4 sppa apap sssa apaa
12
4 4 2 4 1 1 4 aaap ssss papa sspa
7
