400402: GYM100162 I Editor 2

Vasya is pressing the keys on the keyboard reluctantly, squeezing out his ideas on the classical epos depicted in Homer's Odysseus... How can he explain to his literature teacher that he isn't going to become a writer? In fact, he is going to become a programmer. So, he would take great pleasure in writing a program, but none — in writing a composition.

As Vasya was fishing for a sentence in the dark pond of his imagination, he suddenly wondered: what is the least number of times he should push a key to shift the cursor from one position to another one?

Let's describe his question more formally: to type a text, Vasya is using the text editor. He has already written n lines, the i-th line contains a_i characters (including spaces). If some line contains k characters, then this line overall contains (k + 1) positions where the cursor can stand: before some character or after all characters (at the end of the line). Thus, the cursor's position is determined by a pair of integers (r, c), where r is the number of the line and c is the cursor's position in the line (the positions are indexed starting from one from the beginning of the line).

Vasya doesn't use the mouse to move the cursor. He uses keys "Up", "Down", "Right" and "Left". When he pushes each of these keys, the cursor shifts in the needed direction. Let's assume that before the corresponding key is pressed, the cursor was located in the position (r, c), then Vasya pushed key:

• "Up": if the cursor was located in the first line (r = 1), then it does not move. Otherwise, it moves to the previous line (with number r - 1), to the same position. However, if the previous line was too short, that is, the cursor couldn't occupy position c there, the cursor moves to the last position of the line with number r - 1;
• "Down": if the cursor was located in the last line (r = n), then it does not move. Otherwise, it moves to the next line (with number r + 1), to the same position. However, if the next line was too short, that is, the cursor couldn't occupy position c there, the cursor moves to the last position of the line with number r + 1;
• "Right": if the cursor can move to the right in this line (c < a_r + 1), then it moves to the right (to position c + 1). Otherwise, it is located at the end of the line. If the current line is the last one (r = n), the cursor doesn't move anywhere when Vasya presses the "Right" key. Otherwise, it moves to the leftmost position in the next line (with number r + 1).
• "Left": if the cursor can move to the left in this line (c > 1), then it moves to the left (to position c - 1). Otherwise, it is located at the beginning of the line. If the current line is the first one (r = 1), the cursor doesn't move anywhere when Vasya presses the "Left" key. Otherwise, it moves to the rightmost position in the previous line (with number r - 1).

You've got the number of lines in the text file and the number of characters written in each line of this file. Also you are given m queries. For each query, find the least number of times Vasya should push the keys described above to move the cursor from position (r₁, c₁) to position (r₂, c₂).

The input contains several test cases. Each test case starts with a line containing two integers n and m (1 ≤ n ≤ 10⁶, 1 ≤ m ≤ 10). The second line contains n integers a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹), separated by single spaces. Each of the following m lines contains four integers r₁, c₁, r₂, c₂ (1 ≤ r₁, r₂ ≤ n, 1 ≤ c₁ ≤ a_r1 + 1, 1 ≤ c₂ ≤ a_r2 + 1).

For each test case, display the case number followed by the answers to the queries. For each query, display the minimum number of times Vasya should press a key to move the cursor from position (r₁, c₁) to position (r₂, c₂).

4 1
2 1 6 4
3 5 4 2
5 2
3 5 4 3 6
2 1 5 6
1 1 5 7

Case 1: 3
Case 2: 7 9