← 返回题目列表

Codeforces · 491/B

B. 纽约酒店

中文机器翻译题面 查看原题

将纽约想象成一个矩形网格,由 N 条从 1 到 N 编号的垂直大道和 M 条从 1 到 M 编号的水平街道组成。 C 个朋友住在位于某些街道交叉口的 C 个酒店。他们将在位于一些街道交叉口的 H 餐厅之一庆祝其中一位的生日。他们还希望其中一人前往餐厅时所走​​的最大距离尽可能短。帮助朋友选择最佳的庆祝餐厅。

假设相邻交叉路口之间的距离都相同等于一公里。

输入

第一行包含两个整数 N и M — 城市的大小 (1 ≤ N, M ≤ 109)。下一行中有一个整数 C (1 ≤ C ≤ 105) — 朋友入住的酒店数量。接下来的 C 行包含酒店的描述,每行由两个坐标 x 和 y 组成(1 ≤ x ≤ N,1 ≤ y ≤ M)。下一行包含一个整数 H — 餐馆数量 (1 ≤ H ≤ 105)。接下来的 H 行包含相同格式的餐馆描述。

同一十字路口附近可能有几家餐馆和酒店。

输出

在第一行输出最佳距离。在下一行中输出产生此最佳距离的餐厅的索引。如果有多种可能性,则允许输出其中任何一种。

示例

输入 #1

10 10
2
1 1
3 3
2
1 10
4 4

输出 #1

6
2