17733번 - Water Bottle 서브태스크다국어

JOI 君の住む IOI 市は，1 年を通じてとても暑くなることが知られている．

IOI 市は，縦 H × 横 W マスに区切られた長方形の形をしている．それぞれのマスは，建物か，野原か， 壁のいずれかである．建物のマスは P 個あり，1 から P までの番号が付けられている．

JOI 君は，建物か野原のマスのみに入ることができる．また，あるマスから直接移動できるマスは，そ のマスと隣接している（すなわち，1 辺を共有している）マスのみであり，JOI 君は移動の途中で IOI 市の 外に出ることはできない．

JOI 君は，様々な用事のためにいろいろな建物の間を歩いて移動する必要がある．建物の中は冷房が効い ているが，野原は日差しが強く暑いため，野原のマスを 1 マス通るごとに水が 1 必要である．さらに野原 には自動販売機や水飲み場などはないので，IOI 市では水筒を持って移動を行うことが一般的である．大 きさ x の水筒には，水を最大で x 入れることができる．建物のマスには水道があるので，水筒いっぱいに 水を補給することができる． 大きい水筒は持ち運びが大変なので，JOI 君はできるだけ小さい水筒を用いて移動を行いたい．そこで， いくつかの建物間の移動について，JOI 君がその移動のために必要な水筒の大きさの最小値を求めるプロ グラムを書いてほしい．

IOI 市の地図および，Q 個の質問が与えられる．i 番目 (1 5 i 5 Q) の質問は，「建物 S i , Ti の間を移動する のに必要な水筒の大きさの最小値は何か」というものである．このとき，それぞれの質問に答えるプログ ラムを作成せよ．

標準入力から以下のデータを読み込め．

• 1 行目には整数 H, W, P, Q が空白を区切りとして書かれている．これは，IOI 市は縦 H × 横 W マスに 区切られた長方形の形をしており，IOI 市には建物のマスが P 個あり，プログラムに与えられる質問 の数が Q であることを表す．
• 続く H 行には IOI 市の地図が書かれている．このうちの r 行目 (1 ≤ r ≤ H) には，W 文字の文字列 が書かれており，この文字列の各文字は “.” または “#” のいずれかである．この文字列の c 文字目 (1 ≤ c ≤ W) は，IOI 市の上から r 行目，左から c 列目のマスが何であるかを表し，“.” は建物または 野原を，“#” は壁を表す．
• 続く P 行には IOI 市にある建物の位置が書かれている．このうちの j 行目 (1 ≤ j ≤ P) には，整数 A_j, Bj が空白を区切りとして書かれている．これは，建物 j が IOI 市の上から A_j 列目，左から B_j 行 目のマスにあることを表す．先に与えられる地図上で，対応するマスは “.” であることが保証される．
• 続く Q 行のうちの i 行目 (1 ≤ i ≤ Q) には，整数 S_i , T_i が空白を区切りとして書かれている．これは， i 番目の質問が，「建物 S_i, T_i の間を移動するのに必要な水筒の大きさの最小値は何か」であることを 表す．

標準出力に Q 行出力せよ．i 行目 (1 ≤ i ≤ Q) に，建物 S_i , T_i の間を移動するのに必要な水筒の大きさの 最小値を表す整数を出力せよ．ただし，移動が不可能な場合は，-1 を出力せよ．また，野原のマスを通ら ずに移動が行える場合は，0 を出力せよ．

• 1 ≤ H ≤ 2 000．
• 1 ≤ W ≤ 2 000.
• 2 ≤ P ≤ 200 000．
• 1 ≤ Q ≤ 200 000．
• 1 ≤ A_j ≤ H (1 ≤ j ≤ P) .
• 1 ≤ B_j ≤ W (1 ≤ j ≤ P) .
• (A_i, B_i) ≠ (A_j, B_j) (1 ≤ i < j ≤ P) .
• 1 ≤ S_i < T_i ≤ P (1 ≤ i ≤ Q) .

• H ≤ 200．
• W ≤ 200．
• P ≤ 200．

• P ≤ 5 000．
• Q = 1．

• P ≤ 5 000．
• Q ≤ 10 000．

追加の制限はない．