Thảo luậnSnackDown Online Pre-elimination round A - Consecutive Snakes

Mỗi năm có một cuộc diễu hành và binh lính là những con rắn đều đến sân vận động để diễu binh. Tuy nhiên chúng lại đứng không đúng vị trí. Toàn bộ cuộc diễu hành phải được nhìn thấy từ bục chính và các con rắn phải xếp thành một hàng. Nhưng những con rắn lính ấy rất lười biếng và chẳng chịu di chuyển cho nên bạn phải nói với chúng cách di chuyển đến vị trí sao cho giảm thiểu tối đa số bước di chuyển.

Coi toàn bộ dải đi diễu hành là một dòng số nguyên. Có N con rắn, mỗi con rắn là một đoạn thẳng chiều dài L. Con rắn thứ i bắt đầu ở đoạn [Si, Si + L]. Vị trí của các con rắn ban đầu có thể chồng lên nhau. Đoạn duy nhất của dòng có thể nhìn thấy từ bục là [A, B], và tất cả các con rắn đều di chuyển nên cần nhìn thấy tất cả chúng từ bục. Chúng cũng phải ở trong một dòng mà không có khoảng trống và các cặp liên tiếp nối nhau. Nói cách khác, chúng phải chiếm các đoạn [X, X + L], [X + L, X + 2*L], ... , [X + (N-1)*L, X + N*L], với X mà A ≤ X ≤ X + N*L ≤ B. Bạn được đảm bảo rằng dải nhìn thấy đủ dài để có thể chứa tất cả các con rắn.

Nếu con rắn ban đầu ở vị trí [X1, X1 + L] và cuối cùng ở vị trí [X2, X2 + L], thì con rắn này di chuyển một khoảng cách |X2 - X1|. Tổng khoảng cách di chuyển của tất cả các con rắn chỉ là tổng số giá trị như trên của mỗi con rắn. Bạn cần di chuyển theo cách đề đáp ứng tất cả các yêu cầu trên, cũng như giảm thiểu tối đa nhất tổng số khoảng cách di chuyển. Hãy in ra tổng số khoảng cách nhỏ nhất.

Dữ liệu vào

- Dòng đầu tiên của dữ liệu vào chứa số nguyên T – số test. Các test được miêu tả như sau:

- Dòng đầu tiên của mỗi test chứa 4 số nguyên N, L, A và B ở đó N là số con rắn, L là chiều dài của mỗi con rắn, [A, B] là đoạn mà nhìn thấy con rắn trong dải diễu hành.

- Dòng tiếp theo chứa N số nguyên, số nguyên thứ i là Si – thể hiện là con rắn thứ i ban đầu ở vị trí đoạn [Si, Si + L].

Dữ liệu ra

- Ở mỗi test, in ra một số nguyên trong một dòng: là giá trị nhỏ nhất của tổng khoảng cách theo yêu cầu.

Ràng buộc

- 1 ≤ T ≤ 10

- 1 ≤ N ≤ 105

- 1 ≤ Si ≤ 109

- 1 ≤ L ≤ 109

- 1 ≤ A ≤ B ≤ 109

- N * L ≤ B - A

Ví dụ

Input:

2
3 4 11 23
10 11 30
3 4 11 40
10 11 30

Output:

16
16

Giải thích

Trong test đầu tiên, ban đầu có 3 con rắn ở các đoạn [10, 14], [11, 15], và [30, 34]. Một phương án tối ưu là di chuyển con rắn đầu tiên ở [10, 14] đến [15, 19] và con rắn thứ ba ở [30, 34] đến [19, 23]. Sau đó, các con rắn sẽ tạo thành một cuộc diễu hành hợp lệ vì chúng sẽ bắt đầu từ [11, 15], [15, 19] và [19, 23]. Do đó không có bất kỳ khoảng trống nào giữa chúng và tất cả chúng đều có thể nhìn thấy được, bởi vì chúng đều nằm trong đoạn có thể nhìn thấy, đó là [11, 23].

Khoảng cách di chuyển của con rắn đầu tiên là | 15 - 10 | = 5, của con rắn thứ hai là | 11 - 11 | = 0 và của con rắn thứ ba là | 19 - 30 | = 11. Do đó tổng khoảng cách đi là 5 + 0 + 11 = 16. Đây là kết quả tốt nhất bạn có thể dạt được, và do đó câu trả lời là 16.

Trong test thứ hai, chỉ có dải nhìn thấy được tăng lên. Nhưng bạn có thể kiểm tra rằng cách sắp xếp như test đầu là tối ưu. Do đó đáp án là 16.