数据范围:
H,W≤2000H,W\leq2000H,W≤2000,P,Q≤2×105P,Q\leq2\times10^5P,Q≤2×105,1≤Si,Ti≤P1\leq S_i,T_i\leq P1≤Si,Ti≤P。
样例:
5 5 4 4 ..... ..##. .#... ..#.. ..... 1 1 4 2 3 3 2 5 1 2 2 4 1 3 3 4