Этой зимой в городе... ну вы поняли :-) Дорожную систему города XXXводска можно представить как n перекрестков, соединенных n - 1 двунаправленными дорогами так, что между любыми двумя перекрестками есть путь. Организаторы некоего мероприятия хотят выбрать место, где будут жить участники (перекресток v), и место, где будут проходить соревнования (перекресток u). При этом, с одной стороны, они хотят, чтобы участники гуляли по городу и смотрели окрестности (поэтому расстояние между v и u должно быть не меньше l), но не хотят, чтобы участники замерзли (поэтому расстояние между v и u должно быть не больше r). Помимо этого для каждой улицы известна ее красота — некоторое целое число от 0 до 10⁹. Ваша задача — выбрать путь, удовлетворяющий ограничениям по длине, и обладающей наибольшей средней красотой. Средней красотой пути будем называть медиану последовательности красот всех дорог на пути.

Более формально: пусть есть путь длины k. Пусть a_i — неубывающая последовательность, содержащая в точности k элементов, в которой каждое число встречается ровно столько раз, сколько дорог с такой красотой встречается на этом пути. Медианой пути назовем число a_{⌊k / 2⌋}, предполагая что используется индексация от нуля. ⌊x⌋ — число х, округленное вниз до ближайшего целого.

Например, если a = {0, 5, 12}, то медиана равна 5, а если a = {0, 5, 7, 12}, то медианой окажется число 7.

Гарантируется, что найдется хотя бы один путь с подходящим количеством дорог.