Array and Operation

Interview

Time limit2sMemory limit512 MB

Summary

Given an array and a fixed K, decide if adding K to elements any number of times can turn it into a permutation of 1 to N.

Level: Easy3 of 10
Topics: Greedy, Hash map, Math, Implementation
Solved: No attempts yet

Problem

Yeongseon has an array $A$ of $N$ integers.

Only one operation applies to the array.

Choose one of the numbers in $A$ and add $K$ to it.

You can use this operation as many times as you want.

Given the array $A$ , write a program that decides whether the operation can turn $A$ into an array that contains every number from $1$ to $N$ exactly once.

Input

The first line contains the array size $N$ and the integer $K$ . ( $1 \le N \le 50$ , $1 \le K \le 10$ )

The second line contains the $N$ elements of $A$ , separated by spaces. Each element is a natural number not greater than $50$ .

Output

Print $1$ if the operation can produce an array that contains every number from $1$ to $N$ exactly once, and $0$ otherwise.

Examples4

Example 1
Input
```
4 3
1 2 4 3
```
Expected output
```
1
```
Example 2
Input
```
2 5
2 2
```
Expected output
```
0
```
Example 3
Input
```
8 1
1 1 1 1 1 1 1 1
```
Expected output
```
1
```
Example 4
Input
```
5 2
5 3 3 2 1
```
Expected output
```
0
```