- 62

## 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

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

X(0) = 42424242

X(1) = 1443152643

X(2) = 717496960

X(3) = 654696633

So we are comparing horses of strengths

Input

**Line 1:**the number

`N`of classical horses, the number

`M`of congruential horses, the seed

`X`of the generator, space-separated

**the velocity**

`N`following lines:`Vi`and elegance

`Ei`of each classical horse, space-separated

Output

**Line 1:**the difference

`D`between the two closest strengths

Constraints

2 ≤

0 ≤

0 ≤

All values are integral.

`N`+`M`≤ 1000000 ≤

`N`,`M`0 ≤

`Vi`,`Ei`< 2^31`D`≥ 0All values are integral.

Example

Input

1 2 42424242 0 0

Output

1372193593

A higher resolution is required to access the IDE