Problem C
Veggurinn, seinni hluti

When Trump’s contractors have built the wall then Trump calls Maggi the painter:

TRUMP: “I need you to paint my wall. The builders have no clue how to do it. Sad!”
MAGGI: “Ok, what colour should it be?”
TRUMP: “It should be great: Orange like my beautiful face!”
MAGGI: “Ok, I’ll show up with orange paint.”

The wall is $N$ units wide and the units are numbered from $1$ to $N$. Maggi’s car isn’t very large and can’t hold all the paint he needs, so he will need to make several trips to the paint store. After each trip he goes to the wall and starts painting unit $i$. Then he paints the units to its side, $i+1$, $i+2$, $\ldots $ until he has painted the $j$-th unit, at which point he runs out of paint and has to go back to the store.

Maggi sometimes gets confused and thus sometimes paints over units that he has already painted. And now after $M$ trips Maggi has completely forgot how many units he has painted. Luckily Trump was watching him closely and can tell him how many units he has painted.

Input

The first line of the input contains two integers $N$, the number of units the wall is, and $M$, the number of trips. Then there are $M$ lines. The $k$-th line contains two integers $i$ and $j$ where $i \leq j$ which are the starting and ending unit Maggi paints after trip $k$.

Output

Print the number of units Maggi painted and then print “The Mexicans took our jobs! Sad!” if that value is greater than $N / 2$, otherwise print “The Mexicans are Lazy! Sad!”.

Scoring

The solution will be tested on input data of varying difficulty and the data is divided into groups as shown in the table below. The solution will then be scored according to how many groups are solved.

100 5
1 10
9 20
20 30
50 70
55 80

61
The Mexicans took our jobs! Sad!