题目描述

小青在学习栈这种数据结构，他想实现一个简单的栈。

栈的特点是后进先出（LIFO）。

请你帮助小青实现栈的基本操作。

输入格式

第一行输入一个整数 n，表示操作次数 接下来 n 行，每行一个操作：

• "push x"：将 x 压入栈
• "pop"：弹出栈顶元素

输出格式

对于每个 pop 操作，输出弹出的元素，如果栈为空输出"empty"

样例

样例 1

输入 #1

5
push 1
push 2
pop
pop
pop

输出 #1

2
1
empty

提示

使用数组或链表实现栈