绑架 2

题号：NC53230
时间限制：C/C++/Rust/Pascal 2秒，其他语言4秒
空间限制：C/C++/Rust/Pascal 512 M，其他语言1024 M
64bit IO Format: %lld

题目描述

题目译自 JOISC 2017 Day4 T1「誘拐 2 / Abduction 2」

某地的道路网可视为由H条东西向道路与W条南北向道路构成的网格，相邻的两条平行道路之间的距离为 $1 \: \textrm{km}$ 。东西向道路从北到南依次编号为 $1 \ldots H$ ，南北向道路从西到东依次编号为 $1 \ldots W$ 。
东西向道路和南北向道路相交形成路口，规定x号南北向街道和y号东西向街道形成的路口的坐标是(x,y)。
每条道路有一个车流指数。i号东西向道路 $(1 \le i \le H)$ 的车流指数为 $A_{ \; \!i}$ ，j号南北向道路 $(1 \le j \le W)$ 的车流指数为 $B_j$ 。所有道路的车流指数互不相同。
给出Q个互不相同的坐标 $(S_1,T_1),(S_2,T_2), \ldots ,(S_Q,T_Q)$ 作为备选起点。对于每个备选起点，请计算：如果按照下述规则移动，最多可以移动多远。

移动开始时，可以任意选择方向。
当到达十字路口时：

如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」小，就转弯。你可以选择左转还是右转。但如果你在城市边界上，可能只能左转/右转。
如果「直行方向的道路的车流指数」比「该十字路口的另一条道路的车流指数」大，就直行。但如果前面没路（比如到了城市边界），就只能停在此处。不能掉头。

输入描述:

第一行有三个整数H,W,Q，用空格分隔。
第二行有H个整数，用空格分隔。
第三行有W个整数，用空格分隔。
在接下来的Q行中，第k行有两个用空格分隔的整数。

输出描述:

输出共Q行，第i行有一个整数，表示以为起点，按照所给规则移动，最多可以移动多远。

示例1

输入

复制

输出

复制

说明

例如，对于，最多可以移动。
从(2,2)向东移动，到达(2,3)。
在(2,3)可以左转或右转。在(2,3)左转，向南移动，到达(3,3)。
在(3,3)只能右转。在(3,3)右转，向西移动，到达(3,2)。
在(3,2)只能直行。向西移动，到达(3,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

输出

复制

备注:

。
保证所有道路的车流指数互不相同，所有的备选起点互不相同。

CC-BY-SA，感谢LOJ分享，译文来自 https://loj.ac/problem/2399