Data Center Service Deployment

GongRuan Software operates a number of services worldwide in n data centers. Each data center initially has a certain number of available machines. For security and redundancy, each service is deployed as one or more replicas, with each replica running in a different data center and requiring the same number of machines.

When launching a new service i, the company needs to deploy c_i replicas, each requiring m machines. The procedure is as follows:

1. Sort the data centers in non-increasing order by the number of available machines. In case of ties, the data center with the smaller index is considered first.
2. Select the first c_i data centers in this order and allocate m machines from each.

After deploying s services (with each service having its own parameters c_i and m), output the remaining number of machines in each data center.

The formulas used are given in \(\LaTeX\):

• For service \(i\): allocate from the top \(c_i\) data centers after sorting by available machines.
• For each selected data center, update the available machines as: \(\text{machines} = \text{machines} - m\).

inputFormat

The input is given via standard input and has the following format:

n s
A1 A2 ... An
c1 m1
c2 m2
...
cs ms

Where:

• n is the number of data centers.
• s is the number of services to be launched.
• The second line contains n integers \(A_1, A_2, ..., A_n\) representing the initial number of available machines in each data center.
• Each of the following s lines contains two integers: \(c_i\) (the number of replicas for service \(i\)) and \(m\) (the number of machines required per replica).

outputFormat

Print a single line containing n integers separated by spaces. These integers represent the remaining number of machines in each data center in the original order.

sample

3 2
10 20 30
2 5
1 10

10 15 15