Practice Coding with the exercise "Horse-hyperracing Hyperduals"

Statement

Goal

The Casablanca hyperduals are a great success. Such a huge hit that hamburger-heaving horse hoards were heard heading for the harbor, hampering heavy hearses from herding horny hens hither, and also helping hinder the hyper-hullabaloo hovering around the hippodrome. And registering to compete, obviously.

In addition to the regular horses whose velocity and elegance are directly provided in input, a waitlist of new applicants is provided in compressed form. You are provided with the seed to a linear congruential generator, whose even terms (starting at 0) represent the new horses' velocity, and whose odd terms represent their elegance. The LCG works as follows:

X(0) = X, the seed provided in input
X(n+1) = 1103515245 * X(n) + 12345 [mod 2^31]

As before, given a horse pair with strengths (V1,E1) and (V2,E2), the race is assumed to be as interesting as abs(V2-V1)+abs(E2-E1) is small.

Write a program which, using a given number of strengths, identifies the two closest strengths and shows their difference with an integer.

(This is a harder version of community puzzle “Horse-racing Hyperduals”. You may want to solve that problem first.)

Example

You are given a classical horse of strength (0,0), and two congruential horses seeded by 42424242. The congruential sequence is thus:
X(0) = 42424242
X(1) = 1443152643
X(2) = 717496960
X(3) = 654696633

So we are comparing horses of strengths (0,0), (42424242,1443152643) and (717496960,654696633). Interestingness of a race between the first and second horse is 1485576885; the first and third 1372193593; the second and third 1463528728. Therefore the most interesting race is between first and third, and you should output 1372193593.

Input

Line 1: the number N of classical horses, the number M of congruential horses, the seed X of the generator, space-separated
N following lines: the velocity Vi and elegance Ei of each classical horse, space-separated

Output

Line 1: the difference D between the two closest strengths

Constraints

2 ≤ N+M ≤ 100000
0 ≤ N, M
0 ≤ Vi,Ei < 2^31
D ≥ 0
All values are integral.

Example

Input

1 2 42424242
0 0

Output

1372193593

Solve it

A higher resolution is required to access the IDE