阿卡的序列

• 输入文件：seq.in
• 输出文件：seq.out
• 时间限制：1 second
• 空间限制：512 megabytes

题目描述

在跨年晚会上，阿瓦想出了一个新节目。

阿卡拿到了一个初始长度为 n 的序列，其中第 i 个元素（1 ≤ i ≤ n）的值为 a_i。

然后阿瓦将这个序列用幕布遮住，不让阿卡看到。阿卡只能靠芝之前的几秒钟记住这些元素的位置和大小。接着阿瓦会随机地请台下的观众来对这个序列进行一些操作，主要的操作有以下两种：

1. 1 x：表示在序列的开头添加一个值为 x 的元素。
2. 2 x：表示在序列的结尾添加一个值为 x 的元素。
3. 表示将整个序列翻转，也就是说假设当前序列有 cur 个元素，翻转操作就是将原来的第 i 个元素换到第 cur - i + 1 个位置。

进行了一这一系列操作之后，阿卡需要报出最后的序列是长什么样的。显然这个节目的难度很大，阿卡没有这么好的记忆力，但他也不希望台下的观众失望，于是请到了你来帮助他算一算，最后的序列是什么。

Input

第一行一个数 n，表示初始的序列长度。

第二行 n 个数，第 i 个数 a_i，意义如题面中所述。

第三行一个数 m，表示操作的个数。

接下来 m 行，每行的开头都是 "1"、"2" 或 "3"。后面的格式如题面中所述，代表一个操作。

Output

输出一行，从头到尾输出最后序列的每一个元素。每两个数之间用空格隔开。

Example

输入

5
6 9 4 9 8
4
1 4
3
1 4
3

输出

4 6 9 4 9 8 4

Constraints

• 对于 30% 的数据，n, m ≤ 200。
• 对于 50% 的数据，n, m ≤ 3000。
• 对于 100% 的数据，n, m ≤ 10^5，0 < a_i, x ≤ 10^9。