Коту Бенедикту очень нравится число $$$k$$$ и он хочет стать $$$k$$$-мышовым котом.
Как известно, кот считается $$$k$$$-мышовым, если он в течение некоторого времени ловит не менее $$$k$$$ мышей. Известны последовательные моменты времени $$$(0 \le) \, t_1 \le t_2 \le \ldots \le t_n$$$, в которые кот Бенедикт ловил мышей. Для каждого момента $$$t_i$$$ также известно количество мышей $$$m_i$$$, которых кот поймал в этот момент.
Кот Бенедикт хотел бы продемонстрировать, что он способен поймать $$$k$$$ мышей за короткое время. Поэтому он хочет выбрать наиболее короткий отрезок времени из диапазона от $$$0$$$ до $$$t_n$$$ (включительно), в течение которого он поймал не менее $$$k$$$ мышей.
Ваша задача — указать границы такого временного отрезка минимальной длины, которые позволят считать кота Бенедикта $$$k$$$-мышовым. Если существует несколько вариантов ответа, выведите любой из них.
В первой строке содержатся целые числа $$$n$$$ и $$$k$$$ $$$(1 \le n \le 3 \cdot 10^5,\, 1 \le k \le 10^{18})$$$ — количество моментов времени, в которые кот Бенедикт ловил мышей, а также число $$$k$$$.
Во второй строке содержатся целые числа $$$t_1, t_2, \ldots, t_n$$$ $$$\left(0 \le t_1 \le t_2 \le \ldots \le t_n \le 10^{18} \right)$$$ — моменты времени, в которые кот Бенедикт ловил мышей.
В третьей строке содержатся целые числа $$$m_1, m_2, \ldots, m_n$$$ $$$\left(1 \le m_j \le 10^{9}, \, j = 1, 2, \ldots, n \right)$$$, $$$m_j$$$ — количество мышей, которых кот Бенедикт поймал в момент $$$t_j$$$.
Выведите два целых числа — начальный и конечный моменты времени, ограничивающие временной отрезок минимальной длины, в течение которого кот Бенедикт поймал не менее $$$k$$$ мышей. Разделяйте числа пробелом или переводом строки.
Если существует несколько вариантов ответа, выведите любой из них.
Если кот Бенедикт не сможет стать $$$k$$$-мышовым котом, выведите в качестве ответа два числа: $$$-1$$$ $$$-1$$$.
В первой и второй подзадачах применяется потестовая система оценки. В графе «Баллы» указано количество баллов за тест и в скобках максимальное количество баллов, которое можно набрать за подзадачу. Участнику сообщаются номера тестов подзадачи, которые не были пройдены.
Баллы за подзадачи с третьей по пятую начисляются только в случае прохождения всех тестов этой подзадачи. Участнику сообщается либо номер первого непройденного теста и результат проверки на этом тесте, либо что все тесты подзадачи пройдены.
Для всех подзадач, кроме первой, требуется, чтобы программа верно решала одну или несколько из предшествующих подзадач.
Более подробно разбиение на подзадачи показано в таблице ниже.
| Подзадача | Баллы за тест | Ограничения | Необходимые | Информация |
| (баллы | подзадачи | о проверке | ||
| за подзадачу) | ||||
| 1 | 2 (до 20) | $$$n \le 1000, \, k \le 1000, $$$ | нет | полная |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$ | ||||
| $$$m_j = 1 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 2 | 2 (до 20) | $$$n \le 1000, \, k \le 10^9, $$$ | 1 | полная |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^6, \, $$$ | ||||
| $$$m_j \le 10^6 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 3 | 0 (20) | $$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$ | 1 | первая ошибка |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$ | ||||
| $$$ m_j = 1 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 4 | 0 (20) | $$$n \le 3 \cdot 10^5, \, k \le 10^9, $$$ | 1, 2, 3 | первая ошибка |
| $$$0 \le t_1$$$ < $$$t_2 \ldots$$$ < $$$t_n \le 10^9, \, $$$ | ||||
| $$$ m_j \le 5000 \, (j = 1, 2, \ldots, n)$$$ | ||||
| 5 | 0 (20) | любые возможные значения | 1, 2, 3, 4 | первая ошибка |
7 3 0 6 8 19 22 23 25 1 1 1 1 1 1 1
22 25
11 7 5 8 8 14 23 37 42 42 55 64 71 2 1 2 1 4 3 2 2 5 6 2
37 42
5 8 1 5 15 20 28 2 1 1 2 1
-1 -1
Поясним приведённые примеры.
В первом примере кот ловит по одной мыши в каждый момент времени.
Таким образом, кот может утверждать, что может стать $$$k$$$-мышовым котом за $$$3$$$ единицы времени.
Во втором примере минимальное время, которое потребуется коту — $$$5$$$ единиц времени: он поймает трёх мышей в момент $$$37$$$, а затем еще дважды по две мыши в момент $$$42$$$.
В третьем примере кот не сможет стать $$$k$$$-мышовым
