Problem Description

Your railway company's route has $N$ stations arranged in a straight line, numbered from $1$ to $N$. More specifically, stations are arranged in the order of station $1$, station $2$, ..., station $N-1$, station $N$, with tracks connecting adjacent stations.

The route used to have a complex fare calculation method, but due to constant inquiries about fares from passengers, it was decided to simplify the fare calculation by introducing a flat rate of $100$ yen for moving one station. For example, traveling from station $2$ to station $6$ costs $400$ yen.

However, if you have a commuter pass, the fare calculation must also consider the commuter pass. If you have a commuter pass from station $a$ to station $b$, the fare for traveling between any stations within this range is free. For example, if you have a commuter pass from station $3$ to station $5$:

• Traveling from station $2$ to station $6$ costs $200$ yen.
• Moving from station $2$ to station $3$ and from station $5$ to station $6$ are outside the commuter pass range, so each costs $100$ yen.
• On the other hand, moving from station $3$ to station $4$ and from station $4$ to station $5$ are within the commuter pass range, so they are free.
• Traveling from station $3$ to station $4$ is free.
• Traveling from station $7$ to station $10$ costs $300$ yen.

Despite simplifying the fare calculation method, inquiries about fares from passengers are still not decreasing. You thought that such simple rules could be answered by a program. Create a program that answers the question, "How much fare does a person with a commuter pass from station $a$ to station $b$ pay when traveling from station $s$ to station $t$?"

Input Format

$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$

• The first line contains an integer $N$ ($2 ≦ N ≦ 10^5$), representing the number of stations, and an integer $Q$ ($1 ≦ Q ≦ 10^5$), representing the number of fare inquiries.
• The next $Q$ lines contain the information for each fare inquiry. The $i$-th line ($1 ≦ i ≦ Q$) contains four integers $a_i$, $b_i$ ($1 ≦ a_i < b_i ≦ N$), $s_i$, $t_i$ ($1 ≦ s_i < t_i ≦ N$), representing the $i$-th inquiry, which asks "How much fare does a person with a commuter pass from station $a_i$ to station $b_i$ pay when traveling from station $s_i$ to station $t_i$?"

Output Format

Output $Q$ lines. The $i$-th line ($1 ≦ i ≦ Q$) should contain an integer representing the answer to the $i$-th inquiry.

Sample Input and Output

Sample Input #1

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

Sample Output #1

200
0
300

Sample Input #2

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

Sample Output #2

3554500
100
0
9999700
694100

Notes/Hints

Sample Explanation 1

This input/output example is explained in the problem statement.

见题面 Input 部分

见题面 Output 部分