#6045. {提高组模拟试题]队栈

内存限制:512 MiB 时间限制:1000 ms 输入文件:staqueue.in 输出文件:staqueue.out
题目类型:传统 评测方式:文本比较
上传者: zhouhao

题目描述

Yazid 是一名 OI 初学者。他最近在研究基础数据结构:队列和栈。某天,Yazid 脑洞大开,发明了一种叫做“队栈”的数据结构。

众所周知,队列是先进先出的数据结构,而栈是先进后出的数据结构。而 Yazid 发明的队栈则同时支持查询并删除其中最. 早. 被. 插. 入. 的. 元. 素. 和最. 晚. 被. 插. 入. 的. 元. 素. 。 Yazid 有一个初始为空的队栈和一个黑. 盒. (这是一个存放数字的盒子),接下来,他要依次执行 Q 个操作。操作分为 4 种:

  1. push:将一个非负整数加入队栈。
  2. pop_queue:找出队栈中最早. 被插入的元素,将其取出放入黑盒,并从队栈中删除。
  3. pop_stack:找出队栈中最晚. 被插入的元素,将其取出放入黑盒,并从队栈中删除。
  4. print:将黑盒中的所有数取出,并按被放入的先后顺序从左到右排列得到一个整数。

• 例如:黑盒中依次被放入了 0, 23, 330, 6,那么获得并打印的整数即是233306。

由于 Yazid 懒于在每次 push 操作时想插入的数,因此他提前写好了一个长度为 n 的插入序列 A(下标从 1 开始)。在接下来的所有 push 操作中,Yazid 会依次地、循环地将这些数加入队栈。具体来说:

• 在首次 push 操作时,Yazid 会将 A1 加入队栈。 • 在之后的每次 push 操作中,假设 Yazid 上次 push 时加入的数是 Ai,则本次他会将 Ai+1 加入队栈。 • 在上一种情况中,特别地,如果 i = n,则 Yazid 本次会将 A1 加入队栈。请你依次输出 Yazid 通过 print 操作获得的整数。

输入格式

从文件 staqueue.in 中读入数据。 第 1 行一个整数 n,表示插入序列的长度。 第 2 行 n 个用单个空格隔开的非负整数 A1, A2, . . . , An,描述插入序列。第 3 行一个整数 Q,表示操作数目。 第 4 行 Q 个紧挨着的 1 ∼ 4 之间的数字,依次描述每个操作,每个数字表示操作的编号(各操作对应的编号见【题目描述】)。 • 保证所有操作的合法性。即保证: – 执行任意 pop_queue 和 pop_stack 操作时队栈不为空。 – 执行任意 print 操作时黑盒不为空。

输出格式

输出到文件 staqueue.out 中。 对于所有 print 操作,输出一行一个整数,表示该 print 操作中 Yazid 获得的数。

样例

【样例 1 输入】

2
1 2
7
1112324

【样例 1 输出】

112

【样例 2 输入】

4
0 23 330 6
12
121313124134

【样例 2 输出】

233306
0

【样例 3】

见选手目录下的 staqueue/staqueue3.in 与 staqueue/staqueue3.ans。

【子任务】

详见PDF。

数据范围与提示

对于所有测试点,保证 n ≤ 10^4,Ai < 1000,Q ≤ 10^7。