Inventory Management System

You are required to implement an inventory management system. The system should maintain a collection of products with their respective quantities. The inventory is represented by a list of key-value pairs, where the key is the product's name (a string) and the value is its quantity (an integer). The following operations must be supported:

• add <item> <quantity>: Adds the specified quantity to the item. If the item exists, its quantity is increased.
• remove <item>: Removes the item from the inventory. If the item does not exist, output "Item not found".
• update <item> <quantity>: Updates the quantity of the specified item. The updated quantity must be non-negative. If a negative quantity is provided, output "Invalid quantity"; if the item does not exist, output "Item not found".
• check <item>: Outputs the current quantity of the specified item. If the item does not exist, output "Item not found".
• list: Lists all items in the inventory in alphabetical order along with their quantities. Each item and its quantity should be printed on a new line.

The system should handle input and output via standard input (stdin) and standard output (stdout). Note that for operations which do not require an output (such as a successful add), nothing should be printed.

For instance, if a command tries to update an item with a negative quantity, the program should output: \(Invalid\; quantity\).

inputFormat

The input consists of multiple lines:

1. The first line contains an integer \(N\) indicating the number of initial inventory items. If \(N\) is 0, the inventory starts empty.
2. The next \(N\) lines each contain a string and an integer representing an item's name and its quantity.
3. The following line contains an integer \(M\) indicating the number of operations to perform.
4. The next \(M\) lines each describe an operation in one of the following formats:
   • add <item> <quantity>
   • remove <item>
   • update <item> <quantity>
   • check <item>
   • list

outputFormat

For each operation that produces an output, print the result on a new line using stdout. The operations behave as follows:

• check: Print the quantity of the item or "Item not found" if it does not exist.
• remove and update: If the item does not exist, print "Item not found"; if the update operation is given a negative quantity, print "Invalid quantity".
• list: Print each item in the inventory ordered alphabetically, with each line containing the item name and its quantity separated by a space. If the inventory is empty, print nothing.
• add: No output is produced.

## sample

0
5
add apples 10
add apples 5
check apples
remove bananas
list

15
Item not found
apples 15

</p>