시간 제한메모리 제한제출정답맞힌 사람정답 비율
1.5 초 512 MB175360945439.790%

## 문제

Given two sets P and Q of finitely many points in the plane, a closest pair of P and Q is a pair (p, q) of points p ∈ P and q ∈ Q such that the distance between p and q is the minimum among all pairs (p′, q′) with p′ ∈ P and q′ ∈ Q.

Specifically, in this problem, by the distance between two points a and b in the plane, we mean:

d(a, b) = |xa - xb| + |ya - yb|

where xa and ya denote the x- and y-coordinates of point a, and xb and yb denote the x- and y-coordinates of point b. Then, a pair (p, q) with p ∈ P and q ∈ Q is a closest pair of P and Q if and only if the following holds:

d(p, q) = min{ d(p′, q′) | p′ ∈ P and q′ ∈ Q}

Given two sets P and Q, write a program that computes the distance between a closest pair of P and Q and the number of distinct closest pairs of P and Q.

Note that you can assume the following on the input points in P and Q:

1. All the points in P lie on the horizontal line y = c1 while all the points in Q lie on the horizontal line y = c2 for some integers c1 and c2.
2. No two input points in P have the same coordinates; no two input points in Q have the same coordinates.

## 입력

Your program is to read from standard input. The input consists of four lines. The first line contains two integers, n (1 ≤ n ≤ 500,000) and m (1 ≤ m ≤ 500,000), where n is the number of points in set P and m is the number of points in set Q. In the second line, two integers c1 and c2 (-108 ≤ c1, c2 ≤ 108) are given in order, separated by a single space. In the third line, n distinct integers between -108 and 108, inclusively, are given, separated by a single space, that are the x-coordinates of the points in set P, while their y- coordinates are all the same as c1. In the fourth line, m distinct integers between -108 and 108, inclusively, are given, separated by a single space, that are the x-coordinates of the points in set Q, while their y- coordinates are all the same as c2.

## 출력

Your program is to write to standard output. Print exactly one line for the input. The line should contain two integers, separated by a single space, that represent the distance between a closest pair of P and Q and the number of closest pairs of P and Q in this order.

## 예제 입력 1

3 4
1 -3
3 0 6
-2 5 4 2


## 예제 출력 1

5 3


## 예제 입력 2

5 5
1 2
-4 -10 -2 0 -1
3 18 0 1 5


## 예제 출력 2

1 1


## 출처

• 잘못된 데이터를 찾은 사람: jh05013
• 데이터를 만든 사람: koosaga
• 데이터를 추가한 사람: mhkim4886