Java Certification#530

Java Certification

1 second

64 megabytes

Very hard

You have just completed the Java Certification exam, which contained $n$ questions. You have a scorecard that explains your performance.

You have correctly answered $78$ questions out of $87$ .

From this scorecard, you can infer that the questions are divided into $m$ categories (in the above example, $m = 6$ m = 6). Each category contains $n_{i}$ n_i questions ( $1 \leq n_{i} \leq n$ 1 \leq n_i \leq n), so that

i = 1 \sum m n_{i} = n .

\sum_{i=1}^m n_i = n.

You know that you have correctly answered $k$ questions out of $n$ (in the example above, $k = 78$ k = 78 and $n = 87$ n = 87), so you can easily find the number of incorrect answers $w = n - k$ w = n - k (in the above example, $w = 9$ w = 9).

You remember several questions for which you were unsure about the answers and can guess which category they belong to. To find out whether your answers to those questions were right or wrong, you want to know how many incorrect answers you had in each category.

Let $w_{i}$ w_i ( $0 \leq w_{i} \leq n_{i}$ 0 \leq w_i \leq n_i) be the number of incorrect answers in the $i$ -th category, and

i = 1 \sum m w_{i} = w .

\sum_{i=1}^m w_i = w.

From the scorecard, you know the percentage of correct answers in each category. That is, for each $i$ from $1$ to $m$ , you know the value of

100 \cdot \frac{n _{i} - w _{i}}{n _{i}}

100 \cdot \frac{n_i - w_i}{n_i}

rounded to the nearest integer. A value with a fractional part of $0.5$ is rounded to the nearest even integer.

It may not be possible to uniquely determine the values of $w_{i}$ w_i and $n_{i}$ n_i. However, you assume the questions are distributed among the categories as uniformly as possible. Find valid values of $w_{i}$ w_i and $n_{i}$ n_i that minimize the difference between the maximum and minimum value of $n_{i}$ n_i. If there are still multiple possible valid sets of $w_{i}$ w_i and $n_{i}$ n_i, output any of them.

Input

The first line contains three integers $k$ , $n$ , and $m$ : the number of correct answers, the total number of questions, and the number of categories ( $0 \leq k \leq n$ 0 \leq k \leq n, $1 \leq n \leq 100$ 1 \leq n \leq 100, $1 \leq m \leq 10$ 1 \leq m \leq 10).

The next $m$ lines each contain a single integer from $0$ to $100$ (inclusive): the percentage of correct answers in each category.

The input always corresponds to some valid set of $w_{i}$ w_i and $n_{i}$ n_i.

Output

Print $m$ lines. On each line, output two integers $w_{i}$ w_i and $n_{i}$ n_i: the number of incorrect answers and the total number of questions in the $i$ -th category, satisfying the constraints described in the statement.

Examples

Example 1