CF150E Freezing with Style

This winter is so... well, you've got the idea :-) The Nvodsk road system can be represented as $ n $ junctions connected with $ n-1 $ bidirectional roads so that there is a path between any two junctions. The organizers of some event want to choose a place to accommodate the participants (junction $ v $ ), and the place to set up the contests (junction $ u $ ). Besides, at the one hand, they want the participants to walk about the city and see the neighbourhood (that's why the distance between $ v $ and $ u $ should be no less than $ l $ ). On the other hand, they don't want the participants to freeze (so the distance between $ v $ and $ u $ should be no more than $ r $ ). Besides, for every street we know its beauty — some integer from $ 0 $ to $ 10^{9} $ . Your task is to choose the path that fits in the length limits and has the largest average beauty. We shall define the average beauty as a median of sequence of the beauties of all roads along the path. We can put it more formally like that: let there be a path with the length $ k $ . Let $ a_{i} $ be a non-decreasing sequence that contains exactly $ k $ elements. Each number occurs there exactly the number of times a road with such beauty occurs along on path. We will represent the path median as number $ a_{⌊k/2⌋} $ , assuming that indexation starting from zero is used. $ ⌊x⌋ $ — is number $ х $ , rounded down to the nearest integer. For example, if $ a={0,5,12} $ , then the median equals to $ 5 $ , and if $ a={0,5,7,12} $ , then the median is number $ 7 $ . It is guaranteed that there will be at least one path with the suitable quantity of roads.

N/A

N/A

In the first sample all roads have the same beauty. That means that all paths of the positive length have the same median. Thus, any path with length from $ 3 $ to $ 4 $ , inclusive will be valid for us. In the second sample the city looks like that: 1 - 2 - 3 - 4 - 5 - 6. Two last roads are more valuable and we should choose any path that contains both of them and has the suitable length. It is either the path between $ 2 $ and $ 6 $ or the path between $ 3 $ and $ 6 $ .