解题思路

核心思路

本题本质是两个有序集合的维护问题：

1. 打开列表（按打开顺序）
2. 缓存区（FIFO 队列）

题目内容

在大型多人在线角色扮演游戏（MMORPG）中，玩家会频繁打开各种功能界面，如背包、技能、地图、团队和任务等。为了优化内存占用和加快界面响应速度，游戏需要采用界面缓存管理机制。

游戏中的界面分为两类：

• 可缓存界面：关闭后不会立即销毁，而是暂存到一个大小有限的缓存区中。当玩家再次打开该界面时，可以快速从缓存区恢复，避免重新加载资源。

• 不可缓存界面：关闭后立即从内存中卸载，下次打开时需要重新创建。

缓存区采用先入先出（FIFO）淘汰策略：当缓存区已满时，新进入缓存区的界面会将最早进入缓存区的界面挤出（从缓存区中移除，彻底卸载）。

给定所有界面的类型、缓存区的容量，以及一系列打开和关闭界面的操作，请你输出操作完毕后的最终状态：

1. 当前打开的界面列表（按打开顺序由早到晚排列）

2. 当前缓存区中的界面列表（按进入缓存区顺序由早到晚排列）

操作规则如下：

打开界面

• 若该界面已在缓存区中，则将其从缓存区移出并打开界面
• 若该界面未在缓存区中，则创建新界面并打开界面
• 若该界面已经处于打开状态，则将其移到打开列表末尾

关闭界面

• 关闭操作只对打开状态的界面有效，若界面不处于打开状态，忽略此次操作
• 若该界面是可缓存的：如果缓存区有空位，直接将其放入缓存区；若缓存区已满，最早进入缓存区的界面将会被卸载，然后将当前操作的界面放入缓存区
• 若该界面是不可缓存的，则直接从内存中卸载

输入描述

第一行包含三个整数 $n, m, k$ 分别表示界面种类数、操作序列长度、缓存区容量。

第二行包含 $n$ 个整数 $t_1,t_2,\dots,t_n$，其中 $t_i=1$ 表示第 $i$ 个界面是可缓存的，$t_i=0$ 表示第 $i$ 个界面是不可缓存的。

接下来 $m$ 行，每行描述一个操作：

• $open$ $x$：打开编号为 $x$ 的界面（$1 \le x \le n$）
• $close$ $x$：关闭编号为 $x$ 的界面（$1 \le x \le n$）

数据范围：$1 \le n \le 10000$，$1 \le m \le 1000000$，$1 \le k \le 5000$

输出描述

第一行输出当前打开的界面编号，按打开顺序由先到后排列，以空格分隔。若没有打开的界面，输出 $EMPTY$。

第二行输出当前缓存区中的界面编号，按进入缓存区的顺序由先到后排列，以空格分隔。若缓存区为空，输出 $EMPTY$。

样例1

输入

4 9 2
1 1 0 1
open 1
open 2
open 3
close 2
close 3
close 1
open 4
open 1
open 4

输出

1 4
2

说明