Problem Statement

Your task is to implement a Fibonacci number generator using a stack. It is assumed that the first Fibonacci number is 0 and the series starts from there.

Input

• First line will contain the size of the stack
• Second line would contain the number of operations
• Then, for operation: A number n will be given as input.

Output

• For each input n the corresponding number in the Fibonacci series should be printed out.
• If the value of n is 0, an InvalidInputException error should be printed and the function should return the value -999.

Sample Input

2

5

0

1

2

3

4

Sample Output

InvalidInputException

-999

0

1

1

2

Code Template

    """The code has been developed by Dr.Vidhya Balasubramanian as part of the CSE230 Data Structures Course, ASE Coimbatore.
   The code is being constantly improved, so please bring to notice any bugs to dsdaa.amrita@gmail.com

   Modified and updated by: M. Vamsee Krishna Kiran.

"""
class MyStack():
    def __init__(self,size):
        self.stack = []
        # this is the stack container called 'stack'
        self.max_stack_size = size
        for i in range(self.max_stack_size):
            self.stack.append(None)
        # define the stack size 'max_stack_size' and initialize it
        self.t = -1

    # define the push operation which  pushes the value into the stack, must throw a stack full exception
    def push(self, value):
        if (self.size() == self.max_stack_size):
            print("Stack Full Exception")
        else:
            #your code here.
        return


    # returns top element of stack if not empty, else throws stack empty exception
    def pop(self):
        if (self.size() == 0):
            print("Stack Empty Exception")
            return
        else:
            #your code here
            return toret


    # returns top element without removing it if the stack is not empty, else throws exception   
    def top(self):
        if (self.size() == 0):
            print ("Stack Empty Exception")
            return
        else:
            return self.stack[self.t]


    # returns True if stack is empty   
    def isEmpty(self):
        return  (self.t<0)

    # returns the number of elements currently in stack 
    def size(self):
        return self.t+1

    def printStack(self):
        if (self.isEmpty()):
            print ("Stack Empty Exception")
        else:
            for i in range(self.max_stack_size):
                if self.stack[i]!=None:
                    print(self.stack[i],end=" ")
            print(" ")
    def FibGen(self,n):
        #your code here.


    def flushstack(self):
        while(not self.isEmpty()):
            self.pop()  
# Driver code.---------------------------------------------

def teststack():
    stacksize=int(input())
    st1 = MyStack(stacksize)
    inputs=int(input())
    while inputs>0:
        command=int(input())
        fibnumber=st1.FibGen(command)
        st1.flushstack()
        print(fibnumber)
        inputs-=1

def main():
    teststack()

if __name__ == '__main__':
    main()