VUDBOL5 - Ninja

no tags 

A ninja is practicing and he is very fast he can make two cuts in one second and his master give he a new challenge. The master take a cube, thrown through the air and quickly says four numbers. The ninja has to think fast to make two cuts and get desired values.

Given a cube of size N*N*N, he need to cut it into four entire pieces of size A, B, C and D. He needs to divide the cube in these pieces with only two cuts, one vertical and one horizontal.

Input

The input consists in multiple test cases.
Each test case begins a line containing five integers N (2 <= N <= 1000000), A, B, C y D (1 <= A, B, C, D <= 2^63).
The end of input is indicated by a line with five zeros. This is not a part of any test case.

Output

For each test case print "Possible" if it is possible to obtain the pieces and print "Impossible" if it is not possible to obtain the pieces with two cuts.

Example

Input:
2 5 1 1 1
2 2 2 2 2
3 12 3 6 6
0 0 0 0 0

Output:
Impossible
Possible
Possible

hide comments
Massand Sagar Sunil: 2013-05-10 09:39:51

3 WAs because you didn't mention that cut could only be at integer-coordinates.Please change the problem statement immediately, you are wasting everyone's time.

Robert Gerbicz: 2012-12-30 19:35:57

Here size=volume.

Shubham.IIITM: 2012-08-07 15:18:13

wht is meant by size !!!

:D: 2012-05-07 09:44:53

Yes, I got AC with assumpion of only integer coordinates.

Mehmet Inal: Yes ull is enougth (since N^3 fits), but you have to code carefully in few places to not overflow on operations with A,B,C,D.

Alex Anderson: 2012-05-07 01:38:59

For this case, is it possible or impossible?

6 132 6 66 12


Rather, I believe the problem statement is incorrect. You should specify that the cuts can only occur at integer coordinates, since I have submitted a solution which is correct if you can make cuts at fractional lengths.

Last edit: 2012-05-07 01:52:42
Francky: 2012-05-05 20:30:23

I can't imagine reasons that restrict the allowed languages. Please open to all, it's a good problem. (It's a general comment for many problems)

(Tjandra Satria Gunawan)(曾毅昆): 2012-05-05 08:30:36

@all : There are many tricky test cases :-D
Finally AC after 3 submissions...
@ Mehmet Inal : No, I use int64 string to solve this problem...

Last edit: 2012-05-05 09:42:22
mehmetin: 2012-05-03 14:36:35

Do the intermediate values fit into unsigned long long?

Last edit: 2012-05-04 18:30:18
Krishna Datt Mishra: 2012-05-03 06:42:51

Not necessary that all are cubes but can be in best case.


Added by:Edwin Guzman
Date:2012-04-25
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:ASM32-GCC MAWK BC C-CLANG C NCSHARP C++ 4.3.2 CPP CPP14 CPP14-CLANG COBOL COFFEE D-CLANG D-DMD DART ELIXIR FANTOM FORTH GOSU GRV JAVA JS-MONKEY JULIA KTLN NIM NODEJS OBJC OBJC-CLANG OCT PICO PROLOG PYPY PYPY3 PY_NBC R RACKET RUST CHICKEN SQLITE SWIFT UNLAMBDA VB.NET