Просмотр сериалов

문제

Сегодня у Алёны выходной, а значит ничто не помешает ей заниматься любимым делом --- смотреть сериалы по телевизору. В течение всего дня на канале А будут показывать новый сезон сериала <<Борьба табуреток>>, а на канале Б новый сезон сериала <<Дворец из домино>>. Поскольку Алёна не может выбрать, какой из этих двух сериалов ей нравится больше, то она решила попробовать смотреть оба, переключаясь на другой канал каждый раз, когда начинается реклама.

В момент времени $00$ Алёна включит телевизор и начнёт смотреть сериал <<Борьба табуреток>> по каналу А. Если в какой-либо момент времени на телеканале, который Алёна сейчас смотрит, начнётся реклама, то Алёна переключит телевизор на другой телеканал и будет смотреть его. Если Алёна переключает телеканал, а там тоже в данный момент идёт реклама, то она не станет переключаться обратно в надежде, что на этом канале реклама закончится раньше. В момент времени $tt$ Алёна выключит телевизор и пойдёт спать.

По заданному расписанию показа рекламы и продолжительности одного рекламного ролика определите, какое количество единиц времени Алёна будет смотреть каждый из сериалов.

입력

В первой строке входных данных записаны четыре целых числа $nn$, $mm$, $tt$ и $kk$ ($1\le n,m\le 1000001\; \backslash leq\; n,\; m\; \backslash leq\; 100\backslash ,000$, $1\le t\le {10}^{18}1\; \backslash leq\; t\; \backslash leq\; 10^\{18\}$, $1\le k\le {10}^{9}1\; \backslash leq\; k\; \backslash leq\; 10^9$) --- количество показов рекламы на канале А, количество показов рекламы на канале Б, момент времени, когда Алёна пойдёт спать и продолжительность одного рекламного ролика на любом из каналов соответственно.

Во второй строке записаны $nn$ целых чисел $a_1,a_2,\dots ,a_{n}a\_1,\; a\_2,\; \backslash ldots,\; a\_n$ ($1\le a_i\le {10}^{18}1\; \backslash leq\; a\_i\; \backslash leq\; 10^\{18\}$), определяющих моменты времени, когда на канале А начнётся показ рекламы. Гарантируется, что моменты времени следуют в порядке возрастания, и что между любыми двумя рекламными роликами ненулевое количество времени показывается сериал, то есть для любого $ii$ от $11$ до $n-1n\; -\; 1$.

В третьей строке записаны $mm$ целых чисел $b_1,b_2,\dots ,b_{m}b\_1,\; b\_2,\; \backslash ldots,\; b\_m$ ($1\le b_i\le {10}^{18}1\; \backslash leq\; b\_i\; \backslash leq\; 10^\{18\}$), определяющих моменты времени, когда на канале Б начнётся показ рекламы. Как и для канала А, для канала Б гарантируется, что моменты времени следуют в порядке возрастания, и что между любыми двумя рекламными роликами идёт сериал в течение ненулевого отрезка времени.

출력

Выведите два целых числа, равных суммарному количеству времени, которое Алёна будет смотреть сериал <<Борьба табуреток>> и сериал <<Дворец из домино>> соответственно.

힌트

В первом примере реклама на обоих каналах всегда начинается одновременно, поэтому, хотя Алёна и переключит канал в момент времени $44$, она будет смотреть рекламу в течение трёх моментов времени. Затем она снова переключит канал в момент времени $88$, но уже не дождётся конца рекламы и уйдёт спать.

Во втором примере Алёна будет переключать каналы таким образом, что ей никогда не придётся смотреть рекламу.