0659 - 誘拐 2 (Abduction 2)

ある晴天の日のこと，ある交差点で，誘拐事件が発生した．犯人は Anna と Bruno であり，二人は車に乗って誘拐現場から逃走したと考えられている．誘拐犯の車は未だ見つかっておらず，警察は今なお車の行方を追っている．

誘拐犯の車の走った市街地は，東西にのびる道路が H 本，南北にのびる道路が W 本走る碁盤目状の街である．2 つの隣接する交差点間の距離は，1 キロメートルである．

それぞれの道路について，人通りの多さを表す整数が与えられる．北から i 本目 (1 ≤ i ≤ H) の東西方向の道路の人通りの多さは A_i であり，西から j 本目 (1 ≤ j ≤ W) の南北方向の道路の人通りの多さは B_j である．これら H + W 個の値は互いに異なる．それぞれの道路について，道路の人通りの多さは，道路上のどの地点においても同じである．

また，警察による捜査の結果，誘拐犯は市街地で移動する際，次のような方法で移動をしていたことが 明らかとなった．

• 市街地の外や，道路ではない場所に出ることはない．
• 最初は，誘拐犯は，誘拐した交差点から移動可能な方向のうちどれか 1 つを選んで移動する．
• ある交差点に差し掛かったとき，今まで移動してきた道路よりも交わっている道路の方が人通りが多いときは，その交差点で曲がる．もし，2 方向どちらにも曲がることができる場合は，どちらを選んだ可能性もある．
• ある交差点に差し掛かったとき，今まで移動してきた道路の方が交わっている道路よりも人通りが多いときは，そのまま直進する．ただし，市街地の端におり直進できないときは，そこで移動を終了する．

誘拐現場の候補地として，Q 箇所の交差点が候補に挙がっている．Q 箇所の候補地は互いに異なる．警察は，調査チームの人数を決めるときの参考として，それぞれの誘拐現場の候補地に対し，誘拐事件がそこで発生したと仮定したとき，誘拐犯がその場所から最長で何キロメートル移動できるかを知りたい．

Q 個のクエリについて，与えられた誘拐現場の候補地から移動可能な経路の最長の長さを求めよ．

課題

市街地の道路の人通りの多さと，Q 箇所の誘拐現場の候補地が与えられたとき，それぞれの候補地から移動可能な経路の長さの最大値を求めるプログラムを作成せよ．

入力

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

• 1 行目には，3 個の整数 H, W, Q が空白を区切りとして書かれている．これは，市街地は東西方向にのびる H 本の道路と南北方向にのびる W 本の道路からなり，誘拐現場の候補地として Q 箇所が与えられることを表す．
• 2 行目には，H 個の整数 A₁, A₂, ..., A_H が空白を区切りとして書かれている．これは，北から i 本目 (1 ≤ i ≤ H) の東西方向の道路の人通りの多さが A_i であることを表す．
• 3 行目には，W 個の整数 B₁, B₂, ..., B_W が空白を区切りとして書かれている．これは，西から j 本目 (1 ≤ j ≤ W) の南北方向の道路の人通りの多さが B_j であることを表す．
• 続く Q 行のうちの k 行目 (1 ≤ k ≤ Q) には，2 個の整数 S_k, T_k が空白を区切りとして書かれている．これは，k 番目の誘拐現場の候補地が，北から S_k 本目の東西方向の道路と西から T_k 本目の南北方向の道路の交差点であることを表す．

出力

標準出力に Q 行出力せよ．k 行目 (1 ≤ k ≤ Q) には，k 番目の誘拐現場の候補地から移動を開始したときの移動可能な経路の長さの最大値を，キロメートル単位で出力せよ．

制限

すべての入力データは以下の条件を満たす．

• 2 ≤ H ≤ 50 000．
• 2 ≤ W ≤ 50 000．
• 1 ≤ Q ≤ 100．
• 1 ≤ A_i ≤ 1 000 000 000 (1 ≤ i ≤ H)．
• 1 ≤ B_j ≤ 1 000 000 000 (1 ≤ j ≤ W)．
• H + W 個の整数 A₁, A₂, ..., A_H, B₁, B₂, ..., B_W は互いに異なる．
• 1 ≤ S_k ≤ H (1 ≤ k ≤ Q)．
• 1 ≤ T_k ≤ W (1 ≤ k ≤ Q)．
• (S_k, T_k) ≠ (S_l, T_l) (1 ≤ k < l ≤ Q)．

小課題

この課題では小課題は全部で 5 個ある．各小課題の配点および追加の制限は以下の通りである．

小課題 1 [13 点]

• H ≤ 8．
• W ≤ 8．
• Q = 1．

小課題 2 [10 点]

• H ≤ 2 000．
• W ≤ 2 000．
• Q = 1．

小課題 3 [17 点]

• Q = 1．

小課題 4 [4 点]

• H ≤ 2 000．
• W ≤ 2 000．

小課題 5 [56 点]

追加の制限はない．

入出力例

入力例 1

3 3 5
3 2 6
1 4 5
1 1
1 2
2 2
3 1
3 3

出力例 1

4
5
4
4
2

例えば， 3 番目のクエリに関しては，次のように移動する場合が最長となる．

• 北から 2 本目の道路と西から 2 本目の道路の交差点から，東方向に 1 キロメートル移動する．
• 北から 2 本目の道路と西から 3 本目の道路の交差点からは，南もしくは北に移動可能であり，南方向に 1 キロメートル移動する．
• 北から 3 本目の道路と西から 3 本目の道路の交差点からは，西にのみ移動可能であり，西方向に 1 キロメートル移動する．
• 北から 3 本目の道路と西から 2 本目の道路の交差点からは，西にのみ移動可能であり，西方向に 1 キロメートル移動する．
• 北から 3 本目の道路と西から 1 本目の道路の交差点からは，もうどの方向にも移動することはできないので，ここで移動を終了する．

入力例 2

4 5 6
30 10 40 20
15 55 25 35 45
1 3
4 3
2 2
4 1
2 5
3 3

出力例 2

7
6
9
4
6
9