개미

길이가 $l$ cm인 막대 위에 여러 마리의 개미가 놓여 있다. 모든 개미는 항상 일정한 속도 $1\,\text{cm/s}$로 움직인다. 개미가 막대의 한쪽 끝에 도달하면 그 즉시 막대 아래로 떨어진다. 두 개미가 서로 만나면 두 개미 모두 즉시 방향을 반대로 바꾸어 계속 움직인다.

각 개미의 처음 위치는 알고 있지만, 각 개미가 처음에 왼쪽과 오른쪽 중 어느 방향으로 움직이는지는 알 수 없다. 개미들의 처음 이동 방향을 자유롭게 정할 수 있다고 할 때, 모든 개미가 막대에서 떨어지기까지 걸리는 시간이 가장 짧아지는 경우의 시간과 가장 길어지는 경우의 시간을 구하는 프로그램을 작성하시오.

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이 $l$과 개미의 수 $n$이 공백으로 구분되어 주어진다. 이어지는 $n$개의 줄에는 각 줄마다 개미 한 마리의 처음 위치가 하나씩 주어진다. 개미의 위치는 막대의 왼쪽 끝에서부터 떨어진 거리를 나타내는 정수이다. 입력으로 주어지는 모든 수는 $1{,}000{,}000$ 이하이다.

각 테스트 케이스마다 두 개의 정수를 출력한다. 첫 번째 수는 모든 개미가 막대에서 떨어지기까지 걸리는 시간이 가장 짧아질 수 있는 경우의 시간이고, 두 번째 수는 가장 길어질 수 있는 경우의 시간이다. 두 수는 공백으로 구분한다.

• $1 \le n \le 100{,}000$
• $1 \le l \le 1{,}000{,}000$
• 개미의 위치는 정수이다.
• $0 \le$ (개미의 위치) $\le l$