Для участия в лотерее пришли \(n\) человек, пронумерованных от \(1\) до \(n\). Каждый получил билет с целым числом от \(0\) до \(m\).
В лотерее равновероятно вытягивается одно целое целевое число от \(0\) до \(m\). Победителями объявляются \(k\) билетов (или меньше, если участников недостаточно) с числами, наиболее близкими к целевому. В случае ничьей победителем объявляется билет, принадлежащий человеку с меньшим номером.
Байтек решил принять в ней участие. Он знает значения на билетах всех предыдущих участников. Он может выбрать любое значение на своем билете, но, к сожалению, поскольку он получил его последним, номер Байтека равен \(n + 1\).
Байтек хочет выиграть в лотерею. Таким образом, он хочет узнать, какое число он должен выбрать, чтобы максимизировать шансы на выигрыш. Он хочет узнать наименьшее целое число в случае, если таких целых чисел много. Ваша задача — найти число и рассчитать шансы на выигрыш.
Выходные данные
Вы должны вывести два целых числа. Первое должно быть равно количеству значений целевого числа (от \(0\) до \(m\)), при котором Байтек выигрывает, если оптимально выберет свой билет. Второе должно быть равно целому числу, которое Байтек должен выбрать, чтобы максимизировать свой шанс на выигрыш в лотерею.
Примечание
В первом примере Байтек выиграет при \(4\)-х целевых значениях (а именно \(0, 1, 2, 3\)), если выберет целое число \(2\), которое является наименьшим оптимальным значением. Если он выберет \(3\), он также выиграет в четырех случаях, но это значение не является наименьшим.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 6 2
1 4 5
|
4 2
|
|
2
|
7 7 1
2 4 7 3 0 1 6
|
1 5
|