You are a technician for MRIMRI (Maged & Ray's Installation for Magnetic Resonance Imaging), tasked with travelling to a hospital and fixing their faulty MRI machine.

The MRI machine can be calibrated to one of ~n~ stable resonance frequencies ~f_1 < f_2 < \dots < f_n~. It can only ever be calibrated to one of these frequencies, or the machine will explode. The machine in the hospital is currently operating at frequency ~s~, but you want to recalibrate it to frequency ~t~ in order to make it operational for hospital use. ~s~ and ~t~ are among the stable frequencies.

You may manually recalibrate the MRI machine. If the device is currently at stable frequency ~f_i~, you may calibrate it to any other stable frequency ~f_j~ with required cost ~|f_i-f_j|~.

In addition to this, you have ~m~ calibration modules that can be used any number of times to make certain calibrations at different costs. Each module is one of two kinds:

Type 1 - Compressor. A module is described by ~L, R, Y, C~. If the device's current frequency ~f_i~ satisfies ~L \leq f_i \leq R~, you may recalibrate it to ~Y~ at cost ~C~. It is guaranteed that ~Y~ is among the stable frequencies.

Type 2 - Expander. A module is described by ~X, L, R, C~. If the device's current frequency is exactly ~f_i=X~, you may recalibrate it to any ~L \leq f_j \leq R~ at cost ~C~. It is guaranteed that ~X~ is among the stable frequencies, and you can only pick targets among the stable frequencies.

Find the minimum total cost to successfully recalibrate the MRI machine to frequency ~t~.

Input

The first line contains two integers ~n, m~ (~1 \leq n,m \leq 10^5~), the number of stable frequencies and the number of available calibration modules.

The next line contains ~n~ space-separated integers ~f_1,f_2,\dots,f_n~ (~0 \leq f_i \leq 10^9~), the value of each of the stable frequencies. It is guaranteed that each stable frequency is distinct, and it is guaranteed ~f_1 < f_2 < \dots < f_n~.

The next line contains two integers ~s,t~ (~s,t\in \{f_1,f_2,\dots,f_n\}~), the initial frequency of the MRI machine and the desired end frequency.

The next ~m~ lines each detail one of the calibration modules. Each line contains ~5~ space-separated integers. The first is ~0~ for compressor-type modules or ~1~ for expander-type modules. Thus, the lines are one of the two formats:

• 0 L R Y C (~0 \leq C \leq 10^9~, ~0 \leq L \leq R \leq 10^9~, ~Y\in\{f_1,f_2,\dots,f_n\}~)
• 1 X L R C (~0 \leq C \leq 10^9~, ~0 \leq L \leq R \leq 10^9~, ~X\in\{f_1,f_2,\dots,f_n\}~)

Output

Output the minimum total cost to recalibrate the MRI machine from starting frequency ~s~ to desired frequency ~t~ using any sequence of the operations above.

Example

Input 1

5 1
10 20 30 50 80
10 80
0 15 35 80 7

Output 1

17

The machine starts at frequency ~10~. The only module is a compressor that can be used from any stable frequency in ~[15,35]~, sending the machine directly to ~80~ for cost ~7~.

As a baseline, you could manually recalibrate directly to ~80~ for a cost of ~|80-10|=70~. However, you could use the compressor to achieve this at a cheaper cost. The stable frequencies within the range are ~20~ and ~30~. You can manually recalibrate to ~20~ at cost ~|20-10|=10~, and then use the compressor to recalibrate directly to ~80~, which is the target frequency, at cost ~7~. Thus the total minimum cost is ~17~.

Input 2

8 3
3 8 14 21 34 55 56 67
3 56
1 3 10 30 4
0 13 15 55 2
0 20 40 55 20

Output 2

7

The first module is an expander, taking frequency ~3~ to any stable frequency in ~[10,30]~ for cost ~4~. The possible destinations are ~14,21~.

The second module is a compressor, taking any stable frequency in ~[13,15]~ to ~55~ for cost ~2~. This module can thus only be used from stable frequency ~14~.

The third module is a compressor, taking any stable frequency in ~[20,40]~ to ~55~ for cost ~20~. This module can thus only be used from stable frequencies ~21~ and ~34~.

The optimal sequence is as follows: starting from ~3~, use the expander to recalibrate the machine to ~14~ at cost ~4~. Then, use the second compressor to recalibrate the machine to ~55~ at cost ~2~. Then manually recalibrate the machine from ~55~ to ~56~ at cost ~1~, reaching the target frequency for total cost ~7~.

Input 3

6 2
10 20 30 50 80 82
50 80
0 15 25 82 2
1 50 18 22 4

Output 3

8

The optimal sequence is taking the second module (expander) from ~50~ to ~20~ at cost ~4~, then taking the first module (compressor) from ~20~ to ~82~ at cost ~2~. Then, manually recalibrate from ~82~ to ~80~ at cost ~2~.