Arrival of the Saboteurs

0

0 votes
Medium
Problem

The Saboteurs have arrived at the town center of the Saracens. Without any further delay, the Saboteurs are assigned their first task which goes as follows:-

There exists a linked list that consists of a straight path of K nodes followed by a loop of L nodes. More precisely, the nodes of the path are numbered from 1 to K and the nodes of the loop are numbered from K + 1 to K + L. Note that the outgoing edge from node K + L is incident on node K + 1. Two pointers start moving from node 1 at time t = 0 (seconds), with speeds A and B (nodes/second). Given Q queries, each query consisting of a positive integer T, the task is to print the number of times the pointers have met each other from t = 1 to t = T (seconds).

Note that the two pointers are considered to have met each other if and only if they are at the same node at the same integer time t. Also note that the query considers t starting from 1, hence the pointers meeting initially at node 1 should not be considered in the answer.

You being the captain of the Saboteurs, help the Saboteurs to solve the problem.

Input Format

The first line contains 4 integers A, B, K and L as described in the problem statement. The second line contains a single integer Q denoting the number of queries. Each of the following Q lines consist of a single integer T as described in the problem statement.

Output Format

Print Q lines, each line consisting of an integer denoting the answer.

Constraints

1A,B109

0K109

2L109

1Q105

1T1018

Time Limit: 2
Memory Limit: 256
Source Limit:
Explanation

Let the pointer of speed 1 be denoted by P1 and let the pointer of speed 2 be denoted by P2.

At time t = 1, P1 is at node 2 and P2 is at node 3.

At time t = 2, P1 is at node 3 and P2 is at node 2.

At time t = 3, P1 is at node 4 and P2 is at node 4.

Hence, the answer.

Editor Image

?