問題文

ある都市には、駅 $1$ から駅 $N$ までの $N$ 個の駅が時計回りの円環状に並んでいる鉄道路線があります。

この路線には、以下の $2$ 種類の列車の運行ルートが存在します。

• 各駅停車：

  駅 $i$ ($1 \leq i \leq N-1$) から駅 $i+1$ へ移動できます。また、駅 $N$ からは駅 $1$ へ移動できます。
  いずれの区間も時計回りの一方通行であり、$1$ 駅進むのにコストが $1$ かかります。

• 特急列車：

  駅 $S$ から駅 $T$ への直通運行（一方通行）が $1$ 本だけあります。
  駅 $S$ から駅 $T$ へ直接移動することができ、この移動にはコストが $C$ かかります。

各列車の運行ルートは、必要に応じて何度でも利用できます。

列車を乗り継いで移動するとき、移動全体の合計コストは、利用した各移動のコストの総和となります。

$Q$ 個のクエリが与えられます。

$j$ 番目 ($1 \leq j \leq Q$) のクエリでは、出発駅 $U_j$ と目的駅 $V_j$ が与えられるので、駅 $U_j$ から駅 $V_j$ へ移動するために必要な最小の合計コストを求めてください。

なお、$U_j=V_j$ の場合は一度も移動する必要がないため、コストは $0$ とします。

入力

入力は以下の形式で標準入力から与えられます。

$N$ $Q$ $S$ $T$ $C$
$U_1$ $V_1$
$U_2$ $V_2$
$\vdots$
$U_Q$ $V_Q$

出力

$Q$ 行出力してください。

$j$ 行目 ($1 \leq j \leq Q$) には、$j$ 番目のクエリに対する最小の合計コストを出力してください。

最後に改行してください。

制約

• $3 \leq N \leq 10^9$
• $1 \leq S,T \leq N$
• $S \neq T$
• $1 \leq C \leq 10^9$
• $1 \leq Q \leq 2 \times 10^5$
• $1 \leq U_j,V_j \leq N$
• 入力はすべて整数

サンプル

10 6 2 7 2
1 5
2 7
7 2
4 4
9 3
1 8

4
2
5
0
4
4

12 6 10 3 1
10 3
11 4
3 10
1 8
6 2
12 12

1
5
7
7
8
0

8 5 3 6 100
1 5
3 6
6 3
8 2
4 4

4
3
5
2
0