#takes n integers as input, stores them in a list and returns the list
def input_list(n):
  lst=[]
  while n>0:
    lst.append(int(input()))
    n-=1
  return lst


#returns the sum of the numbers in list a[]
#version 1: iteration by item
def sum_list_1(a):
  _sum=0
  for num in a:
    _sum+=num
  return _sum


#returns the sum of the numbers in list a[]
#version 2: iteration by index
def sum_list_2(a):
  _sum=0
  for i in range(len(a)):
    _sum+=a[i]
  return _sum


#write it yourself
#return the sum of the squares of the numbers in list a[]
#for example, sum_square([1,2,3]) should return 14
#def sum_square(a):




#write it yourself
#return the average of the numbers in list a[]
#for example, average([1,2,3]) should return 2.0
#def average(a):




#write it yourself
#return the minimum number in list a[]
#for example, minimum([1,2,3]) should return 1
#def minimum(a):




#write it yourself
#return the number of odd numbers in list a[]
#for example, count_odd([1,2,3]) should return 2
#def count_odd(a):




#write it yourself
#return the sum of the even numbers in list a[]
#for example, sum_even([1,2,3,4]) should return 6
#def sum_even(a):




#write it yourself
#return the sum of the numbers in list a[] until the first negative number is found (excluding the negative number)
#for example, sum_until_negative([1,2,3,-4,5,6]) should return 6
#def sum_until_negative(a):




#returns a list of consecutive sums
#ret[i] contains the sum of the first i+1 elements of list a[]
#for example consecutive_sum_1([1,2,3,4]) returns [1,3,6,10]
#version 1 uses the sum_list_1() function and slicing operator
def consecutive_sum_1(a):
  ret=[]
  for i in range(len(a)):
    ret.append(sum_list_1(a[0:i+1]))
  return ret


#returns a list of consecutive sums
#ret[i] contains the sum of the first i+1 elements of list a[]
#for example consecutive_sum_2([1,2,3,4]) returns [1,3,6,10]
#version 2 builds ret[] incrementally and thus is more efficient
def consecutive_sum_2(a):
  ret=[]
  _sum=0
  for num in a:
    _sum+=num
    ret.append(_sum)
  return ret


#returns a list of first n fibonacci numbers
def fibonacci(n):
  fib=[]
  fib.append(0)
  fib.append(1)
  for i in range(2,n):
    fib.append(fib[i-1]+fib[i-2])
  return fib


#write it yourself
#return a list of first n prime numbers
#def prime(n):




#write it yourself
#return the largest (having maximum length) sublist of a[] having only nonnegative elements(sublist of a list is similar to substring of a string)
#for example, largest_nonnegative_sublist([2,-2,-1,1,2,3,-2,1,1,1,2,-1,-2,1]) should return [1,1,1,2]
#def largest_nonnegative_sublist(a):




#write it yourself
#return the sublist of a[] having maximum sum
#for example, maximum_sum_sublist([2,-3,1,2,3,-5,1,1,1,1]) should return [1,2,3]
#def maximum_sum_sublist(a):




#sorts a list of integers in ascending order using bubble sort algorithm
#bubble_sort() returns nothing, it just modifies the argument list a[]
#see the animation in the wiki page to have a clearer idea: http://en.wikipedia.org/wiki/Bubble_sort
def bubble_sort(a):
  for i in range(len(a)-2,-1,-1):
    swapped=False
    for j in range(0,i+1):
      if a[j]>a[j+1]:
        a[j],a[j+1]=a[j+1],a[j]
        swapped=True
        #print(a)   #comment in this line to see a simulation of the bubble sort algorithm
    if not swapped:
      return


#sorts a list of integers in ascending order using selection sort algorithm
#selection_sort() returns nothing, it just modifies the argument list a[]
#see the animation in the wiki page to have a clearer idea: http://en.wikipedia.org/wiki/Selection_sort
def selection_sort(a):
  for i in range(len(a)-1):
    min_index=i
    for j in range(i+1,len(a)):
      if a[j]<a[min_index]:
        min_index=j
    a[i],a[min_index]=a[min_index],a[i]
    #print(a)   #comment in this line to see a simulation of the selection sort algorithm


#write it yourself
#sort a list of integers in ascending order using counting sort algorithm
#assume that the elements of a[] are integers in range(10)
#create a list count[] of length 10, where count[i] holds the number of occurrences of i in a[], for 0<=i<=9
#for example, for a=[3,5,1,2,3,7,0,0,9,8,4,3,5,6,2], count=[2,1,2,3,1,2,1,1,1,1], because 0 appears twice in a[], 1 appears once in a[] and so on
#note that, sum_list_1(count) equals len(a) (why?)
#now create another list ret[] by appending count[i] number of i's, for 0<=i<=9
#for example, the first two elements of ret[] are 0, the next element is 1, the next two elements are 2 and so on
#thus ret[] is the sorted version of a[]
#note that, counting_sort() can not be used to sort non-integral values and the range of integers should be small and known in advance (why?)
#def counting_sort(a):




#takes n strings as input, stores them in a list and returns the list
def input_str_list(n):
  lst=[]
  while n>0:
    lst.append(input())
    n-=1
  return lst


#write it yourself
#return the number of strings in list s[] which have length equal to c
#for example, len_count(["abc","de","fghi","jk","l"],2) should return 2
#you can use the input_str_list() function above to take a list of strings as input
#def len_count(s,c):




#s is a string containing words separated by a single space
#returns a string containing the words of s in reverse order
#for example, reverse_sentence("this is good") will return "good is this"
def reverse_sentence(s):
  words=s.split()
  words.reverse()
  return " ".join(words)
    

#write it yourself
#take a string s as input, which contains words separated by a single space
#return a string containing each word in its' position but individually reversed
#for example, reverse_words("this is good") should return "siht si doog"
#def reverse_words(s):




#takes n*m integers as input, stores them in a 2D list of n rows and m columns and returns the list
def input_2D_list(n,m):
  lst=[]
  while n>0:
    lst.append(input_list(m))
    n-=1
  return lst


#adds two matrices and returns the resultant matrix
def add_matrices(a,b):
  n=len(a)      
  m=len(a[0])
  c=[]
  for i in range(n):
    tmp=[]
    for j in range(m):
      tmp.append(a[i][j]+b[i][j])
    c.append(tmp)
  return c


#multiplies two matrices and returns the resultant matrix
def multiply_matrices(a,b):
  p=len(a)
  q=len(a[0])
  r=len(b[0])
  c=[]
  for i in range(p):
    tmp=[]
    for j in range(r):
      _sum=0
      for k in range(q):
        _sum+=a[i][k]*b[k][j]
      tmp.append(_sum)
    c.append(tmp)
  return c


#write it yourself
#return a list containing the maximum number of each row of a 2D list a[][]
#for example, row_maximum([3,1,2],[-3,-1,-2],[1,0,1],[0,0,0]) should return [3,-1,1,0]
#def row_maximum(a):




#write it yourself
#a[] is a list of positive integers 
#return a 2D list of integers ret[][], where ret[i][j] holds the sum of the numbers in the sublist a[i:j] if i<j, 0 otherwise
#for example, sublist_sum([1,2,3]) should return [[0,1,3,6],[0,0,2,5],[0,0,0,3]]
#def sublist_sum(a):




#write it yourself
#flatten a list a[] of arbitrary dimension
#for example, flatten([1,[2,3],[[[1]],3],[[[[[1]]]]],2,[1,[2,[3]]]]) should return [1,2,3,1,3,1,2,1,2,3]
#you might need to use recursion and a global list
#def flatten(a):




#returns true if a[][] is an identity matrix, false otherwise
# http://en.wikipedia.org/wiki/Identity_matrix
def isIdentity(a):
  n=len(a)
  for i in range(n):
    for j in range(n):
      if i==j:
        if a[i][j]!=1:
          return False
      else:
        if a[i][j]!=0:
          return False
  return True


#returns the transpose of matrix a[][]
# http://en.wikipedia.org/wiki/Transpose
def transpose(a):
  n=len(a)
  m=len(a[0])
  c=[]
  for i in range(m):
    tmp=[]
    for j in range(n):
      tmp.append(a[j][i])
    c.append(tmp)
  return c


#write it yourself
#return true if 2D matrix a[][] is symmetric, false otherwise
# http://en.wikipedia.org/wiki/Symmetric_matrix
#write 2 versions with and without using the transpose() function
#def isSymmetric(a):




#write it yourself
#return true if 2D matrix a[][] is upper triangular, false otherwise
# http://en.wikipedia.org/wiki/Triangular_matrix
#def isUpperTriangular(a):




#prints 2D list a[][]
def print_2D_list(a):
  n=len(a)
  m=len(a[0])
  for i in range(n):
    for j in range(m):
      print(repr(a[i][j]).ljust(4),end="")
    print()
  print()


#returns the number of distinct elements in a list of integers a[]
def distinct_count(a):
  lst=[]
  for num in a:
    if num not in lst:
      lst.append(num)
  return len(lst)


#write it yourself
#return the number of distinct elements in a sorted list of integers a[]
#write a more efficient version than the previous one
#def distinct_count_sorted(a):




#for practice problems on dictionary, solve problem number 1, 2 and 5 in the following link
# http://interactivepython.org/runestone/static/thinkcspy/Dictionaries/Exercises.html


#returns a dictionary containing the unique substrings of string s along with the number of times each substring appears in s
#for example unique_substring("abab") will return {'ba': 1, 'ab': 2, 'aba': 1, 'bab': 1, 'b': 2, 'a': 2, 'abab': 1}
def unique_substring(s):
  dct={}
  for i in range(len(s)):
    for j in range(i+1,len(s)+1):
      if s[i:j] not in dct:
        dct[s[i:j]]=1
      else:
        dct[s[i:j]]=dct[s[i:j]]+1
  return dct


#tester of some functions
def main():
  #test sum_list_1() and sum_list_2()
  #n=int(input())
  #a=input_list(n)
  #print(a)
  #print(sum_list_1(a))
  #print(sum_list_2(a))

  #test consecutive_sum_1() and consecutive_sum_2()
  #n=int(input())
  #a=input_list(n)
  #print(a)
  #print(consecutive_sum_1(a))
  #print(consecutive_sum_2(a))
  
  #test bubble_sort()
  #n=int(input())
  #a=input_list(n)
  #print(a)
  #bubble_sort(a)
  #print(a)

  #test selection_sort()
  #n=int(input())
  #a=input_list(n)
  #print(a)
  #selection_sort(a)
  #print(a)

  #test reverse_sentence()
  #s=input()
  #print(reverse_sentence(s))
  
  #test add_matrices()
  #n=int(input())
  #m=int(input())
  #a=input_2D_list(n,m)
  #b=input_2D_list(n,m)
  #print_2D_list(a)
  #print_2D_list(b)
  #c=add_matrices(a,b)
  #print_2D_list(c)

  #test multiply_matrices()
  #p=int(input())
  #q=int(input())
  #r=int(input())
  #a=input_2D_list(p,q)
  #b=input_2D_list(q,r)
  #print_2D_list(a)
  #print_2D_list(b)
  #c=multiply_matrices(a,b)
  #print_2D_list(c)

  #test unique_substring()
  #s=input()
  #print(unique_substring(s))
  
  print()


main()