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

면접 대비

시간 제한2초메모리 제한1024 MB

요약

두 채널의 광고 시작 시각이 주어질 때, 광고가 시작될 때마다 채널을 바꾸는 알료나가 시각 t까지 각 드라마를 본 총시간을 구한다.

난이도: 보통10점 중 6점
유형: 시뮬레이션, 구간, 구현
정답자: 아직 제출이 없습니다

문제

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

В момент времени $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$ , но уже не дождётся конца рекламы и уйдёт спать.

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

예제2

예제 1
입력
```
2 2 10 3
4 8
4 8
```
예상 출력
```
4 1
```
예제 2
입력
```
6 5 10 1
1 3 5 7 9 11
2 4 6 8 10
```
예상 출력
```
5 5
```