Prologin, the French National Computer Science Contest

Énoncé¶

$N$ loqueteaux empêchent d'ouvrir une porte. Un loqueteau peut se retrouver dans deux positions: gauche (représenté par un 0), et droite (représenté par un 1). Un loqueteau en position droite fixé sur la porte gauche ou un loqueteau en position gauche fixé sur la porte droite bloquent l'ouverture de la porte. La première moitié des loqueteaux sont fixés sur la porte gauche, et l'autre moitié sont fixés sur la porte droite.

Pour pouvoir ouvrir la porte, il est nécessaire qu'aucun loqueteau ne bloque l'ouverture de la porte. C'est-à-dire que tous les loqueteaux situés sur la porte gauche doivent être en position gauche (0), et tous les loqueteaux situés sur la porte droite doivent être en position droite (1).

Grâce à un système ingénieux, vous pouvez échanger la position de deux loqueteaux situés à une distance de $D$ l'un de l'autre. ($D - 1$ loqueteaux les séparent). Par exemple, si $D = 3$, vous pouvez échanger la position de tous deux loqueteaux à une distance de 3 dans la liste des loqueteaux (Le 1er et le 4ème, par exemple).

Est-il possible d'ouvrir la porte en n'utilisant que ce système ?

Entrée¶

L’entrée contiendra :

Sur la première ligne, un entier : N, le nombre de loqueteaux.
Sur la ligne suivante, un entier : D, la distance entre deux loqueteaux échangeables.
Sur la ligne suivante, une liste de N entiers séparés par des espaces : loqueteaux, la liste des positions des loqueteaux.

Sortie¶

Indiquer s'il est possible d'ouvrir la porte.

Contraintes¶

$2 \le N \le 1\,000$
$N$ est garanti pair

Runtime constraints

Maximum memory usage: 1000 kilobytes
Maximum execution time: 1000 milliseconds

Input/output samples

Sample input

10
2
0 0 0 1 1 0 0 1 1 1

Sample output

OUI

Note

Il est possible d'échanger les loqueteaux en position 4 et 6, ainsi que les loqueteaux en position 5 et 7 (On considère une position comme étant un nombre allant de 1 à $N$). Ainsi les 5 loqueteaux en position 0 se retrouveront dans la moitié gauche de la liste.