#931 Retreat

Statement

Statement language

Every lost battle weakens and dissolves an army. The immediate task is to rally, and in rallying to recover order, courage, and confidence.

Carl von Clausewitz, On War, Book IV, Chapter 13

Sorry to greet you with such news as soon as you open the problem, but you have just lost an important battle. Only a fraction of the units you commanded have survived, and they are scattered, fleeing to save their own lives.

Unless you want your own life to become another price of defeat, you must rally the fleeing units and restore their formations to keep the front from collapsing.

To prevent enemy infiltration and further advances while holding key routes and positions, you must swiftly move the scattered units to designated assembly points in the rear and reserve units to important defensive positions. You want to minimize each unit's travel time so that you can regain control while giving the enemy as few opportunities as possible.

There are $N$ points in this area that can serve as departure points or destinations, numbered $1$ through $N$ . Every pair of distinct points is connected by a direct two-way road. The time needed to travel directly from point $i$ to point $j$ is

Input

The first line contains integers $N$ , $C$ , and $Q$ , separated by spaces.

Each of the next $Q$ lines contains the departure point and destination $S$ , $T$ of a movement plan, separated by a space.

Output

For each movement plan, print the minimum travel time on its own line, in the order the plans are given.

Constraints

$2\le N\le 50\,000$
$0\le C\le 50\,000$
$1 \leq Q \leq$

Samples

Sample 1

Input

0 2
3
5

Output

2
3

For the first plan in example 1, traveling directly from point $12$ to point $3$ takes $2$ units of time, which is minimal.

For the second plan in example 1, traveling directly from point $11$ to point $5$ takes $3$ units of time, which is minimal.

Note

This is the original version of BCD 13 Ex.

If you have solved this problem, try BCD 13 Ex as well.