29156번 - 탭 UI

문제

탭 UI는 여러 탭이 일렬로 나열되어 특정 탭을 클릭하면 해당 탭에 대한 내용을 확인할 수 있는 UI(User Interface)이다. 화면 내에 있는 탭은 노출되고 좌우로 화면을 벗어난 탭은 노출되지 않으며 사용자가 화면을 스크롤하면 전체 탭이 이동하여 화면에 노출되는 탭이 변화한다. 사용자는 화면에 노출된 탭 중에서 원하는 탭을 클릭하여 내용을 확인할 수 있다. 각 탭은 길이를 가지며 인접한 탭 사이 간격은 없는 것으로 생각한다.

전체 탭이 왼쪽으로 이동하는 방향을 양의 방향이라 하고, 전체 탭이 오른쪽으로 이동하는 방향을 음의 방향이라 하자. 위치 $x$에서 양의 방향으로 $a$만큼 이동하면 위치는 $x+a$가 되고, 위치 $x$에서 음의 방향으로 $a$만큼 이동하면 위치는 $x-a$가 된다. 가장 왼쪽에 있는 탭의 왼쪽 끝과 화면의 왼쪽 끝이 일치하는 순간의 위치는 0ドル$이다.

• 위 그림의 초기 화면에서는 왼쪽에서부터 첫 번째 탭인 “DP” 탭이 화면 왼쪽으로 벗어나 있고, 왼쪽에서부터 두 번째 탭인 “그리디” 탭의 왼쪽 끝과 화면의 왼쪽 끝이 일치한다. 이때 위치는 2ドル$이다.
• 초기 화면에서 “그리디” 탭의 길이인 2ドル$만큼 양의 방향으로 이동하면 “그리디” 탭이 화면 왼쪽으로 벗어나고, 왼쪽에서부터 세 번째 탭인 “그래프” 탭의 왼쪽 끝과 화면의 왼쪽 끝이 일치하게 된다. 이때 위치는 4ドル$가 된다.
• 초기 화면에서 “DP” 탭의 길이인 2ドル$만큼 음의 방향으로 이동하면 “DP” 탭의 화면 왼쪽 끝과 화면의 왼쪽 끝이 일치하게 된다. 이때 위치는 0ドル$이 된다.

탭 UI의 특징은 기본적으로 특정 탭을 클릭하면 해당 탭의 중앙과 화면의 중앙이 일치하도록 전체 탭이 이동한다는 것이다. 그러나 이동에 제한이 있기 때문에 어떤 탭은 클릭해도 해당 탭의 중앙과 화면의 중앙이 일치하지 않을 수 있다. 탭의 이동은 다음의 세 가지 제한을 가진다.

• 가장 왼쪽에 있는 탭의 왼쪽 끝과 화면의 왼쪽 끝이 일치하는 순간 더 이상 음의 방향으로 이동하지 않는다.
• 가장 오른쪽에 있는 탭의 오른쪽 끝과 화면의 오른쪽 끝이 일치하는 순간 더 이상 양의 방향으로 이동하지 않는다.
• 모든 탭의 길이의 합이 화면의 길이보다 작다면, 가장 왼쪽에 있는 탭의 왼쪽 끝과 화면의 왼쪽 끝이 일치하는 순간 더 이상 양의 방향으로 이동하지 않는다.

탭을 클릭하면 해당 탭의 중앙이 화면의 중앙과 일치하도록 하는 방향으로 이동하다 더 이상 이동할 수 없다면 그 위치에서 멈춘다. 사용자가 탭을 클릭한 순서대로, 각 탭을 클릭하고 난 직후의 위치를 구하시오.

입력

첫째 줄에 탭의 개수 $N$이 주어진다. $(1\leq N \leq 100,000円)$

둘째 줄부터 $N$개의 줄에 걸쳐 $i$번째 줄에는 $i$번 탭의 길이 $l_{i}$가 정수로 주어진다. $i$번 탭은 왼쪽에서부터 $i$번째 탭이다. $(1\leq l_{i} \leq 10,000円)$

그다음 줄에 화면의 길이 $L$이 정수로 주어진다. $(1\leq L \leq 10^9)$

그다음 줄에 사용자가 탭을 클릭하는 횟수 $Q$가 주어진다. $(1\leq Q \leq 500,000円)$

그다음 줄부터 $Q$개의 줄에 걸쳐 사용자가 클릭한 탭의 번호가 탭을 클릭한 순서대로 주어진다.

출력

사용자가 탭을 클릭한 순서대로, 각 줄에 각 탭을 클릭하고 난 직후의 위치를 소수점 셋째 자리에서 버림하여 출력한다.

제한

힌트