k-Sort

Interview

Time limit2sMemory limit1024 MB

Summary

Given an array and k, decide whether the array can be sorted when only elements with equal remainders mod k may be swapped.

Level: Easy3 of 10
Topics: Sorting, Implementation
Solved: No attempts yet

Problem

This year Grisha entered the University of IT. The university offers many new subjects, some interesting and some not. Grisha especially likes the course "Algorithms and Data Structures". The last lecture covered sorting algorithms.

Grisha is an ambitious young man who wants to invent his own sorting algorithm and name it after his beloved grandfather. Inspired by Knuth's multi-volume series, he decided to modify an existing sorting algorithm for natural numbers with the following restriction. Two elements can be swapped only if they are congruent modulo some natural number $k$ , that is, they leave the same remainder when divided by $k$ .

Check whether the new version of the algorithm can sort the given array of natural numbers.

Input

The first line contains two integers $n$ ( $1 \le n \le 1000$ ) and $k$ ( $1 \le k \le 10^9$ ), the number of elements in the array and the number used for comparing the elements modulo $k$ .

The second line contains $n$ integers $a_i$ , the elements of the array ( $1 \le a_i \le 10^9$ ).

Output

Print "YES" if the algorithm can sort the given array, and "NO" otherwise.

Examples2

Example 1
Input
```
5 2
5 4 3 2 1
```
Expected output
```
YES
```
Example 2
Input
```
3 2
2 3 1
```
Expected output
```
NO
```