Wizard in Maze

Ένας λαβύρινθος αποτελείται από ένα πλέγμα διαστάσεων ~H \times W~, με τετράγωνα - ~H~ κατακόρυφα, ~W~ οριζόντια.

Το τετράγωνο στην ~i~-οστή σειρά από την κορυφή και την ~j~-οστή στήλη από τα αριστερά - ~(i,j)~ - είναι τοίχος αν το ~S_{ij}~ είναι # και δρόμος αν το ~S_{ij}~ είναι ~(.)~ .

Στο ~(C_h,C_w)~ βρίσκεται ένας μάγος ο οποίος μπορεί να κάνει τα δύο ακόλουθα είδη κινήσεων:

• Κίνηση A: Περπατάει σε ένα τετράγωνο δρόμου που είναι κατακόρυφα ή οριζόντια διπλανό στο τετράγωνο στο οποίο βρίσκεται αυτή τη στιγμή.
• Κίνηση B: Χρησιμοποιεί μαγεία για να μεταφερθεί σε ένα τετράγωνο δρόμου στην περιοχή ~5 \times 5~ που έχει κέντρο το τετράγωνο στο οποίο βρίσκεται αυτή τη στιγμή.

Και στις δύο περιπτώσεις, δεν μπορεί να βγει από τον λαβύρινθο. Πόσες είναι οι ελάχιστες φορές που χρειάζεται να χρησιμοποιήσει τη μαγεία του για να φτάσει στο ~(D_h,D_w)~;

Περιορισμοί

• ~1 \le H,W \le 10^3~
• ~1 \le C_h,D_h \le H~
• ~1 \le C_w,D_w \le W~
• ~S_{ij}~ είναι # ή ~(.)~ .
• ~S_{C_hC_w}~ και ~S_{D_hD_w}~ είναι ~(.)~ .
• ~(C_h,C_w) \neq (D_h,D_w)~
• Time Limit: ~2~ sec.
• Memory Limit: ~1024~ MB

Είσοδος

Η είσοδος θα δίνεται από την τυπική είσοδο και θα έχει την ακόλουθη μορφή:

H 

W

Ch Cw

Dh Dw

S11 ... S1W

⋮

SH1 ... SHW

Έξοδος

Εκτυπώστε τον ελάχιστο αριθμό φορών που χρειάζεται ο μάγος να χρησιμοποιήσει τη μαγεία του. Αν δεν μπορεί να φτάσει στο ~(D_h,D_w)~, αντί γι'αυτό εκτυπώστε ~-1~.

Παραδείγματα

1ο

input

4 4
1 1
4 4
..#.
..#.
.#..
.#..

output

1

Επεξήγηση πρώτου παραδείγματος:

Για παράδειγμα, περπατώντας ως το ~(2,2)~ και στη συνέχεια χρησιμοποιώντας τη μαγεία του για να ταξιδέψει ως το ~(4,4)~, αρκεί να τη χρησιμοποιήσει μία φορά.

Σημειώστε ότι δεν μπορεί να περπατήσει διαγωνίως.

2ο

input

4 4
1 4
4 1
.##.
####
####
.##.

output

-1

Επεξήγηση δεύτερου παραδείγματος:

Από εκεί, δεν μπορεί να μετακινηθεί.

3ο

input

4 4
2 2
3 3
....
....
....
....

output

0

Επεξήγηση τρίτου παραδείγματος:

Δεν χρειάζεται να χρησιμοποιήσει μαγεία.

4ο

input

4 5
1 2
2 5
#.###
####.
#..##
#..##

output

2