DOJO - With a Pit of Death

Leo is training his martial arts in byteland's dojo.
The dojo is a rectangular ( n × m ) area with a pit of death, a square located at (i, j), where 1 <= i <= n, and 1 <= j <= m.
Every night, battles are very hard and the dojo is destructed, and reconstructed during the day around the pit.
Every evening, Leo's first mission is to make in place tatamis (2 × 1) in the new dojo.
Tatamis should cover the whole dojo except the pit of death.
Sometimes it's possible, sometimes not!

Input

The input begins with the number T of test cases in a single line.
In each of the next T lines there are four integers n, m, i and j.

Output

For each test case, print the answer of the problem : "Possible." or "Impossible.".

Example

Input:
2
3 3 2 2
3 3 1 2
Output: Possible.
Impossible.

Constraints

1 <= T <= 1 000
1 <= i <= n <= 32
1 <= j <= m <= 102000

 

dojo

Edit 2017-02-11 : 0.15s as TL, alongside the compiler changes.


Added by:Francky
Date:2012-05-26
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:Own problem

hide comments
2015-06-14 21:16:33 Piyush Kumar
I submitted the same solution numerous times , it got ac two times and exceeded the time limit in the rest. How is this possible ?

(Francky) => server instability, and the fact that your solution is very near from time limit at each time. It is rare now with cube cluster, more stable than pyramid cluster. That's all.

Last edit: 2015-06-15 08:55:10
2014-01-10 17:30:32 Shivam
those full stops cost me 2 hours of debugging :/ .. AC finally :D
2013-04-20 01:38:27 (Tjandra Satria Gunawan)(曾毅昆)
@Francky: I hope you make BF solvable problem again :-) This is your first and easiest problem isn't it?
--ans--> It's true : it's my very first problem, and the easiest too. I can't guarantee that my future problems are BrainFuck solvable, as I didn't yet pay attention at that art. I begin to make a list of my problems, as you asked ;-)
It's still in beta : http://www.spoj.com/problems/FRANCKY/
@Francky: Wow, that's good :-)

Last edit: 2013-04-20 15:39:05
2013-03-26 00:46:52 Mitch Schwartz
Thanks. And it uses less memory than those Java submissions too! :p
2013-03-25 23:54:55 Francky
Congratulations to Mitch, the first solver with uncommon language, and faster than others.
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.