#931 撤退

题面

题面语言

每一场败仗都会削弱军队并使其瓦解。当务之急是重新集结，并在集结中恢复秩序、勇气和信心。

卡尔·冯·克劳塞维茨，《战争论》第四篇第 13 章

很抱歉，在你刚打开题目时就告诉你这个消息：你刚刚输掉了一场重要的战斗。你指挥的部队只有部分士兵幸存下来，他们四散奔逃，只顾保住自己的性命。

如果你不想连自己的性命也成为战败的代价，就必须收拢溃败的部队，整顿阵列，阻止战线崩溃。

为了阻止敌军渗透和进一步推进，并维持主要通道和据点，你需要迅速将战败后散落的部队调往后方指定的集结地点，将预备队调往主要防御地点。你希望尽量缩短各支部队移动所需的时间，不给敌人更多机会，并挽回局势。

这个地区有 $N$ 个可以作为移动起点或终点的地点，编号为 $1$ 到 $N$ 。任意两个不同地点之间都有一条可以直接通行的双向道路。从地点 $i$ 直接移动到地点 $j$ 所需的时间如下。

\big((i+j)\bmod N\big)+C

其中， $C$ 是非负整数， $x\bmod N$ 表示 $x$ 除以 $N$ 的余数。

移动时可以经过其他地点。沿一条路径移动所需的时间，等于经过这条路径上的各条道路所需时间之和。

为了重新部署部队，你准备评估 $Q$ 个移动计划。每个计划给出部队当前所在的地点 $S$ 和目的地 $T$ 。对于每个计划，请求出从地点 $S$ 移动到地点 $T$ 所需的最短时间。

第一行包含整数 $N$ 、 $C$ 和 $Q$ ，以空格分隔。

接下来 $Q$ 行，每行包含一个移动计划的起点编号 $S$ 和终点编号 $T$ ，以空格分隔。

按照给定顺序输出每个移动计划的最短移动时间，每个答案占一行。

样例 1

样例输入

0 2
3
5

样例输出

2
3

在样例一的第一个计划中，从地点 $12$ 直接移动到地点 $3$ ，所需时间为 $2$ ，这是最短时间。

在样例一的第二个计划中，从地点 $11$ 直接移动到地点 $5$ ，所需时间为 $3$ ，这是最短时间。

本题是 BCD 13 Ex 的原始版本。

如果你已经解决了本题，不妨也挑战一下 BCD 13 Ex。