Busy Beaver jest zbyt leniwy, by napisać ciekawą historię do tego zadania, więc podał po prostu formalną treść.

Zdefiniujmy $M$-ciąg jako ciąg dodatnich liczb całkowitych, z których każda mieści się w przedziale od $1$ do $M$ włącznie.

$M$-ciąg nazywamy $K$-dobrym, jeśli wartość bezwzględna różnicy między dowolną parą sąsiednich elementów wynosi co najwyżej $K$. Na przykład $[1, 2, 3, 5, 5, 3, 2, 1]$ jest $2$-dobry i $2024$-dobry, ale nie jest $1$-dobry. Przyjmujemy również, że $M$-ciągi o długości $0$ lub $1$ są $K$-dobre.

Mając dane dodatnie liczby całkowite $N$, $M$, $K$, $L$ oraz $M$-ciąg $a_1, \dots, a_N$ o długości $N$, znajdź maksymalną możliwą liczbę elementów w $M$-ciągu $b$, takim że:

• $b$ ma $a$ jako prefiks; oraz
• Każdy $K$-dobry podciąg $b$ ma co najwyżej $L$ elementów.

Przypomnijmy, że podciąg ciągu otrzymuje się poprzez usunięcie pewnych elementów (być może wszystkich lub żadnego) z ciągu, bez zmiany kolejności pozostałych elementów.

Wejście

Dostępnych jest wiele zestawów danych testowych. Pierwsza linia zawiera dodatnią liczbę całkowitą $T$ ($1 \le T \le 2 \cdot 10^5$), liczbę zestawów danych.

Pierwsza linia każdego zestawu danych zawiera cztery liczby całkowite $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$).

Druga linia zestawu danych zawiera $a_1, \dots, a_N$ ($1 \le a_i \le M$). Jeśli $N = 0$, linia ta jest pomijana.

Gwarantuje się, że każdy $K$-dobry podciąg $a$ ma co najwyżej $L$ elementów. Ponadto suma $N$ we wszystkich zestawach danych nie przekracza $4 \cdot 10^5$.

Wyjście

Dla każdego zestawu danych wypisz w jednej linii maksymalną liczbę elementów w $b$. Można wykazać, że przy ograniczeniach zadania maksimum zawsze istnieje i nie przekracza $9 \cdot 10^{18}$.

Podzadania

• ($5$ punktów) $M \le K + 1$.
• ($5$ punktów) $K = 0$.
• ($10$ punktów) $N = 0$.
• ($15$ punktów) $N = 1$.
• ($30$ punktów) Suma $N$, $M$, $K$ oraz $L$ we wszystkich zestawach danych nie przekracza $3000$.
• ($35$ punktów) Brak dodatkowych ograniczeń.

Przykład

Przykład 1

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

Wyjście 1

5
6
7

Uwagi

W pierwszym przykładowym zestawie danych jednym z możliwych $M$-ciągów $b$ jest $[1, 3, 2, 3, 1]$, którego $1$-dobre podciągi, takie jak $[3, 2, 3]$ oraz $[3, 2, 1]$, mają długość co najwyżej $L = 3$.

W drugim przykładowym zestawie danych jednym z możliwych $M$-ciągów $b$ jest $[1, 1, 5, 4, 2, 5]$, którego $2$-dobre podciągi, takie jak $[5, 4, 2]$ oraz $[1, 1, 2]$, mają długość co najwyżej $L = 3$.

W trzecim przykładowym zestawie danych można wykazać, że jedynym możliwym $b$ jest $b = a$.