← 返回题目列表

AtCoder · code_thanks_festival_14_quala_d

D. 月票

中文机器翻译题面 查看原题

問題文

你所在的铁路公司的线路上有一直线排列的 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