An owner of the godown of mangoes is facing a great problem. He has enough employer but being the amount of worst mango so much larger, they are in trouble to calculate. They have to do the operations in daily are given below:

1. There are bⁿ buckets in the shop. They have to put the buckets in several rooms equally.
2. Extra buckets contain worst mangoes. But sometimes extra buckets are not enough to store those.

These are enough hard to complete the task for the employers.

Input

The first line will contain b, n, r (1 ≤ b, n ≤ 10⁶)  and (1≤ r ≤ 5000) where bⁿ is the number of buckets and r is the number of rooms.

Second line will contain p (1≤ p ≤ 50) the partitions or places where the worst mangoes are.

Next p lines will contain the amount of worst mangoes (1≤ xi ≤ 10¹⁸) in each partition.

Output

Print the amount of extra buckets and amount of extra worst mangoes which are not enough to store in bucket equally.

The answer must exist!

Example

Input:
2 3 5
3
2
4
4

Output:
3 1

Note: The number of buckets are 2³ or 8. As there are 5 rooms, so after putting them equally in each room the extra buckets are 3. In three partitions or places total worst mangoes are 2+4+4 or 10. As there are 3 buckets so 10 % 3 or 1 mangoes is extra to store those in buckets equally. So the answer is 3 and 1, the number of extra buckets and mangoes.