Problem: Snuke, a water strider, lives in a rectangular pond that can be seen as a grid with H east-west rows and W north-south columns. Let (i,j) be the square at the i-th row from the north and j-th column from the west.

Some of the squares have a lotus leaf on it and cannot be entered. The square (i,j) has a lotus leaf on it if c_{ij} is `@`, and it does not if c_{ij} is `.`.

In one stroke, Snuke can move between 1 and K squares (inclusive) toward one of the four directions: north, east, south, and west. The move may not pass through a square with a lotus leaf. Moving to such a square or out of the pond is also forbidden.

Find the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2). If the travel from (x_1,y_1) to (x_2,y_2) is impossible, point out that fact.

Constraints

* 1 \leq H,W,K \leq 10^6
* H \times W \leq 10^6
* 1 \leq x_1,x_2 \leq H
* 1 \leq y_1,y_2 \leq W
* x_1 \neq x_2 or y_1 \neq y_2.
* c_{i,j} is `.` or `@`.
* c_{x_1,y_1} = `.`
* c_{x_2,y_2} = `.`
* All numbers in input are integers.

Input

Input is given from Standard Input in the following format:


H W K
x_1 y_1 x_2 y_2
c_{1,1}c_{1,2} .. c_{1,W}
c_{2,1}c_{2,2} .. c_{2,W}
:
c_{H,1}c_{H,2} .. c_{H,W}


Output

Print the minimum number of strokes Snuke takes to travel from the square (x_1,y_1) to (x_2,y_2), or print `-1` if the travel is impossible.

Examples

Input

3 5 2
3 2 3 4
.....
.@..@
..@..


Output

5


Input

1 6 4
1 1 1 6
......


Output

2


Input

3 3 1
2 1 2 3
.@.
.@.
.@.


Output

-1

Solution (in JAVA):

Solution:
import java.io.*;
import java.lang.reflect.Array;
import java.math.BigDecimal;
import java.math.BigInteger;
import java.math.RoundingMode;
import java.text.DecimalFormat;
import java.util.*;
import java.util.regex.Matcher;
import java.util.regex.Pattern;

public class Main
{	
	
   static long mod=(long)(1e+9 + 7);
	
   //static long mod=(long)998244353;
   static int[] sieve;
   
   static ArrayList<Integer> primes;
   static PrintWriter out;
   static fast s;
   static StringBuilder fans;
   
   static int x_dir[];
   static int y_dir[];
   
   static class Pair
   {
   	int dir;
   	int r;
   	int c;
   	int val;
   	int kk;
   	public Pair(int x,int y,int z,int w,int p)
   	{
   		this.dir=x;
   		this.r=y;
   		this.c=z;
   		this.val=w;
   		this.kk=p;
   	}
   }
   
   static class comp  implements Comparator<Pair>
   	{
   		public int compare(Pair a,Pair b)
   		{
   			if(a.val<b.val) return -1;
   			if(a.val>b.val) return 1;
   			if(a.kk<b.kk)return -1;
   			if(a.kk>b.kk)return 1;
   			return 0;
   		}
   	}
   
   public static boolean check(int x,int y,int a[][])
   {
   	if(x<1 || y<1 || x>=a.length || y>=a[0].length || a[x][y]==0) return false;
   	return true;
   }
   
   public static void solve()
   {
   	int n=s.nextInt();
   	int m=s.nextInt();
   	int fk=s.nextInt();
   	//for(int i=1;i<=n;i++) for(int j=1;j<=m;j++) a[i][j]=1;

   	int r1=s.nextInt();
   	int c1=s.nextInt();
   	int r2=s.nextInt();
   	int c2=s.nextInt();

   	int a[][]=new int[n+1][m+1];
   	
   	for(int i=1;i<=n;i++)
   		{
   			String str=s.nextLine();
   			for(int j=0;j<str.length();j++)
   				if(str.charAt(j)=='.') a[i][j+1]=1;
   		}
   	  	
   	PriorityQueue<Pair> qu=new PriorityQueue<Pair>(new comp());
   	int visited[][][]=new int[6][n+1][m+1];
   	
   	qu.add(new Pair(-1,r1,c1,0,0));
   	
   	int ans=Integer.MAX_VALUE;
   	x_dir=new int[] {0,0,-1,1};
   	y_dir=new int[] {1,-1,0,0};
   	
   	while(qu.size()>0)
   		{
   			Pair cur=qu.poll();

   			if(cur.r==r2 && cur.c==c2) {ans=Math.min(ans, cur.val);break;}
   			
   			if(visited[cur.dir+1][cur.r][cur.c]==1) continue;
   			visited[cur.dir+1][cur.r][cur.c]=1;
   			
   			for(int k=0;k<4;k++)
   				{
   					int new_r=cur.r+x_dir[k];
   					int new_c=cur.c+y_dir[k];
   					int new_dir=k;
   				   int new_val=cur.val;
   				   int new_kk=cur.kk;
   				   
   				   if(new_dir!=cur.dir) {new_val++;new_kk=1;}
   				   else {
   				   	new_kk++;
   				   	if(new_kk>fk) {new_val++;new_kk=1;}
   				   }
   				   
   				   if(check(new_r,new_c,a) && visited[new_dir+1][new_r][new_c]==0)
   				   	{
   				         qu.add(new Pair(new_dir,new_r,new_c,new_val,new_kk));
   				   	}
   				}
   		}
   	
   	//System.out.println(cnt);
   	if(ans==Integer.MAX_VALUE) ans=-1;
   	fans.append(ans+"\n");
   }
   
   public static void main(String[] args) throws java.lang.Exception
   {	  	
	     s = new fast();
	     
	     out=new PrintWriter(System.out);
	     fans=new StringBuilder("");
		  
	     int t=1;
	     
	     while(t>0)
	    	 {
	    		 solve();
	    		 t--;
	    	 }
	    
	    out.println(fans);
	    out.close();
   }
  
 
 
static class fast {   
	
	   private InputStream i;
		private byte[]  buf = new byte[1024];
		private int curChar;
		
		private int numChars;
		
		//Return floor log2n
		public static long log2(long bits) // returns 0 for bits=0
			{
			    int log = 0;
			    if( ( bits & 0xffff0000 ) != 0 ) { bits >>>= 16; log = 16; }
			    if( bits >= 256 ) { bits >>>= 8; log += 8; }
			    if( bits >= 16  ) { bits >>>= 4; log += 4; }
			    if( bits >= 4   ) { bits >>>= 2; log += 2; }
			    return log + ( bits >>> 1 );
			}
		
		public static boolean next_permutation(int a[])
		   {
			   int i=0,j=0;int index=-1;	   
			   int n=a.length;
			   
			   for(i=0;i<n-1;i++)
				   if(a[i]<a[i+1]) index=i;
			   
			   if(index==-1) return false;
			   i=index;
 
			  
			   for(j=i+1;j<n && a[i]<a[j];j++);
 
			   int temp=a[i];
			   a[i]=a[j-1];
			   a[j-1]=temp;
			   	   
			   for(int p=i+1,q=n-1;p<q;p++,q--)
			   {
				   temp=a[p];
				   a[p]=a[q];
				   a[q]=temp;
			   }
			   
			   return true;
		   }
		   
		public static void sieve(int size)
		{
			sieve=new int[size+1];
			
			primes=new ArrayList<Integer>();
			
			sieve[1]=1;
			
			for(int i=2;i*i<=size;i++)
			{
				if(sieve[i]==0)
				 {
					for(int j=i*i;j<size;j+=i) {sieve[j]=1;}
				 }
			}
			
			for(int i=2;i<=size;i++)
			{
				if(sieve[i]==0) primes.add(i);
			}
		}
		
		public static long pow(long a, long p){
		    long o = 1;
		    for(; p>0; p>>=1){
		        if((p&1)==1)o = mul(o, a);
		        a = mul(a, a);
		    }
		    return o;
		}
		
		public static long add(long... a){
		    long o = 0;
		    for(long x:a)o = (o+mod+x)%mod;
		    return o;
		}
		
		public static long mul(long... a){
		    long p = 1;
		    for(long x:a)p = (mod+(p*x)%mod)%mod;
		    return p;
		}
		
		public static long mod_inv(long n)
		{
			return pow(n,mod-2);
		}
		   
		public long gcd(long r,long ans)
		{
			if(r==0) return ans;
			return gcd(ans%r,r);
		}
		
		public fast() {
			this(System.in);
		}
		public fast(InputStream is) {
			i = is;
		}
		public int read() {
			if (numChars == -1)
				throw new InputMismatchException();
			if (curChar >= numChars) {
				curChar = 0;
				try {
					numChars = i.read(buf);
				} catch (IOException e) {
					throw new InputMismatchException();
				}
				if (numChars <= 0)
					return -1;
			}
			return buf[curChar++];
		}
		public String nextLine() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isEndOfLine(c));
			return res.toString();
		}
		public String nextString() {
     		int c = read();
			while (isSpaceChar(c))
				c = read();
			StringBuilder res = new StringBuilder();
			do {
				res.appendCodePoint(c);
				c = read();
			} while (!isSpaceChar(c));
			return res.toString();
		}
		public long nextLong() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			long res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public int nextInt() {
			int c = read();
			while (isSpaceChar(c))
				c = read();
			int sgn = 1;
			if (c == '-') {
				sgn = -1;
				c = read();
			}
			int res = 0;
			do {
				if (c < '0' || c > '9')
					throw new InputMismatchException();
				res *= 10;
				res += c - '0';
				c = read();
			} while (!isSpaceChar(c));
			return res * sgn;
		}
		public boolean isSpaceChar(int c) {
			return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
		}
		public boolean isEndOfLine(int c) {
			return c == '\n' || c == '\r' || c == -1;
		}
 
	}	
}