Busy Beaver est trop paresseux pour écrire une histoire intéressante pour ce problème, il vous a donc simplement donné un énoncé formel.

Définissons une $M$-séquence comme une séquence d'entiers positifs, chacun compris entre $1$ et $M$ inclus.

Une $M$-séquence est dite $K$-bonne si la différence absolue entre toute paire d'éléments adjacents est au plus $K$. Par exemple, $[1, 2, 3, 5, 5, 3, 2, 1]$ est $2$-bonne et $2024$-bonne, mais pas $1$-bonne. Nous considérons également les $M$-séquences de longueur $0$ ou $1$ comme étant $K$-bonnes.

Étant donné des entiers positifs $N$, $M$, $K$, $L$, et une $M$-séquence $a_1, \dots, a_N$ de longueur $N$, trouvez le nombre maximum possible d'éléments dans une $M$-séquence $b$, telle que :

• $b$ a $a$ comme préfixe ; et
• Chaque sous-séquence $K$-bonne de $b$ possède au plus $L$ éléments.

Rappelons qu'une sous-séquence d'une séquence est obtenue en supprimant certains éléments (éventuellement tous ou aucun) d'une séquence, sans réordonner les éléments restants.

Entrée

Il y a plusieurs cas de test. La première ligne contient un entier positif $T$ ($1 \le T \le 2 \cdot 10^5$), le nombre de cas de test.

La première ligne de chaque cas de test contient quatre entiers $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$).

La deuxième ligne d'un cas de test contient $a_1, \dots, a_N$ ($1 \le a_i \le M$). Si $N = 0$, alors cette ligne est ignorée.

Il est garanti que chaque sous-séquence $K$-bonne de $a$ possède au plus $L$ éléments. De plus, la somme de $N$ sur tous les cas de test ne dépasse pas $4 \cdot 10^5$.

Sortie

Pour chaque cas de test, affichez une ligne contenant le nombre maximum d'éléments dans $b$. Il peut être démontré que sous les contraintes du problème, le maximum existe toujours et ne dépasse pas $9 \cdot 10^{18}$.

Sous-tâches

• ($5$ points) $M \le K + 1$.
• ($5$ points) $K = 0$.
• ($10$ points) $N = 0$.
• ($15$ points) $N = 1$.
• ($30$ points) La somme de chacun des $N$, $M$, $K$ et $L$ sur tous les cas de test ne dépasse pas $3000$.
• ($35$ points) Aucune contrainte supplémentaire.

Exemples

Entrée 1

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

Sortie 1

5
6
7

Remarque

Dans le premier cas de test, une $M$-séquence $b$ possible est $[1, 3, 2, 3, 1]$, dont les sous-séquences $1$-bonnes, telles que $[3, 2, 3]$ et $[3, 2, 1]$, ont toutes une longueur au plus égale à $L = 3$.

Dans le deuxième cas de test, une $M$-séquence $b$ possible est $[1, 1, 5, 4, 2, 5]$, dont les sous-séquences $2$-bonnes, telles que $[5, 4, 2]$ et $[1, 1, 2]$, ont toutes une longueur au plus égale à $L = 3$.

Dans le troisième cas de test, il peut être démontré que la seule $b$ possible est $b = a$.