Implement a Generic Stack in C++

Problem: Build a Generic C++ Stack

Write a class template Stack<T> that can hold elements of any type T. For testing, the following operations must be available:

• push x: place integer x on top of the stack.
• pop: remove and print the top element; print EMPTY if the stack is empty.
• top: print the top element without removal; print EMPTY if the stack is empty.
• empty: output true when the stack has no elements, otherwise false.
• size: output the current count of elements.

The top() accessor should return a reference T& (a const T& overload may also be provided). Returning a copy is not allowed; the implementation must avoid dangling references and manage object lifetimes correctly, preventing any resource leaks.

Input Format

The first line provides q, the number of operations. Then q lines follow, each containing one command: push x, pop, top, empty, or size.

Output Format

For every command that is not push, print the appropriate result on a separate line.

Constraints

• 1 <= q <= 2 * 10^5
• x is a signed 32‑bit integer

Example

Input:

8
push 10
push 20
top
pop
size
empty
pop
empty

Output:

20
20
1
false
10
true