import time
import random


def distribute(arr, x):
    total = sum(arr) + x
    I = sorted(range(len(arr)), key=arr.__getitem__)
    while I:
        minimum, additional = divmod(total, len(I))
        if arr[I[-1]] <= minimum:
            break
        total -= arr[I.pop()]
    for i in sorted(I):
        arr[i] = minimum
        if additional > 0:
            arr[i] += 1
            additional -= 1

def f(A, x):
  smallest = min(A)

  lo = smallest
  hi = smallest + x

  while lo < hi:
    mid = lo + (hi - lo) // 2

    can_reach = True
    temp = x

    for a in A:
      if a <= mid:
        diff = mid - a
        if diff > temp:
          can_reach = False
          break
        else:
          temp -= diff

    if can_reach:
      lo = mid + 1
    else:
      hi = mid

  target = lo - 1

  for i, a in enumerate(A):
    if a < target:
      x -= target - a
      A[i] = target

  if x:
    for i, a in enumerate(A):
      if a == target:
        A[i] += 1
        x -= 1
        if x == 0:
          break
  
  return A


n = 1000000


m = 20
x = int(random.random() * m)
A = [random.randint(0, m) for _ in range(n)]
A1 = A.copy()

t0 = time.time()
distribute(A, x)
print(time.time() - t0)


t0 = time.time()
f(A1, x)
print(time.time() - t0)

print(sorted(A) == sorted(A1))


m = 100000000
x = int(random.random() * m)
A = [random.randint(0, m) for _ in range(n)]
A1 = A.copy()

t0 = time.time()
distribute(A, x)
print(time.time() - t0)


t0 = time.time()
f(A1, x)
print(time.time() - t0)

print(sorted(A) == sorted(A1))