output_description: Find the minimum possible absolute difference of the maximum and the minimum
  among P,Q,R,S.
  
  * * *
input_description: Input is given from Standard Input in the following format:
  
      
      
      N
      A_1 A_2 ... A_N
attempt: #!/usr/bin/env python
  # coding: utf-8
  
  
  def ri():
      return int(input())
  
  
  def rl():
      return list(input().split())
  
  
  def rli():
      return list(map(int, input().split()))
  
  
  def calc(n):
      s = sum(map(int, str(n)))
      return n / s
  
  
  def main():
      k = ri()
      cand = list(range(1, 10))
      last = 9
      for n in range(1, 15):
          pow10n = pow(10, n)
          for d in range(1, 10):
              lim = (d + 1) * pow10n
              e = 0
              while True:
                  e1 = d * pow10n + e * (last + 1) + last
                  if e1 >= lim:
                      break
                  e2 = e1 + (last + 1)
                  if calc(e1) > calc(e2):
                      last = last * 10 + 9
                      e = 0
                      continue
                  cand.append(e1)
                  e += 1
      print("\n".join(map(str, cand[:k])))
  
  
  if __name__ == "__main__":
      main()
  
  """
  1 1.0
  2 1.0
  3 1.0
  4 1.0
  5 1.0
  6 1.0
  7 1.0
  8 1.0
  9 1.0
  19 1.9
  29 2.6363636363636362
  39 3.25
  49 3.769230769230769
  59 4.214285714285714
  69 4.6
  79 4.9375
  89 5.235294117647059
  99 5.5
  199 10.473684210526315
  299 14.95
  399 19.0
  499 22.681818181818183
  599 26.043478260869566
  699 29.125
  799 31.96
  899 34.57692307692308
  999 37.0
  1099 57.8421052631579
  1199 59.95
  1299 61.857142857142854
  1399 63.59090909090909
  1499 65.17391304347827
  1599 66.625
  1699 67.96
  1799 69.1923076923077
  1899 70.33333333333333
  1999 71.39285714285714
  2999 103.41379310344827
  3999 133.3
  4999 161.25806451612902
  5999 187.46875
  6999 212.0909090909091
  7999 235.26470588235293
  8999 257.1142857142857
  9999 277.75
  10999 392.82142857142856
  11999 413.7586206896552
  12999 433.3
  13999 451.5806451612903
  14999 468.71875
  15999 484.8181818181818
  16999 499.97058823529414
  17999 514.2571428571429
  18999 527.75
  19999 540.5135135135135
  20999 724.1034482758621
  21999 733.3
  22999 741.9032258064516
  23999 749.96875
  24999 757.5454545454545
  25999 764.6764705882352
  26999 771.4
  27999 777.75
  28999 783.7567567567568
  29999 789.4473684210526
  39999 1025.6153846153845
  49999 1249.975
  59999 1463.3902439024391
  69999 1666.642857142857
  79999 1860.4418604651162
  89999 2045.4318181818182
  99999 2222.2
  109999 2972.945945945946
  119999 3157.8684210526317
  129999 3333.3076923076924
  139999 3499.975
  149999 3658.512195121951
  159999 3809.5
  169999 3953.4651162790697
  179999 4090.8863636363635
  189999 4222.2
  199999 4347.804347826087
  209999 5526.289473684211
  219999 5641.0
  229999 5749.975
  239999 5853.634146341464
  249999 5952.357142857143
  259999 6046.488372093023
  269999 6136.340909090909
  279999 6222.2
  289999 6304.326086956522
  299999 6382.95744680851
  309999 7948.692307692308
  319999 7999.975
  329999 8048.756097560976
  339999 8095.214285714285
  349999 8139.511627906977
  359999 8181.795454545455
  369999 8222.2
  379999 8260.847826086956
  389999 8297.851063829787
  399999 8333.3125
  499999 10204.061224489797
  599999 11999.98
  699999 13725.470588235294
  799999 15384.596153846154
  899999 16981.11320754717
  999999 18518.5
  """
  
problem_description: Statement
  
  Snuke has an integer sequence A of length N.
  
  He will make three cuts in A and divide it into four (non-empty) contiguous
  subsequences B, C, D and E. The positions of the cuts can be freely chosen.
  
  Let P,Q,R,S be the sums of the elements in B,C,D,E, respectively. Snuke is
  happier when the absolute difference of the maximum and the minimum among
  P,Q,R,S is smaller. Find the minimum possible absolute difference of the
  maximum and the minimum among P,Q,R,S.
samples: [{"input": "5\n    3 2 4 1 2", "output": "2\n    \n\nIf we divide A as B,C,D,E=(3),(2),(4),(1,2), then P=3,Q=2,R=4,S=1+2=3. Here,\nthe maximum and the minimum among P,Q,R,S are 4 and 2, with the absolute\ndifference of 2. We cannot make the absolute difference of the maximum and the\nminimum less than 2, so the answer is 2.\n\n* * *"}, {"input": "10\n    10 71 84 33 6 47 23 25 52 64", "output": "36\n    \n\n* * *"}, {"input": "7\n    1 2 3 1000000000 4 5 6", "output": "999999994"}]