It's Christmas! But unfortunately, Santa's sleigh stopped working! So he has asked Encodeous to help deliver his presents. Santa gave him an ~N~ by ~M~ grid to show where to deliver them. Santa told him that he must travel to a specified destination while picking up a present along the way. To pick it up, he must stand exactly over the location of the present.

Santa's grid will contain the following characters:

• # representing a wall that he cannot travel through.
• * representing empty space.
• P indicating the location of the present.
• O indicating his starting point.
• X indicating where he should drop the present off.

Encodeous can either move up, down, left, or right from his position, but he cannot pass through walls or walk diagonally.

Since you are his trusty helper, he wants you to find the minimum distance to complete his delivery.

For Python users, it is recommended to use PyPy to solve this problem.

Input Specification

The first line contains the integers ~(4 \le N \le 1\,000)~ and ~(4 \le M \le 1\,000)~ representing rows and columns respectively.

The next ~N~ lines contain ~M~ characters, specifying Santa's grid.

It is guaranteed that there will be a border around the edge of every grid and positions may be visited multiple times.

Output Specification

Your program should output the minimum distance for his delivery. If it is not possible to deliver the present, print -1.

Sample Input

7 10
##########
#*#****P*#
#***#****#
###*####*#
#***##***#
#O**#***X#
##########

Sample Output

15

Explanation

The optimal path has a length of 15.

From the starting point, he should follow this path to complete his mission. (As shown below with + representing where he travelled)

##########
#*#++++P+#
#**+#***+#
###+####+#
#**+##**+#
#O++#***X#
##########

He travels 2 right, 4 up, and 5 right, running through P, and 4 more down to X.

There may be multiple paths he could take, but the minimum distance is always unique.