ami ?có một dãy số nguyên \(a\) gồm \(N\) phần tử và một số \(k\). Các bạn được làm thao tác sau không quá \(m\) lần:

• Chọn một cặp số \((i , j)\) thoả điều kiện \(1 ≤ i, j ≤ N\) và \(a[i] ≥ k\). Sau đó, gán \(a[i] = a[i] - k\) và \(a[j] = a[j] + k\).

Hãy tìm cách tận dụng thao tác trên để sau khi chuyển đổi, giá trị \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\) là nhỏ nhất có thể.

Input

• Dòng đầu tiên chứa một số nguyên dương \(k\).
• Dòng thứ hai chứa một số nguyên dương \(m\).
• Dòng tiếp theo chứa một số nguyên dương \(N\).
• \(N\) dòng tiếp theo, mỗi dòng chứa một phần tử của \(a\).

Output

• \(1\) số nguyên dương là kết quả bài toán. Giá trị nhỏ nhất của \(max(a[1] , a[2] , ... , a[N]) - min(a[1] , a[2] , ... , a[N])\).

Example

2
1
3
2
2
3

1

1
1
3
2
3
4

0

Scoring

• Subtask \(1\): \(70\)% test có \(N\), \(m\) \(\leq 50\) và 1 ≤ \(k\) , \(a[i]\) ≤ \(10^9\).
• Subtask \(2\): \(30\)% test có \(N\), \(m\) \(\leq 5 * 10^4\) và 1 ≤ \(k\) , \(a[i]\) ≤ \(10^9\).