전쟁중인 코딩나라의 연구원인 구름이는 생화학 무기 개발을 하느라 실험실에 들어가 있다. 이 실험실은 생화학 무기가 밖으로 반출이 잘 안되게 하기 위해 미로와 같이 설계가 되어있다. 어느날 실험중인 생화학 무기가 폭발하였고, 구름이는 이 실험실에서 생화학무기에 감염되지 않고 탈출을 해야한다. 매 초마다 생화학 무기는 상하좌우 인접한 빈 공간으로 퍼져나간다. 단, 벽을 통과하지는 못한다. 구름이는 상하좌우 인접한 칸으로 1초에 한 칸씩 이동할 수 있으며, 벽을 통과할 수 없고, 생화학 무기와 접촉하면 감염되므로 생화학 무기가 퍼진 칸으로는 이동할 수 없다. 구름이가 있던 칸에 생화학 무기가 퍼짐과 동시에 다른 칸으로 이동할 때는 감염되지 않는다. 이 실험실의 지도가 주어졌을 때, 구름이가 최대한 빠르게 실험실을 탈출할 경우에 걸리는 시간을 구하여라.

입력

첫째 줄에는 실험실 지도 너비와 높이 W와 H가 주어진다. (1 ≤ W,H ≤ 1000)

다음 H개 줄에는 W개의 문자, 실험실의 지도가 주어진다.

• '-': 빈 공간
• '#': 벽
• '*': 구름이의 시작 위치
• '+': 생화학 무기

각 지도에 *의 개수는 하나이고, +의 개수는 여러개일 수 있다.

출력

실험실을 탈출하는데 걸리는 가장 빠른 시간을 출력한다. 실험실을 탈출할 수 없는 경우에는 -1을 출력한다.