Polymorphism: Managing Child Classes with Parent Type Array

In this problem, you will create a program that defines Animal as a parent class, creates Dog and Cat as subclasses using inheritance and method overriding, builds an Animal type array based on input, and calls each object's speak() method using polymorphism, displaying the result to standard output.

Learning Objective: Understand how to uniformly handle different child class objects using a parent type array

Overview

Create Dog and Cat classes that extend Animal, build an Animal type array from input, and call each object's speak method.

Specifications

• Animal class: speak() method (outputs "Animal speaks")
• Dog class: override speak() (outputs "Woof!")
• Cat class: override speak() (outputs "Meow!")
• Store animals of the input-specified types in an Animal type array

Input Format

N
type1
type2
...
typeN

• Line 1: number of animals N (at least 1)
• Next N lines: type of each animal ("Dog" or "Cat")

Output Format

Print the result of each animal's speak() call, one per line.

Example

Input:

3
Dog
Cat
Dog

Output:

Woof!
Meow!
Woof!