D - 定期券 Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

問題文

あなたの勤める鉄道会社の路線には一直線に並んだ N 個の駅があり、駅には 1 から N までの異なる整数の番号がついています。より具体的には、駅 1、駅 2、……、駅 N-1、駅 N の順で駅が並んでいて、隣り合う駅の間に線路が引かれています。

この路線では従来は複雑な運賃計算方法を使っていましたが、乗客から運賃に関する質問が絶えないので、運賃計算を簡単にするために 1 駅ぶん移動するごとに 100 円の運賃がかかるという単純な運賃計算を導入することにしました。たとえば、駅 2 から駅 6 へ行くのには 400 円かかります。

ただし、定期券を持っている場合には運賃計算の際に定期券も考慮する必要があります。駅 a から駅 b までの定期券を持っている場合、その間にある駅どうしで移動するぶんの運賃はかかりません。たとえば、駅 3 から駅 5 までの定期券を持っているとき

  • 駅 2 から駅 6 へ行くのには 200 円かかります。
    • 駅 2 から駅 3 への移動と、駅 5 から駅 6 への移動は定期券の圏外なのでそれぞれ 100 円がかかります。
    • 一方、駅 3 から駅 4、駅 4 から駅 5 への移動は定期券の圏内なので運賃はかかりません。
  • 駅 3 から駅 4 へ行くのには運賃はかかりません。
  • 駅 7 から駅 10 へ行くのには 300 円かかります。

さて、せっかく運賃計算方法を単純にしたのに、いまだ乗客からの運賃に関する質問は減る様子を見せません。あなたは、これぐらい単純なルールであれば、プログラムで質問に答えられるのではないかと考えました。「駅 a から駅 b までの定期券を持っている人が、駅 s から駅 t へ行くときにかかる運賃は何円か？」という形式の質問に答えるプログラムを作成してください。

入力

N Q
a_1 b_1 s_1 t_1
a_2 b_2 s_2 t_2
:
a_Q b_Q s_Q t_Q
  • 1 行目には、駅の数を表す整数 N (2 ≦ N ≦ 10^5) と、運賃に関する質問の数を表す整数 Q (1 ≦ Q ≦ 10^5) が書かれている。
  • 2 行目から Q 行にわたって、各行に運賃に関する質問の情報が書かれている。このうち i (1 ≦ i ≦ Q) 行目には i 番目の質問を表す 4 つの整数 a_i, b_i (1 ≦ a_i < b_i ≦ N), s_i, t_i (1 ≦ s_i < t_i ≦ N) が書かれている。これは i 番目の質問が「駅 a_i から駅 b_i までの定期券を持っている人が、駅 s_i から駅 t_i へ行くときにかかる運賃は何円か？」であることを表す。

出力

Q 行出力せよ。i (1 ≦ i ≦ Q) 行目に、i 番目の質問に対する答えを表す整数を出力せよ。

入力例1

10 3
3 5 2 6
3 5 3 4
3 5 7 10

出力例1

200
0
300

この入出力例は問題文中で説明されている例です。

入力例2

100000 5
30000 50000 12345 67890
50000 50001 50000 50002
1 100000 9384 99384
1 2 3 100000
48592 84911 58124 91852

出力例2

3554500
100
0
9999700
694100