Welcome to ZOJ
Select Problem
ZOJ Problem Set - 1483

Time Limit: 2 Seconds      Memory Limit: 65536 KB

Xylophone produces N working robots. But these robots are just lazy as Xylophone. Each time their work assginment is not well arranged so that some robots do more work than others, they complains a lot and even goes on strike sometimes.

The other day, Xylophone asks the robots to do his homework. He has M problems to do, each of which has a difficulty level. for convenience, Xylophone assigns these problems in their original order, so that each robot gets some neighboring problems. Xylophone needs a scheme to assign the problems, so that the difference between the total difficulty points of a robot and the average value does not exceed K. Notice that a robot gets difficulty point 0 if he is not assigned any problems.

Your job is to tell whether such a scheme exists.


There are multiple cases.

The first line contains three integers N, M and K. (0 < N, M<= 500, 0 < K <= 2,000,000)

The following M lines contains one integer Di (0 < Di <= 2,000,000), which is the difficulty level of the ith problem.


One line for each case, eith "possible" or "impossible".

Sample Input

2 3 1

Sample Output


Author: XU, Chuan
Source: ZOJ Monthly, January 2003
Submit    Status