Box Office

Problem Description

Rar the Cat is bored and is loitering at the box office of a certain cinema. There are a 3 queues in the box office and movie go-ers queue at either one of these 3 queues in order to obtain a movie ticket. Initially, all the 3 queues are empty.

Thanks to long hours of loitering, Rar the Cat has made the following observation regarding the 3 queues:

1. Queue 1 is manned by a (relatively) short customer service staff. Thus, he serves customers from a shorter height to a taller height. He will always serve the shortest customer in his queue at any point in time. Queue 1 takes A time units to serve a single customer.
2. Queue 2 is manned by a customer service staff that is average in height. Hence, he does not seem to be biased and will always serve the customer that started queueing first. In other words, this resembles a normal queue. Queue 2 takes B time units to serve a single customer.
3. Queue 3 is manned by a (relatively) tall customer service staff. In contrast to Queue 1, he serves customers from a taller height to a shorter height. He will always serve the tallest customer in his queue at any point in time. Queue 3 takes C time units to serve a single customer.

During his time there, he has observed N customers buying tickets from the box office. Below is a summary of his observation:

• When entering the box office, the customer will go to the queue with the shortest length at that point in time.
• In the event that more than one queue has the shortest length, the customer will join the queue with a lower queue number. (Eg: Prefers Queue 1 over Queue 2 and Queue 2 over Queue 3)

At the start of each time unit, if the queue is ready to serve another customer and there is more than one person in the queue, the queue will serve those already in the queue first. For example, if there is a person with height 2 at Queue 1 and another person with height 1 that just joins the queue, the person with height 2 will be served instead. However, if the queue is originally empty, the new incoming person will be served immediately instead.

Rar the Cat has recorded the height of each customer, as well as when they entered the box office. The height of the i^th customer is H_i and he/she entered the box office at time T_i, where T_i is the number of time unit elasped since Rar the Cat started his observation.

However, Rar the Cat did not stay long enough for all the customers he has recorded to finish with the ticket purchase. Being a curious cat, he still wants to know what time will each customer obtain their tickets (get served by the queue they are queuing at). Assume that there will be no additional customers that enter after the N customers.

Limits

For all testcases: 0 < A, B, C, T_i, H_i ≤ 10⁹. In addition, there will be no 2 customers with the same value of T_i or H_i

Subtask 1 (13%): 1 ≤ N ≤ 3.

Subtask 2 (38%): 1 ≤ N ≤ 2000.

Subtask 3 (20%): 1 ≤ N ≤ 200000. All queues will serve at the same speed, A = B = C.

Subtask 4 (29%): 1 ≤ N ≤ 200000.

Subtask 5 (0%): Sample Testcases.

Input

The first line of input will contain one integer, N.

The second line of input will contain three integers, A, B and C. These 3 integers indicate how long each queue takes to serve one customer, respectively.

The following N lines of input will contain 2 integers each, with the i^th line being T_i then H_i, describing the i^th customer.

Output

The output should contain N integers, one per line.

The i^th integer should indicate the time customer i has obtained their tickets at the box office. The integer should be the total number of time units elasped after Rar the Cat has started his observation. This will include the amount of time the customer has waited in the queue, as well as the amount of time the queue takes to serve him.

You are reminded to use 64-bit integers.

Sample Testcase 1

Input

6
5 3 4
1 5
2 4
3 3
4 2
5 1
6 7

Output

6
5
7
11
8
16

Explanation

Customer 1 enters the box office at time unit 1 and goes to queue 1, he is instantly served as there is nobody else in the queue. Queue 1 takes 5 time units to serve customer 1, so he receives his ticket at time 6.

Customer 2 enters the box office at time unit 2 and goes to queue 2, he is instantly served as there is nobody else in the queue. Queue 2 takes 3 time units to serve customer 2, so he receives his ticket at time 5.

Customer 3 enters the box office at time unit 3 and goes to queue 3, he is instantly served as there is nobody else in the queue. Queue 3 takes 4 time units to serve customer 3, so he receives his ticket at time 7.

Customer 4 enters the box office at time unit 4 and goes to queue 1 as all the queues have a length of 1. After waiting till time 6, he will be served and receives his ticket at time 11.

Customer 5 enters the box office at time unit 5 and goes to queue 2 as it is empty. He is instantly served and will be done at time 8.

Customer 6 enters the box office at time unit 6 and goes to queue 1 as all the queues have a length of 1. After waiting till time 11, he will be served and receives his ticket at time 16.