26C. Which Window?

1500 pts2s256 MB

A house has $n$ windows arranged in a row, numbered from $1$ to $n$ .

There are $m$ alarms. You are given an array $a_1,a_2,\ldots,a_m$ . Alarm $i$ monitors exactly the $k$ consecutive windows $a_i,a_i+1,\ldots,a_i+k-1$ .

An alarm is on if at least one window it monitors is open, and off otherwise. You can see the state of every alarm separately.

You may permanently lock some windows closed. Afterward, at most one unlocked window will be open at any moment; it is also possible that all windows are closed. Locking a window does not change which windows the alarms monitor.

Find the minimum number of windows you must permanently lock so that the alarm states always determine exactly which window is open, or determine that all windows are closed.

Constraints

$1 \le t \le 10^4$
$1 \le n,m \le 2 \times 10^5$
$1 \le k \le n$
$1 \le a_i \le n-k+1$
Alarm starting positions may repeat
The sum of $n+m$ over all test cases is at most $4\times 10^5$

Input

t

\left. \begin{array}{l} n \quad m \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_m \end{array} \right\} \times t

Output

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Samples

Input

Case 1

7 3 3
1 3 5

Case 2

6 3 2
1 3 5

Explanation

Case 1

Lock windows $2$ and $7$ . Opening one of windows $1,3,4,5,6$ triggers, respectively, alarm sets $\{1\}$ , $\{1,2\}$ , $\{2\}$ , $\{2,3\}$ , and $\{3\}$ . These are all different and nonempty. At least one window from each pair $(1,2)$ and $(6,7)$ must be locked, since the two windows in either pair trigger exactly the same alarms.

Case 2

Lock windows $2,4,6$ . Opening window $1$ , $3$ , or $5$ triggers only alarm $1$ , $2$ , or $3$ , respectively. In each pair $(1,2)$ , $(3,4)$ , and $(5,6)$ , at least one window must be locked.

Output

Case 1

Case 2

Input

Case 1

8 2 2
1 5

Case 2

5 3 3
1 2 3

Case 3

4 3 4
1 1 1

Explanation

Case 1

Windows $3,4,7,8$ are not monitored by any alarm, so opening one would look the same as leaving every window closed. They must all be locked. At least one window from each pair $(1,2)$ and $(5,6)$ must also be locked. Keeping only windows $1$ and $5$ unlocked achieves the minimum of $6$ locked windows.

Case 2

Opening windows $1,2,3,4,5$ triggers alarm sets $\{1\}$ , $\{1,2\}$ , $\{1,2,3\}$ , $\{2,3\}$ , and $\{3\}$ , respectively. These are all different and nonempty, so no window needs to be locked.

Case 3

All three alarms monitor all four windows. Opening any window turns on every alarm, so at most one window may remain unlocked. Locking any three windows is sufficient.

Output

Case 1

Case 2

Case 3

A house has $n$ windows arranged in a row, numbered from $1$ to $n$ .

There are $m$ alarms. You are given an array $a_1,a_2,\ldots,a_m$ . Alarm $i$ monitors exactly the $k$ consecutive windows $a_i,a_i+1,\ldots,a_i+k-1$ .

An alarm is on if at least one window it monitors is open, and off otherwise. You can see the state of every alarm separately.

Find the minimum number of windows you must permanently lock so that the alarm states always determine exactly which window is open, or determine that all windows are closed.

$1 \le t \le 10^4$
$1 \le n,m \le 2 \times 10^5$
$1 \le k \le n$
$1 \le a_i \le n-k+1$
Alarm starting positions may repeat
The sum of $n+m$ over all test cases is at most $4\times 10^5$

t

\left. \begin{array}{l} n \quad m \quad k \\ a_1 \quad a_2 \quad \ldots \quad a_m \end{array} \right\} \times t

\left. \begin{array}{l} \mathrm{answer} \end{array} \right\} \times t

Lock windows $2,4,6$ . Opening window $1$ , $3$ , or $5$ triggers only alarm $1$ , $2$ , or $3$ , respectively. In each pair $(1,2)$ , $(3,4)$ , and $(5,6)$ , at least one window must be locked.

Opening windows $1,2,3,4,5$ triggers alarm sets $\{1\}$ , $\{1,2\}$ , $\{1,2,3\}$ , $\{2,3\}$ , and $\{3\}$ , respectively. These are all different and nonempty, so no window needs to be locked.

Which Window? - Repovive Standard Round 8 | Repovive

My submissions

Announcements

My submissions

Announcements

My submissions

Announcements

26C. Which Window?

Constraints

Input

Output

Samples

26C. Which Window?

Constraints

Input

Output

Samples