hanzch   1년 전

캠퍼스

시간 제한 메모리 제한
1 초 512 MB

문제

바이트버그 대학교의 새 캠퍼스 건물은 1층부터 n층까지 번호가 매겨진 n개의 층이 있습니다. 학생들의 방은 여러 개의 출입구에 위치해 있습니다.

각 출입구에서 k의 배수인 층에는 x개의 방이 있고, 나머지 층에는 y개의 방이 있습니다.

각 출입구 내의 방들은 연속된 자연수로 번호가 매겨져 있습니다. 1층의 방 번호가 해당 출입구에서 가장 작은 값을 가지며, 그 다음으로 2층의 방 번호가 이어지는 식입니다. 첫 번째 출입구의 방은 1번부터 시작하며, 각 다음 출입구의 방 번호는 이전 출입구의 최대 방 번호 다음 숫자부터 시작합니다.

그림 1은 n = 7층, 3개의 출입구, k = 3, x = 2, y = 3인 건물의 방 번호를 보여줍니다.

층 출입구 1 출입구 2 출입구 3
7층 17, 18, 19 36, 37, 38 55, 56, 57
6층 15, 16 34, 35 53, 54
5층 12, 13, 14 31, 32, 33 50, 51, 52
4층 9, 10, 11 28, 29, 30 47, 48, 49
3층 7, 8 26, 27 45, 46
2층 4, 5, 6 23, 24, 25 42, 43, 44
1층 1, 2, 3 20, 21, 22 39, 40, 41

캠퍼스 관리부는 학생들의 입주를 조직하기 위해 방 번호로 해당 방이 위치한 층을 신속하게 확인해야 합니다.

주어진 n, k, x, y 값과 방 번호들에 대해, 각 방이 위치한 층을 결정하는 프로그램을 작성해야 합니다.

입력

입력 파일의 첫 번째 줄에는 자연수 n, k, x, y가 포함되어 있습니다 (1 ≤ n ≤ 109, 1 ≤ k ≤ n, 1 ≤ x, y ≤ 109). 인접한 숫자들은 정확히 하나의 공백으로 구분됩니다.

두 번째 줄에는 층을 결정해야 하는 방 번호의 개수인 자연수 q가 포함되어 있습니다 (1 ≤ q ≤ 1000).

세 번째 줄에는 q개의 정수 a1, a2, …, aq가 포함되어 있습니다 - 방 번호들입니다 (1 ≤ ai ≤ 1018). 건물에 충분히 많은 출입구가 있어서 주어진 모든 방 번호가 존재한다고 가정할 수 있습니다.

출력

q개의 숫자를 출력해야 하며, 각각 한 줄에 하나씩 출력합니다. 입력 파일의 각 방 번호에 대해 해당 방이 위치한 층의 번호를 출력해야 합니다.

서브태스크

번호 배점 제한
1 31 1 ≤ n ≤ 10, 1 ≤ x, y ≤ 10, q = 1, 1 ≤ ai ≤ 100
2 19 1 ≤ n ≤ 107, 1 ≤ x, y ≤ 109, q = 1, 1 ≤ ai ≤ 107
3 16 1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109, x = y, 1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018
4 34 1 ≤ n ≤ 109, 1 ≤ x, y ≤ 109, 1 ≤ q ≤ 1000, 1 ≤ ai ≤ 1018

예제

입력 1

7 3 2 3
4
1 19 20 50

출력 1

1
7
1
5

댓글을 작성하려면 로그인해야 합니다.