시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 128 MB 1392 637 521 48.874%

문제

개미 여러 마리가 길이가 lcm인 막대 위에 있다. 각 개미의 이동 속도는 모두 일정하며, 1cm/s이다. 개미가 막대의 마지막까지 걸어간다면, 개미는 그 즉시 떨어지게 된다. 또, 두 개미가 만나게 된다면, 방향을 반대로 바꾸어 걸어가게 된다.

가장 처음에 막대 상에서 개미의 위치를 알고 있다. 하지만, 개미가 어느 방향으로 움직이는 지는 알 수가 없다. 이 때, 모든 개미가 땅으로 떨어질 때까지 가능한 시간 중 가장 빠른 시간과 느린 시간을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 테스트 케이스의 개수가 주어진다. 각 테스트 케이스의 첫째 줄에는 막대의 길이와 개미의 수 n이 주어진다. 다음 n개 줄에는 숫자가 하나씩 주어지며, 이 숫자는 개미의 초기 위치를 나타낸다. 개미의 위치는 1000000보다 작거나 같으며, 공백으로 구분되어져 있다.

출력

각 테스트 케이스에 대해서, 두 숫자를 출력한다. 첫 번째 숫자는 개미가 모두 땅으로 떨어지는 가능한 시간 중 가장 빠른 시간, 두 번째 숫자는 가장 늦은 시간이다.

예제 입력 1

2
10 3
2
6
7
214 7
11
12
7
13
176
23
191

예제 출력 1

4 8
38 207

힌트

W3sicHJvYmxlbV9pZCI6IjQzMDciLCJwcm9ibGVtX2xhbmciOiIwIiwidGl0bGUiOiJcdWFjMWNcdWJiZjgiLCJkZXNjcmlwdGlvbiI6IjxwPlx1YWMxY1x1YmJmOCBcdWM1ZWNcdWI3ZWMgXHViOWM4XHViOWFjXHVhYzAwIFx1YWUzOFx1Yzc3NFx1YWMwMCBsY21cdWM3NzggXHViOWM5XHViMzAwIFx1YzcwNFx1YzVkMCBcdWM3ODhcdWIyZTQuIFx1YWMwMSBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzc0XHViM2Q5IFx1YzE4ZFx1YjNjNFx1YjI5NCBcdWJhYThcdWI0NTAgXHVjNzdjXHVjODE1XHVkNTU4XHViYTcwLCAxY21cL3NcdWM3NzRcdWIyZTQuIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI5YzlcdWIzMDBcdWM3NTggXHViOWM4XHVjOWMwXHViOWM5XHVhZTRjXHVjOWMwIFx1YWM3OFx1YzViNFx1YWMwNFx1YjJlNFx1YmE3NCwgXHVhYzFjXHViYmY4XHViMjk0IFx1YWRmOCBcdWM5ODlcdWMyZGMgXHViNWE4XHVjNWI0XHVjOWMwXHVhYzhjIFx1YjQxY1x1YjJlNC4gXHViNjEwLCBcdWI0NTAgXHVhYzFjXHViYmY4XHVhYzAwIFx1YjljY1x1YjA5OFx1YWM4YyBcdWI0MWNcdWIyZTRcdWJhNzQsIFx1YmMyOVx1ZDVhNVx1Yzc0NCBcdWJjMThcdWIzMDBcdWI4NWMgXHViYzE0XHVhZmI4XHVjNWI0IFx1YWM3OFx1YzViNFx1YWMwMFx1YWM4YyBcdWI0MWNcdWIyZTQuPFwvcD5cclxuXHJcbjxwPlx1YWMwMFx1YzdhNSBcdWNjOThcdWM3NGNcdWM1ZDAgXHViOWM5XHViMzAwIFx1YzBjMVx1YzVkMFx1YzExYyBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViOTdjIFx1YzU0Y1x1YWNlMCBcdWM3ODhcdWIyZTQuIFx1ZDU1OFx1YzljMFx1YjljYywgXHVhYzFjXHViYmY4XHVhYzAwIFx1YzViNFx1YjI5MCBcdWJjMjlcdWQ1YTVcdWM3M2NcdWI4NWMgXHVjNmMwXHVjOWMxXHVjNzc0XHViMjk0IFx1YzljMFx1YjI5NCBcdWM1NGMgXHVjMjE4XHVhYzAwIFx1YzVjNlx1YjJlNC4gXHVjNzc0IFx1YjU0YywgXHViYWE4XHViNGUwIFx1YWMxY1x1YmJmOFx1YWMwMCBcdWI1NDVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWM4IFx1YjU0Y1x1YWU0Y1x1YzljMCBcdWFjMDBcdWIyYTVcdWQ1NWMgXHVjMmRjXHVhYzA0IFx1YzkxMSBcdWFjMDBcdWM3YTUgXHViZTYwXHViOTc4IFx1YzJkY1x1YWMwNFx1YWNmYyBcdWIyOTBcdWI5YjAgXHVjMmRjXHVhYzA0XHVjNzQ0IFx1YWQ2Y1x1ZDU1OFx1YjI5NCBcdWQ1MDRcdWI4NWNcdWFkZjhcdWI3YThcdWM3NDQgXHVjNzkxXHVjMTMxXHVkNTU4XHVjMmRjXHVjNjI0LjxcL3A+XHJcbiIsImlucHV0IjoiPHA+XHVjY2FiXHVjOWY4IFx1YzkwNFx1YzVkMCBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1YWMxY1x1YzIxOFx1YWMwMCBcdWM4ZmNcdWM1YjRcdWM5YzRcdWIyZTQuIFx1YWMwMSBcdWQxNGNcdWMyYTRcdWQyYjggXHVjZjAwXHVjNzc0XHVjMmE0XHVjNzU4IFx1Y2NhYlx1YzlmOCBcdWM5MDRcdWM1ZDBcdWIyOTQgXHViOWM5XHViMzAwXHVjNzU4IFx1YWUzOFx1Yzc3NFx1YzY0MCBcdWFjMWNcdWJiZjhcdWM3NTggXHVjMjE4IG5cdWM3NzQgXHVjOGZjXHVjNWI0XHVjOWM0XHViMmU0LiBcdWIyZTRcdWM3NGMgblx1YWMxYyBcdWM5MDRcdWM1ZDBcdWIyOTQgXHVjMjJiXHVjNzkwXHVhYzAwIFx1ZDU1OFx1YjA5OFx1YzUyOSBcdWM4ZmNcdWM1YjRcdWM5YzBcdWJhNzAsIFx1Yzc3NCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhYzFjXHViYmY4XHVjNzU4IFx1Y2QwOFx1YWUzMCBcdWM3MDRcdWNlNThcdWI5N2MgXHViMDk4XHVkMGMwXHViMGI4XHViMmU0LiBcdWFjMWNcdWJiZjhcdWM3NTggXHVjNzA0XHVjZTU4XHViMjk0IDEwMDAwMDBcdWJjZjRcdWIyZTQgXHVjNzkxXHVhYzcwXHViMDk4IFx1YWMxOVx1YzczY1x1YmE3MCwgXHVhY2Y1XHViYzMxXHVjNzNjXHViODVjIFx1YWQ2Y1x1YmQ4NFx1YjQxOFx1YzViNFx1YzgzOCBcdWM3ODhcdWIyZTQuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+XHVhYzAxIFx1ZDE0Y1x1YzJhNFx1ZDJiOCBcdWNmMDBcdWM3NzRcdWMyYTRcdWM1ZDAgXHViMzAwXHVkNTc0XHVjMTFjLCBcdWI0NTAgXHVjMjJiXHVjNzkwXHViOTdjIFx1Y2Q5Y1x1YjgyNVx1ZDU1Y1x1YjJlNC4gXHVjY2FiIFx1YmM4OFx1YzlmOCBcdWMyMmJcdWM3OTBcdWIyOTQgXHVhYzFjXHViYmY4XHVhYzAwIFx1YmFhOFx1YjQ1MCBcdWI1NDVcdWM3M2NcdWI4NWMgXHViNWE4XHVjNWI0XHVjOWMwXHViMjk0IFx1YWMwMFx1YjJhNVx1ZDU1YyBcdWMyZGNcdWFjMDQgXHVjOTExIFx1YWMwMFx1YzdhNSBcdWJlNjBcdWI5NzggXHVjMmRjXHVhYzA0LCBcdWI0NTAgXHViYzg4XHVjOWY4IFx1YzIyYlx1Yzc5MFx1YjI5NCBcdWFjMDBcdWM3YTUgXHViMmE2XHVjNzQwIFx1YzJkY1x1YWMwNFx1Yzc3NFx1YjJlNC48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIwIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWQ1NWNcdWFkNmRcdWM1YjQifSx7InByb2JsZW1faWQiOiI0MzA3IiwicHJvYmxlbV9sYW5nIjoiMSIsInRpdGxlIjoiQW50cyIsImRlc2NyaXB0aW9uIjoiPHA+QW4gYXJteSBvZiBhbnRzIHdhbGsgb24gYSBob3Jpem9udGFsIHBvbGUgb2YgbGVuZ3RoIGwgY20sIGVhY2ggd2l0aCBhIGNvbnN0YW50IHNwZWVkIG9mIDEgY21cL3MuIFdoZW4gYSB3YWxraW5nIGFudCByZWFjaGVzIGFuIGVuZCBvZiB0aGUgcG9sZSwgaXQgaW1tZWRpYXRlbGx5IGZhbGxzIG9mZiBpdC4gV2hlbiB0d28gYW50cyBtZWV0IHRoZXkgdHVybiBiYWNrIGFuZCBzdGFydCB3YWxraW5nIGluIG9wcG9zaXRlIGRpcmVjdGlvbnMuIFdlIGtub3cgdGhlIG9yaWdpbmFsIHBvc2l0aW9ucyBvZiBhbnRzIG9uIHRoZSBwb2xlLCB1bmZvcnR1bmF0ZWx5LCB3ZSBkbyBub3Qga25vdyB0aGUgZGlyZWN0aW9ucyBpbiB3aGljaCB0aGUgYW50cyBhcmUgd2Fsa2luZy4gWW91ciB0YXNrIGlzIHRvIGNvbXB1dGUgdGhlIGVhcmxpZXN0IGFuZCB0aGUgbGF0ZXN0IHBvc3NpYmxlIHRpbWVzIG5lZWRlZCBmb3IgYWxsIGFudHMgdG8gZmFsbCBvZmYgdGhlIHBvbGUuPFwvcD5cclxuIiwiaW5wdXQiOiI8cD5UaGUgZmlyc3QgbGluZSBvZiBpbnB1dCBjb250YWlucyBvbmUgaW50ZWdlciBnaXZpbmcgdGhlIG51bWJlciBvZiBjYXNlcyB0aGF0IGZvbGxvdy4gVGhlIGRhdGEgZm9yIGVhY2ggY2FzZSBzdGFydCB3aXRoIHR3byBpbnRlZ2VyIG51bWJlcnM6IHRoZSBsZW5ndGggb2YgdGhlIHBvbGUgKGluIGNtKSBhbmQgbiwgdGhlIG51bWJlciBvZiBhbnRzIHJlc2lkaW5nIG9uIHRoZSBwb2xlLiBUaGVzZSB0d28gbnVtYmVycyBhcmUgZm9sbG93ZWQgYnkgbiBpbnRlZ2VycyBnaXZpbmcgdGhlIHBvc2l0aW9uIG9mIGVhY2ggYW50IG9uIHRoZSBwb2xlIGFzIHRoZSBkaXN0YW5jZSBtZWFzdXJlZCBmcm9tIHRoZSBsZWZ0IGVuZCBvZiB0aGUgcG9sZSwgaW4gbm8gcGFydGljdWxhciBvcmRlci4gQWxsIGlucHV0IGludGVnZXJzIGFyZSBub3QgYmlnZ2VyIHRoYW4gMTAwMDAwMCBhbmQgdGhleSBhcmUgc2VwYXJhdGVkIGJ5IHdoaXRlc3BhY2UuPFwvcD5cclxuIiwib3V0cHV0IjoiPHA+Rm9yIGVhY2ggY2FzZSBvZiBpbnB1dCwgb3V0cHV0IHR3byBudW1iZXJzIHNlcGFyYXRlZCBieSBhIHNpbmdsZSBzcGFjZS4gVGhlIGZpcnN0IG51bWJlciBpcyB0aGUgZWFybGllc3QgcG9zc2libGUgdGltZSB3aGVuIGFsbCBhbnRzIGZhbGwgb2ZmIHRoZSBwb2xlIChpZiB0aGUgZGlyZWN0aW9ucyBvZiB0aGVpciB3YWxrcyBhcmUgY2hvc2VuIGFwcHJvcHJpYXRlbHkpIGFuZCB0aGUgc2Vjb25kIG51bWJlciBpcyB0aGUgbGF0ZXN0IHBvc3NpYmxlIHN1Y2ggdGltZS48XC9wPlxyXG4iLCJoaW50IjoiIiwib3JpZ2luYWwiOiIxIiwicHJvYmxlbV9sYW5nX2NvZGUiOiJcdWM2MDFcdWM1YjQifV0=