题目描述

给定一个初始长度为 $n$ 的双向链表，要求在链表的第 $k$ 个节点之后插入一个新的节点，新节点的值为 $v$。

• 节点编号从头节点开始算起，编号为 $1, 2, 3, \dots, n$。
• 如果 $k = 0$，表示在双向链表的最头部（首个节点之前）插入新节点。
• 如果 $k \ge n$，表示在双向链表的最尾部插入新节点。 请输出执行插入操作后的整个双向链表（从头到尾的节点值）。

输入格式

第一行包含一个整数 $n$ $(0 \le n \le 10^5)$，表示初始双向链表的长度。 第二行包含 $n$ 个整数，表示初始双向链表从头到尾各个节点的值。如果 $n=0$，则此行为空。 第三行包含两个整数 $k$ 和 $v$ $(0 \le k \le 10^5, -10^9 \le v \le 10^9)$，分别表示插入位置和新插入节点的值。

输出格式

输出一行整数，包含操作后的双向链表从头到尾所有节点的值，数字之间用一个空格隔开。

样例输入 1

4
10 20 30 40
2 25

样例输出 1

10 20 25 30 40

样例说明 1

在第 2 个节点（值为 20）之后插入值为 25 的新节点。新节点 25 的前驱指向 20，后继指向 30；同时 20 的后继指向 25，30 的前驱指向 25。

样例输入 2

3
5 15 25
0 100

样例输出 2

100 5 15 25

样例说明 2

$k=0$ 时，在链表最头部插入值为 100 的新节点。新节点成为新的头节点，其后继指向原头节点 5，原头节点 5 的前驱指向新节点。

样例输入 3

2
7 7
10 99

样例输出 3

7 7 99

样例说明 3

$k=10$ 大于当前链表长度 $2$，因此在链表最尾部插入值为 99 的新节点。原尾节点的前驱和后继指针相应更新。