A. Clan Battle
time limit per test
1.5 seconds
memory limit per test
512 megabytes
input
standard input
output
standard output

Hikawa Kyouka is participating in her clan battle, where she needs to defeat $$$m$$$ types of bosses. Each boss can appear in multiple rounds. All bosses start in round $$$1$$$ and are initially available to challenge. For a boss $$$i$$$ to become available in round $$$j$$$ ($$$j\ge 2$$$), both conditions must be met:

  • The same boss $$$i$$$ of the immediately preceding round $$$(j-1)$$$ is defeated.
  • All bosses of the earlier round $$$(j-k)$$$ have been defeated.

For example, in the picture below, because the third boss is of Round $$$60$$$, although the first boss of Round $$$61$$$ is defeated, that boss of Round $$$62$$$ won't appear.

An example of clan battle when $$$k=2$$$. The defeated label suggests that the first, fourth, and fifth bosses are unavailable.

Kyouka wants to defeat $$$n$$$ bosses in order $$$a_1,a_2,\dots,a_n$$$. Can you help her determine if it is possible?

Input

Each test contains multiple test cases. The first line contains one integer $$$t$$$ ($$$1\le t\le 10^4$$$) — the number of test cases. The description of each test case follows.

The first line of each test case contains three integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1\le n\le 4\cdot10^6$$$, $$$1\le m \lt 10^6$$$, $$$1\le k\le10^9$$$).

The second line of each test case contains $$$n$$$ integers $$$a_1,a_2,\dots,a_n$$$ ($$$1\le a_i\le m$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$4\cdot10^6$$$.

Output

If Kyouka can defeat the bosses in the order, output "YES"; otherwise, output "NO". You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.

Example
Input
4
5 2 2
1 1 2 2 1
5 2 2
2 1 1 1 2
5 3 2
2 1 1 1 2
10 4 3
4 3 3 2 2 1 1 1 1 4
Output
YES
YES
NO
YES