unuzero

Se consideră un șir format din $M \cdot N$ termeni a căror valoare poate fi $0$ sau $1$, cele $Q$ poziții în care se găsesc termenii egali cu $1$ fiind $P_1, P_2, \ldots, P_Q$. Termenii șirului sunt memorați, într-o matrice inițială cu $M$ linii și $N$ coloane, astfel încât șirul se obține dacă se parcurge matricea linie cu linie, în ordine, de sus în jos, și fiecare linie de la stânga la dreapta. Pentru un număr $K$ dat, se obține o matrice nouă, cu $M \cdot K$ linii și $N$ coloane, prin scrierea matricei inițiale de $K$ ori, de sus în jos, astfel încât fiecare copie este plasată sub cea de la pasul anterior.

Un grup-1 în matrice este format din una sau mai multe valori $1$ și se consideră că două valori egale cu $1$ fac parte din același grup-1 dacă se poate ajunge de la una la cealaltă parcurgând matricea pe un traseu format doar din elemente egale cu $1$, astfel încât oricare două elemente parcurse consecutiv să fie pe aceeași linie și coloane vecine sau pe aceeași coloană și linii vecine.

De exemplu, dacă $M = 2$, $N = 4$, $Q = 4$, $P_1 = 1$, $P_2 = 3$, $P_3 = 7$, $P_4 = 8$, șirul va avea 8 termeni, $1$, $0$, $1$, $0$, $0$, $0$, $1$, $1$, iar pentru $K$ având valorile $1$, $2$, respectiv $3$, matricele formate sunt:

$$\begin{pmatrix} {\color{red}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \end{pmatrix} \quad \begin{pmatrix} {\color{red}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \\ {\color{green}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \end{pmatrix} \quad \begin{pmatrix} {\color{red}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \\ {\color{green}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \\ {\color{orange}1} & 0 & {\color{blue}1} & 0 \\ 0 & 0 & {\color{blue}1} & {\color{blue}1} \end{pmatrix}$$

Cele trei matrice au $2$, $3$, respectiv $4$ grupuri-1. Cele $3$ grupuri-1 din a doua matrice sunt formate cu elementele: $\{(1, 1)\}$, $\{(3, 1)\}$, respectiv $\{(1, 3), (2, 3), (2, 4), (3, 3), (4, 3), (4, 4)\}$, elementele din același grup-1 având aceeași culoare.

Cerință

Se cere numărul grupurilor-1 din matricea cu $M \cdot K$ linii și $N$ coloane formată.

Date de intrare

Fișierul de intrare unuzero.in conține, în această ordine, pe prima linie numerele $M$, $N$, $K$, $Q$, iar pe a doua linie cele $Q$ numere $P_1, P_2, \ldots, P_Q$, separate prin câte un spațiu.

Date de ieșire

În fișierul de ieșire unuzero.out se afișează numărul grupurilor-1 cerut.

Restricții și precizări

• $1 \le M, N, K \le 1 \ 000 \ 000 \ 000$;
• $1 \le Q \le \min(M \cdot N, 100 \ 000)$;
• $1 \le P_1 < P_2 < \cdots < P_Q \le M \cdot N$.

Exemplul 1

unuzero.in

1 5 1 2
3 5

unuzero.out

2

Explicație

Pentru primul exemplu termenii egali cu $1$ sunt pe pozițiile $3$ și $5$, deci șirul este $0, 0, 1, 0, 1$, iar matricea formată are o linie și $5$ coloane, conține două grupuri-1 și este:

$$\begin{pmatrix} 0 & 0 & {\color{blue}1} & 0 & {\color{red}1} \end{pmatrix}$$

Exemplul 2

unuzero.in

3 4 1 5
2 5 7 8 11

unuzero.out

3

Explicație

Pentru al doilea exemplu termenii egali cu $1$ sunt pe pozițiile $2$, $5$, $7$, $8$ și $11$, deci șirul este $0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 1, 0$, iar matricea formată are $3$ linii și $4$ coloane, conține trei grupuri-1 și este:

$$\begin{pmatrix} 0 & {\color{red}1} & 0 & 0 \\ {\color{green}1} & 0 & {\color{blue}1} & {\color{blue}1} \\ 0 & 0 & {\color{blue}1} & 0 \end{pmatrix}$$

Exemplul 3

unuzero.in

2 5 3 4
1 4 7 9

unuzero.out

7

Explicație

Pentru al treilea exemplu termenii egali cu $1$ sunt pe pozițiile $1$, $4$, $7$ și $9$, deci șirul este $1, 0, 0, 1, 0, 0, 1, 0, 1, 0$, iar matricea formată are $6$ linii și $5$ coloane (cele $2$ linii au fost multiplicate de $3$ ori), conține $7$ grupuri-1 și este:

$$\begin{pmatrix} {\color{red}1} & 0 & 0 & {\color{blue}1} & 0 \\ 0 & {\color{green}1} & 0 & {\color{blue}1} & 0 \\ {\color{orange}1} & 0 & 0 & {\color{blue}1} & 0 \\ 0 & {\color{cyan}1} & 0 & {\color{blue}1} & 0 \\ {\color{yellow}1} & 0 & 0 & {\color{blue}1} & 0 \\ 0 & {\color{magenta}1} & 0 & {\color{blue}1} & 0 \end{pmatrix}$$