D. 繁星坠海
time limit per test
5 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

辉夜姬正在乘坐飞船穿越时空寻找彩叶。

辉夜姬的飞船可以停靠在 $$$n$$$ 个时间点。辉夜姬的飞船有 $$$m$$$ 条航线，每条航线可以用四个整数 $$$x,l,r,d$$$ 描述，航线的类型有两种。

  • 类型 $$$1$$$：此类航线从一个时刻 $$$x$$$ 出发，可以前往在区间 $$$[l,r]$$$ 的任意一个时刻。
  • 类型 $$$2$$$：此类航线可以从位于区间 $$$[l,r]$$$ 的时刻出发，前往时刻 $$$x$$$。

每沿着一条航线穿越一次时空，辉夜姬需要耗费一定的燃料。耗费的燃料由基础燃料 $$$d$$$ 和附加燃油两部分组成。如果辉夜姬通过某条航线从 $$$x$$$ 时刻前往 $$$y$$$ 时刻，那么她必须消耗 $$$d + |x - y|$$$ 的燃料。

辉夜姬现在已经启程，出于安全考虑，她不会对 $$$m$$$ 条航线进行更改。辉夜姬在时刻 $$$s$$$，彩叶在时刻 $$$t$$$。辉夜姬的飞船燃料有限，因此她希望使用最少的燃料到达彩叶身边。

请你帮帮辉夜姬！

请注意，所有航线都是单向的。

Input

第一行三个整数 $$$n,m,s,t$$$，表示时刻的数量，辉夜姬所在的时刻和彩叶的时刻。

接下来 $$$m$$$ 行，第 $$$i$$$ 行两个整数 $$$op_i,l_i,r_i,x_i,d_i$$$ 描述第 $$$i$$$ 条航线。

  • 如果 $$$op_i = 1$$$，说明该条航线为类型 $$$1$$$ 的航线。
  • 如果 $$$op_i = 2$$$，说明该条航线为类型 $$$2$$$ 的航线。
Output

一行一个整数，表示消耗的最少燃料。如果无论如何辉夜姬都到达不了彩叶所在的时间点，请输出 $$$-1$$$。

Examples
Input
5 5 4 1
1 3 3 2 6
1 1 5 5 1
2 2 4 1 1
2 2 3 5 9
1 1 5 4 1
Output
4
Input
5 5 3 1
1 1 3 1 10
2 3 4 4 1
1 2 4 1 7
1 3 5 4 10
2 1 5 4 6
Output
-1
Input
5 5 5 2
2 1 5 3 9
2 1 4 2 10
2 2 5 1 6
1 2 3 2 1
2 3 5 1 9
Output
21
Note

对于所有测试点，$$$1\leq m \leq 2\times 10^5, 1\leq n \leq 5 \times 10 ^ 5, 1\leq l_i \leq r_i \leq n, 1 \leq x_i \leq n, 1 \leq d_i \leq 1 \times 10 ^ {12}$$$。