Time limit per test: 0.25 second(s) Memory limit: 65536 kilobytes
input: standard output: standard
One day Vasya decided to buy a bottle of his favourite Kola in the old vending machine. But he forgot that there was a Halloween that day, so evil forces had made an inner structure of the vending machine quite complicated. Inside the machine is represented by a table of size n × m. Some of the cells are empty, and some contains obstacles of two types: '/' and '\'. One of the cell initially contains a bottle of Kola. After the purchasing it starts to fall vertically down by the following rules:
If a cell immediately below the bottle is empty, the bottle falls down.
If the bottle falls down from the lowest row, it falls to the tray and Vasya can take it.
Reaching and obstacle '/' ('\') the bottle moves left (right) without changing it's row and tries to continue to fall down if it is possible.
The bottle stops to move when there is a wall in the current moving direction.
The bottle stops to move when it moves from the cell with an obstacle of one type to the cell with an obstacle of another type.
But if the bottle moves to the cell with the same type of obstacle as in the current cell, it continues moving down.
Help Vasya to find out whether the bottle will reach the tray. In case of a positive answer, determine the number of column where it will happen.
The first line of the input contains two integer numbers n and m (1 ≤ n, m ≤ 100). Then the description of the vending machine follows. It consists of n lines of m characters each: '.' means empty cell, 'P' means initial position of the bottle, '/' and '\' — mean obstacles of the corresponding type. It is guaranteed that the 'P' character appears exactly once.
Print to the output -1 if the bottle doesn't reach the tray. Otherwise print the number of the column where the bottle will leave the vending machine. Columns are numbered starting from 1 from the leftmost one.
Codeforces (c) Copyright 2010-2023 Mike Mirzayanov