Ants

Several ants are placed on a rod that is $l$ cm long. Every ant always moves at a constant speed of $1\,\text{cm/s}$. When an ant reaches either end of the rod, it immediately falls off. Whenever two ants meet, both of them instantly reverse direction and keep moving.

You know the initial position of every ant, but you do not know whether each ant initially moves to the left or to the right. Assuming the initial directions can be chosen freely, write a program that finds the shortest possible time and the longest possible time until every ant has fallen off the rod.

The first line contains the number of test cases. For each test case, the first line contains the rod length $l$ and the number of ants $n$, separated by a space. Each of the next $n$ lines contains the initial position of one ant. A position is an integer distance measured from the left end of the rod. Every number in the input is at most $1{,}000{,}000$.

For each test case, print two integers. The first is the shortest possible time for all ants to fall off the rod, and the second is the longest possible time. Separate the two numbers with a space.

• $1 \le n \le 100{,}000$
• $1 \le l \le 1{,}000{,}000$
• Each ant's position is an integer.
• $0 \le$ (ant position) $\le l$