Time limit per test: 1.5
Memory limit: 65536
It seems that the Museum of the Modern Technology is the only place where they don't celebrate Halloween! How can they be so far from all the mistical and mysterious? You can hardly believe that two weeks ago the Museum staff have destroyed the last detail that could bring with its ominous creak a bit of Halloween atmosphere to the realm of technology. They have replaced the old wooden doors with new automatic ones, and now they are scratching their heads over how to configure the doors.
By the order of the Director, two automatic doors were purchased. An automatic door is characterized by parameter t
, called the
, which can be set to an integer value from 1 to 109
during the door installation. Then the door functions on the following principle. If a person passes through the door at time p
, the door opens at time p
and closes at time p
. There is an exceptional case when several people go in a row with a time interval not exceeding 2 t
between any two consecutive people. In this case the door opens only once, t
seconds before the first person in the row, and it closes t
seconds after the last person in the row has passed through it. It is very important to set the optimal values of the door parameters. On the one hand, if the doors open and close too often, it will annoy visitors. On the other hand, if both doors stay opened for a long time, visitors can get cold.
More formally, two lists of time moments are given. At the moments p1
<... < pn
people have passed through the first door, and at the moments q1
<... < qm
people have passed through the second one. The task is to use the given statistics to find the optimal
for the doors — t1
for the first door and t2
for the second one that satisfy the following conditions: The total number of openings of the doors must be minimal possible. There is no continuous interval of time that both doors are opened during this interval and its length exceeds the given value d.
InputThe first line of the input contains three integers n, m and d (1 ≤ n, m ≤ 5000, 1 ≤ d ≤ 109). The second line contains numbers pi, and the third line contains numbers qi, given in the ascending order (1 ≤ pi, qi ≤ 109).
OutputOutput two integers t1 and t2, separated by a single space. If there are multiple solutions, output any. If there is no solution, output "
3 2 4
1 6 13