In the last war of PMP, he defeated all his opponents and advanced to the final round. But after the end of semi-final round evil attacked him from behind and killed him! God bless him. Before his death, PMP signed a contract with the bus rapid transit (BRT) that improves public transportations by optimizing time of travel estimation. You should help PMP finish his last contract. Each BRT line is straight line that passes n intersecting on its ways. At each intersection there is traffic light that periodically cycles between green and red. It starts illuminating green at time zero. During the green phase which lasts for g seconds, traffic is allowed to proceed. After the green phase the light changes to red and remains in this color for r seconds. During the red phase traffic is prohibited from proceeding. If a vehicle reaches the intersection exactly at a time when the light changes to red, it should stop, but the vehicle is clear to proceed if the light has just changed to green. All traffic lights have the same timing and are synchronized. In other words the period of red (and green) phase is the same for all of traffic lights and they all start illuminating green at time zero. The BRT Company has calculated the time that a bus requires to pass each road segment. A road segment is the distance between two consecutive traffic lights or between a traffic light and source (or destination) station. More precisely BRT specialists provide n + 1 positive integers l i , the time in seconds that a bus needs to traverse i -th road segment in the path from source to destination. The l 1 value denotes the time that a bus needs to pass the distance between source and the first intersection. The l n + 1 value denotes the time between the last intersection and destination. In one day q buses leave the source station. The i -th bus starts from source at time t i (in seconds). Decision makers of BRT Company want to know what time a bus gets to destination? The bus is co