Meeting on the Number Line via Teleporters

dXqwq and Haitang start at two different points A and B on the number line. They want to meet but cannot walk; they can only move using teleporters.

There are N teleporters. The i-th teleporter is located at position \(c_i\) and has frequency \(f_i\). However, due to some restrictions, only teleporters whose frequency lies within the range \([L,R]\) can be used.

The effect of using a teleporter is to reflect one’s current position about the teleporter’s position. Formally, if a person is at position \(x_1\) and uses a teleporter at \(c_i\), he is transported to position \(x_2\) satisfying \[ \frac{x_1+x_2}{2} = c_i. \]

At each move, dXqwq and Haitang simultaneously choose (possibly different) usable teleporters \(p\) and \(q\) (with frequencies in \([L,R]\)), and are teleported to \(2c_p-A\) and \(2c_q-B\) respectively. This move incurs a fatigue value of \(|f_p - f_q|\). They can repeat such moves arbitrarily until they meet (i.e. their positions become equal). The total fatigue value is defined as the maximum fatigue encountered over all moves.

The problem is: given \(Q\) queries, each specifying a frequency range \([L,R]\), determine the minimum possible total fatigue value that can be achieved so that dXqwq and Haitang can meet using only teleporters within that frequency range. If it is impossible for them to meet using the allowed teleporters, output −1.

Note: In all formulas, use LaTeX notation.

inputFormat

The first line contains four integers \(A\), \(B\), \(N\) and \(Q\) — the starting positions of dXqwq and Haitang, the number of teleporters, and the number of queries, respectively.

The next \(N\) lines each contain two integers \(c_i\) and \(f_i\) — the position and frequency of the \(i\)-th teleporter.

Then \(Q\) lines follow, each containing two integers \(L\) and \(R\) which specify a query: only teleporters with frequencies in the range \([L,R]\) are available.

outputFormat

For each query, output a single line containing the minimum possible total fatigue value (the minimum possible maximum \(|f_p - f_q|\) among moves) needed for dXqwq and Haitang to meet. If it is impossible for them to meet using the allowed teleporters, output −1.

sample

2 4 3 3
1 5
3 3
6 4
3 5
3 4
4 5

0
1
1