Busy Beaver quá lười để viết một câu chuyện thú vị cho bài toán này, vì vậy anh ấy chỉ đưa cho bạn một phát biểu hình thức.

Định nghĩa một $M$-dãy là một dãy các số nguyên dương, mỗi số nằm trong khoảng từ $1$ đến $M$ (bao gồm cả $1$ và $M$).

Một $M$-dãy được gọi là $K$-tốt nếu hiệu tuyệt đối giữa bất kỳ cặp phần tử liền kề nào không vượt quá $K$. Ví dụ, $[1, 2, 3, 5, 5, 3, 2, 1]$ là $2$-tốt và $2024$-tốt, nhưng không phải là $1$-tốt. Chúng ta cũng coi các $M$-dãy có độ dài $0$ hoặc $1$ là $K$-tốt.

Cho các số nguyên dương $N, M, K, L$ và một $M$-dãy $a_1, \dots, a_N$ có độ dài $N$, hãy tìm số lượng phần tử lớn nhất có thể của một $M$-dãy $b$ sao cho:

• $b$ có $a$ là tiền tố; và
• Mọi dãy con $K$-tốt của $b$ có tối đa $L$ phần tử.

Nhắc lại rằng một dãy con của một dãy được tạo ra bằng cách xóa đi một số phần tử (có thể là tất cả hoặc không xóa phần tử nào) từ dãy đó mà không làm thay đổi thứ tự của các phần tử còn lại.

Dữ liệu vào

Có nhiều bộ dữ liệu kiểm thử. Dòng đầu tiên chứa một số nguyên dương $T$ ($1 \le T \le 2 \cdot 10^5$), số lượng bộ dữ liệu.

Dòng đầu tiên của mỗi bộ dữ liệu chứa bốn số nguyên $N, M, K, L$ ($0 \le N \le 2 \cdot 10^5$, $1 \le M \le 10^9$, $0 \le K \le 10^9$, $1 \le L \le 10^9$).

Dòng thứ hai của mỗi bộ dữ liệu chứa $a_1, \dots, a_N$ ($1 \le a_i \le M$). Nếu $N = 0$, dòng này sẽ bị bỏ qua.

Đảm bảo rằng mọi dãy con $K$-tốt của $a$ đều có tối đa $L$ phần tử. Hơn nữa, tổng $N$ trên tất cả các bộ dữ liệu không vượt quá $4 \cdot 10^5$.

Dữ liệu ra

Với mỗi bộ dữ liệu, in ra trên một dòng số lượng phần tử lớn nhất của $b$. Có thể chứng minh rằng với các ràng buộc của bài toán, giá trị lớn nhất luôn tồn tại và không vượt quá $9 \cdot 10^{18}$.

Nhiệm vụ con

• ($5$ điểm) $M \le K + 1$.
• ($5$ điểm) $K = 0$.
• ($10$ điểm) $N = 0$.
• ($15$ điểm) $N = 1$.
• ($30$ điểm) Tổng của mỗi giá trị $N, M, K$ và $L$ trên tất cả các bộ dữ liệu không vượt quá $3000$.
• ($35$ điểm) Không có ràng buộc bổ sung.

Ví dụ

Dữ liệu vào 1

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

Dữ liệu ra 1

5
6
7

Ghi chú

Trong bộ dữ liệu ví dụ đầu tiên, một $M$-dãy $b$ có thể là $[1, 3, 2, 3, 1]$, các dãy con $1$-tốt của nó, chẳng hạn như $[3, 2, 3]$ và $[3, 2, 1]$, đều có độ dài tối đa là $L = 3$.

Trong bộ dữ liệu ví dụ thứ hai, một $M$-dãy $b$ có thể là $[1, 1, 5, 4, 2, 5]$, các dãy con $2$-tốt của nó, chẳng hạn như $[5, 4, 2]$ và $[1, 1, 2]$, đều có độ dài tối đa là $L = 3$.

Trong bộ dữ liệu ví dụ thứ ba, có thể chứng minh rằng $b$ duy nhất có thể là $b = a$.