Divisibility

Time Limit: 2 Seconds
Memory Limit: 65536 KB

Consider an arbitrary sequence of integers. One can place + or - operators
between integers in the sequence, thus deriving different arithmetical expressions
that evaluate to different values. Let us, for example, take the sequence: 17,
5, -21, 15. There are eight possible expressions:

17 + 5 + -21 + 15 = 16

17 + 5 + -21 - 15 = -14

17 + 5 - -21 + 15 = 58

17 + 5 - -21 - 15 = 28

17 - 5 + -21 + 15 = 6

17 - 5 + -21 - 15 = -24

17 - 5 - -21 + 15 = 48

17 - 5 - -21 - 15 = 18

We call the sequence of integers divisible by K if + or - operators can be placed
between integers in the sequence in such way that resulting value is divisible
by K. In the above example, the sequence is divisible by 7 (17+5+-21-15=-14)
but is not divisible by 5.

You are to write a program that will determine divisibility of sequence of
integers.

**Input**

The first line of the input contains two integers, N and K (1 <= N <=
10000, 2 <= K <= 100) separated by a space.

The second line contains a sequence of N integers separated by spaces. Each
integer is not greater than 10000 by it's absolute value.

**Output**

Write to the output file the word "Divisible" if given sequence of
integers is divisible by K or "Not divisible" if it's not.

**This problem contains multiple test cases!**

The first line of a multiple input is an integer N, then a blank line followed
by N input blocks. Each input block is in the format indicated in the problem
description. There is a blank line between input blocks.

The output format consists of N output blocks. There is a blank line between
output blocks.

Sample Input

2

4 7

17 5 -21 15

4 5

17 5 -21 15

**Sample Output**

Divisible

Not divisible

Source:

**Northeastern Europe 1999**
Submit
Status