Watching TV Series

Interview

Time limit2sMemory limit1024 MB

Summary

Given ad start times on two channels, find the total time Alyona spends on each channel when she switches at every ad on the channel she is watching.

Level: Medium4 of 10
Topics: Simulation, Binary search
Solved: No attempts yet

Problem

Alyona has a day off, so nothing stops her from doing her favorite thing, watching TV series. All day, channel A airs the new season of Stool Fight, and channel B airs the new season of Domino Palace. Alyona cannot decide which of the two she likes more, so she decides to watch both, switching to the other channel every time an advertisement starts.

At time $0$ Alyona turns on the TV and starts watching Stool Fight on channel A. If an advertisement starts on the channel she is watching, she switches to the other channel and watches that one. If she switches and an advertisement is already playing there, she does not switch back in hope that the ad on that channel ends sooner. At time $t$ Alyona turns off the TV and goes to sleep.

Given the ad schedules and the length of one advertisement, find how many time units Alyona watches each of the two series.

Input

The first line contains four integers $n$ , $m$ , $t$ , and $k$ ( $1 \leq n, m \leq 100000$ , $1 \leq t \leq 10^{18}$ , $1 \leq k \leq 10^9$ ): the number of ad breaks on channel A, the number of ad breaks on channel B, the time Alyona goes to sleep, and the length of one advertisement on either channel.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ( $1 \leq a_i \leq 10^{18}$ ), the times when an ad starts on channel A. They are strictly increasing, and $a_i + k < a_{i+1}$ , so the show airs for a positive amount of time between any two ads.

The third line contains $m$ integers $b_1, b_2, \ldots, b_m$ ( $1 \leq b_i \leq 10^{18}$ ), the times when an ad starts on channel B. They are strictly increasing, and the show airs for a positive amount of time between any two ads on channel B as well.

Output

Print two integers: the total time Alyona watches Stool Fight, followed by the total time she watches Domino Palace.

Hint

In the first example, ads start at the same time on both channels. Alyona switches channels at time 4, but she watches the ad for three time units. She switches again at time 8, does not wait for the ad to end, and goes to sleep.

In the second example, Alyona switches channels so that she never has to watch an ad.

Examples2

Example 1
Input
```
2 2 10 3
4 8
4 8
```
Expected output
```
4 1
```
Example 2
Input
```
6 5 10 1
1 3 5 7 9 11
2 4 6 8 10
```
Expected output
```
5 5
```