题目背景

有一头名叫Kangkang的奶牛,他因为年老没用了被主人嫌弃，主人做了一个手推车，趁他睡觉时把他丢到了一个迷宫当中，现在Kangkang想要知道怎么走出这个迷宫。

题目描述

Kangkang被困在一个N * M的迷宫里,他刚开始在S字符这个位置，迷宫内墙用#号表示,路径用.表示, 迷宫只有一个出口，用P表示，在迷宫中还会有许多传送路径，这些路径是单向的，在通过传送路径传送到其他地点时是不计入路径长度的，注意,Kangkang已经走过的路径Kangkang不会再次行走,当到达一个传送路径起始点时,并不是强制使用,现在，Kangkang想知道到达出口的最短路径

输入格式

第一行输入两个数字,N和M

接下来N行里每行有M个字符,表示迷宫内的情况

第N + 2行输入一个数字Q，表示这张地图有Q条单向传送路径

接下来Q行每行有4个数字，分别表示起点行，起点列，终点行，终点列

输出格式

只输出一个数字,表示到达出口的最短路径,如果无法到达出口,输出一个-1

样例 #1

样例输入 #1

5 5
S.#.P
..#..
..#..
..#..
..#..
1
5 2 5 5

样例输出 #1

9

提示

样例#1解释

向下走4步,向右走1步到达传送路径传送到5 5,之后向上走4步到达终点，共4+1+4=9步

数据范围

N,M,Q <= 300,保证无自环