MACVSMAG - Machau vs Maggu

You will find three types of people in an engineering college Maggu, Machau and Others. We all know how much hard Maggu people try to portray themselves as Machau but they never succeed. Today Machau people have decided to recruit few Maggus and convert them to Machau. All the Maggus who wanted to become Machau had to reach Machau Club situated at "YAY MACHAU" from their current location A. Machau people had laid many books everywhere on the campus to distract Maggus and make it difficult for them to reach Machau club. The campus can be imagined as a large N x N grid in which Maggu is located at position A which is denoted by (Ax, Ay) coordinate and the Machau Club is located at position B which is denoted by (Bx, By) coordinate. Machau people had laid books at M random locations denoted by (Xi, Yi) where 1<=i<=M. Additionally to prevent Maggus who take up the challenge to runaway Machau people laid books everywhere outside the rectangular area where Maggu's location A and Machau Club's location B are are ends of the diagonal of that rectangular area. A Maggu can only walk in left, right, up or down directions from his current place as long as he doesn't leave the campus i.e. he stays inside the N x N grid. If a Maggu wants to become Machau he must reach Machau Club without touching a single book in his path and without leaving the campus grid.

More formally stating the problem: Given an N x N grid with M non-reachable cells. Test whether cell "B" can be reached from cell "A" provided only left, right, up and down movements are valid.

You must print "YAY MACHAU" if it is possible for a Maggu to reach Machau Club else print "MAGGU FOREVER"

Input

First line will contain 6 integers N, M, Ax, Ay, Bx and By Where

N=Number of rows and columns in campus grid,

M=Total number of books laid on the campus,

Ax, Ay=Coordinates of Maggu,

Bx, By=Coordinates of Machau Club.

Next M lines will contain Xi and Yi denoting coordinates on N x N grid which contain books to distract MAGGUS

NOTE: If any book is placed in position A or B MAGGU will always be distracted. All (Xi, Yi) pairs are not guaranteed to be distinct.

Output

Print "YAY MACHAU" if Maggu can reach Machau club otherwise print "MAGGU FOREVER" [without quotes]

Constraints

1<=N<=10^9

1<=M<=10^5

1<=Ax, Ay, Bx, By, Xi, Yi<=N

Sample

Input
1000 2 10 1000 1000 10
1 1
100 100

Output
YAY MACHAU

Added by:Manish Singh Bisht
Date:2014-04-01
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All

hide comments
2023-08-18 23:02:28 Oleg
Clarification - "people laid books everywhere outside the rectangular area where Maggu's location A and Machau Club's location B" means that we can travel only within rectangle [min(A,B), max(A,B)] - not whole square.
Strange that "formal" statement of problem misses it.
2014-07-26 13:43:10 [Lakshman]
@ --Jarv1s-- maximum array size which you can declare is 10^8 and that should be global not local.
2014-07-26 10:56:03 .:: Jarv1s ::.
Someone help please, I'm not even able to declare a bool array having 1000000000 size in c++
2014-06-20 19:45:59 Koderok
It says "Machau people laid books everywhere outside the rectangular area where Maggu's location A and Machau Club's location B are are ends of the diagonal of that rectangular area".
So, that means all the books will be outside the rectangular area of A and B? But, then it is always possible to move within the rectangle to reach B from A without touching any of the books.
2014-05-12 17:44:22 Manish Singh Bisht
@Flago: Not all test files are generated randomly, there are some test files with manually generated test cases as well.
2014-04-02 12:08:01 Flago
"Machau people had laid books at M random locations" does that mean that Xi and Yi are randomly generated for each test case ?
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.