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

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

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

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

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

Во второй строке записаны $n$ целых чисел $a_1, a_2, \ldots, a_n$ ($1 \leq a_i \leq 10^{18}$), определяющих моменты времени, когда на канале А начнётся показ рекламы. Гарантируется, что моменты времени следуют в порядке возрастания, и что между любыми двумя рекламными роликами ненулевое количество времени показывается сериал, то есть $a_i + k < a_{i + 1}$ для любого $i$ от $1$ до $n - 1$.

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

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

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

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