Ammo X11353

Neo has run out of ammo and quickly needs to find some more. To reach the ammo depot Neo might need to traverse two different dimensions of the Matrix. Help Neo find the shortest path to the ammo depot.

Input

The input consists of several test cases. Each test case starts with the number of rows $1\leq n\leq 100$ and the number of columns $1\leq m\leq 100$ of the Matrix. This is followed by $2n$ rows with $m$ characters each, corresponding to two different dimensions of the Matrix. The character "." is a free cell of the Matrix, "#" is a blocked cell, "P" is a portal that allows Neo to move to the opposite dimension, "N" is Neo’s starting position, and "A" is the ammo depot.

Output

For each test case, a number on a single line representing the minimum distance to the ammo depot, or $-1$ in case Neo cannot reach the ammo depot.