HM220 链表头尾

来源： 第 220 集 list容器-数据存取

难度： 普及-

时间限制： 1s

空间限制： 64MB

题目描述

链表的数据存取接口只有两个：front() 返回第一个元素，back() 返回最后一个元素。

它**没有**重载的 []，也**没有**成员函数 at。底层是结点地址不连续的链表，迭代器只是双向迭代器：支持 ++ 和 --，一步一步前移或后移；不支持 it + 1 这种跳跃，因此也不能按下标随机访问。

若要看中间某个位置，只能从 begin() 起连做若干次 ++，或从 end() 起连做若干次 --。

先把输入序列尾插入，输出 front 与 back。再处理 \(q\) 条查询：

• 1：输出 front()；
• 2：输出 back()；
• 3 k：迭代器从 begin() 出发，只做 \(k\) 次 ++，再解引用（\(k=0\) 即第一个元素）；
• 4 k：迭代器从 end() 出发，只做 \(k\) 次 --，再解引用（\(k=1\) 即最后一个元素）。

禁止使用 []、at 或迭代器加法。保证链表非空，所有偏移合法。

输入格式

第一行两个整数 \(n\)、\(q\)（\(n \ge 1\)）。

第二行 \(n\) 个整数，依次尾插。

接下来 \(q\) 行，每行一条查询。

输出格式

第一行两个整数：front() 与 back()，中间一个空格。

随后 \(q\) 行，每行一个整数，为对应查询的结果。行末均换行。

样例

输入 #1

4 5
10 20 30 40
1
2
3 1
4 1
4 2

输出 #1

10 40
10
40
20
40
30

输入 #2

1 3
9
1
2
3 0

输出 #2

9 9
9
9
9

说明

\(1 \le n \le 1000\)，\(1 \le q \le 2000\)，元素绝对值不超过 \(10^9\)。对操作 \(3\) 有 \(0 \le k < n\)，对操作 \(4\) 有 \(1 \le k \le n\)。

样例 #1：首尾是 \(10\) 与 \(40\)；从开头 ++ 一次得到第二个元素 \(20\)；从末尾 -- 一次仍是 \(40\)，再 -- 一次是 \(30\)。只有一个元素时，front 和 back 相同。