접기
시간 제한2초메모리 제한1024 MB
길이 10^9인 테이프 위 두 개의 서로 떨어진 빨간 구간이 주어질 때, 위치 x에서 접은 뒤 새 테이프에서 빨간 부분의 총 길이를 최대 10^6개의 질의마다 구한다.
문제
길이가 정확히 1미터(10^9 나노미터)인 투명한 테이프가 있다. 이 문제에서 모든 수는 정수이고, 수로 테이프 위의 위치를 나타낸다. 수 p는 테이프의 머리에서 p 나노미터 떨어진 지점의 위치를 나타낸다.
Bob은 염색의 대가라서 나노미터 단위까지 정확하게 테이프를 염색할 수 있다. Bob은 구간 [p1, q1]과 [p2, q2]를 빨간색으로 칠한다. p1과 q1 사이의 테이프는 빨간색이고, p2와 q2 사이의 테이프도 빨간색이다. 나머지 부분은 투명하게 남는다.
Bob의 실력을 검증하기 위해 우리는 테이프 접기의 대가인 Ben에게 도움을 청한다. Ben은 임의의 위치에서 테이프를 완벽하게 접을 수 있다. Ben이 x에서 테이프를 접으면, 어떤 점 p의 새 위치는 다음 중 하나가 된다.
- p = x이면 p는 테이프의 새 머리, 즉 0이 된다.
- p > x이면 p - x가 된다.
- p < x이면 x - p가 된다.
Ben이 테이프를 접은 뒤, 새 테이프에서 빨간색 부분의 전체 길이를 잰다. 빨간색 부분의 길이가 기대한 값과 같으면 Bob과 Ben 모두 대가라고 믿는다. 새 테이프의 어떤 위치의 색은 이전 테이프의 대응하는 위치들의 색으로 정해진다. 새 테이프의 어떤 위치에 대응하는 이전 테이프의 위치 중 하나라도 빨간색이면 그 위치는 빨간색이 된다.
Bob은 이미 테이프를 칠했고, Ben은 접을 위치를 제안했다. 빨간색으로 칠해진 기대 길이를 계산하는 프로그램을 작성하시오.
입력
첫째 줄에 공백으로 구분된 네 정수 p1, q1, p2, q2가 주어진다. Bob은 구간 [p1, q1]과 [p2, q2]를 칠했다. 둘째 줄에 정수 q가 주어지며, Ben이 q개의 제안을 했다는 뜻이다. 이어지는 q개의 줄에 각각 Ben이 접을 위치를 나타내는 정수 x가 하나씩 주어진다. q개의 제안은 서로 독립적이다. 한 제안에는 접는 점이 하나만 있다.
출력
각 위치마다 새 테이프에서 빨간색으로 칠해진 기대 전체 길이를 출력한다.
제한
- 0 ≤ p1 < q1 < p2 < q2 ≤ 10^9
- 0 ≤ x ≤ 10^9
- q ≤ 10^6