종이 눈송이

종이 눈송이를 만들려면 종이를 여러 곳에서 접은 다음 접힌 종이의 일부를 잘라낸다. 종이를 펼치면 아주 멋진 무늬가 나타날 수도 있다. 물론 접는 위치와 자르는 위치를 잘 골랐을 때의 이야기다.

Samantha는 최근에 이 취미를 시작했는데 "현대 미술" 풍으로 접근한다. 우선 길이가 $L$ 피코미터인 종이 띠를 접는 방법을 탐구한다(Samantha는 접는 위치와 자르는 위치를 아주 정밀하게 측정하는 것을 좋아한다). 종이 띠를 실수선 위에 놓는데, 한쪽 끝은 $0$에, 다른 쪽 끝은 $L$에 둔다. 점 $0$에 있는 왼쪽 끝은 이 점에 고정되어 있고, $L$ 위치에 있는 다른 끝은 느슨한 끝이다.

그다음 Samantha는 일련의 접기를 한다. 첫 번째 접기에서는 느슨한 끝에서 $f_1$ 피코미터 떨어진 곳에서 종이에 접는 선을 만들고 느슨한 끝을 이 접는 선 위로 접는다. 이제 느슨한 끝은 왼쪽을 향한다. 두 번째 접기에서는 종이의 위쪽 부분을 느슨한 끝에서 $f_2$ 피코미터 떨어진 곳에서 접고($f_2 < f_1$), 종이의 위쪽 부분을 이 접는 점 위로 다시 오른쪽으로 접는다. 이제 느슨한 끝은 오른쪽을 향한다.

Samantha는 이런 식으로 왼쪽과 오른쪽을 번갈아 가며 접는다. 각 단계에서 종이의 위쪽 부분을 느슨한 끝에서 $f_i$ 피코미터 떨어진 곳에서 접고($f_i < f_{i-1}$), 느슨한 끝을 접는 선 위로 접는다.

이제 종이를 $M$개의 서로 다른 위치에서 자르면 종이가 $M+1$개의 더미로 나뉜다. 각 더미에는 0개 이상의 종이 층이 들어 있다. 아래 그림은 첫 번째 예제 입력의 접힌 종이, 자르는 위치(실선), 그리고 종이가 접힌 $x$ 위치(점선)를 나타낸다.

각 $M+1$개의 더미에 들어 있는 종이의 총 길이는 얼마인가?

입력의 첫째 줄에는 세 정수 $N$ ($1 \leq N \leq 10^5$), $M$ ($1 \leq M \leq 10^5$), $L$ ($2 \leq L \leq 10^{18}$)이 주어진다. $N$은 접는 횟수, $M$은 자르는 횟수, $L$은 종이의 길이를 피코미터 단위로 나타낸 값이다.

둘째 줄에는 접는 위치가 주어진다. 이 줄에는 $N$개의 정수 $f_1, f_2, \ldots, f_N$이 주어지며, $i$번째 접기가 느슨한 끝에서 $f_i$ 피코미터 떨어진 곳에서 이루어졌음을 나타낸다. 이 값들은 $1 \leq f_N < f_{N-1} < \cdots < f_1 < L$을 만족한다.

셋째 줄에는 자르는 위치가 주어진다. 이 줄에는 $M$개의 정수 $c_1, c_2, \ldots, c_M$이 주어지며, $i$번째 자르기가 고정된 점에서 $c_i$ 피코미터 떨어진 곳에서 이루어졌음을 나타낸다. 이 값들은 $-10^{18} \leq c_1 < c_2 < \cdots < c_M \leq 10^{18}$을 만족한다.

각 $M+1$개의 더미에 들어 있는 종이의 총 길이를 왼쪽에서 오른쪽 순서로 출력한다.