Mr. Cai and TT were playing in a beautiful sandy beach, and TT discovered a tree branch with many ant walking on it.

TT noticed that when one ant meet another, they would turn back and keep on walking, when an ant walk straight to the side of the branch and there is no block on it's road(if exist, this ant will meet another and turn back,then it can't walk out the branch), it will walk out the branch and disappear. Mr.Cai also noticed this, he said:"TT, if you tell me how long will all the ants disappear and how long is the first ant walked out, I'll buy you many many snacks as praise."

There are many cases. First there are two integers len and n, means the length of the branch and the number of the ant.then followed n lines, the ith line includes the ith ant's position to the left side and it's position. Suppose all the ants walk 1m/s, and no time will waste in every meet or turn back.

For each case, output the maximun time these ants spent and the mininum time the first ant walked out.