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^n ' buckets in the shop.They have to put the buckets in several rooms eually.

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^6)  and (1<= r <= 5000) where b^n is amount of buckets and r is amount 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^18) in each partition.

Output

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

The answer must be exists!!!

Example

Input:

2 3 5

3

2

4

4

Output:

3 1