题目描述

队列是一种数据结构。现在你要支持几种操作：

• $push$ $x$，将 $x$ 这个元素放到队尾。
• $pop$，将队首的元素删除。
• $query$ $k$，询问从队首往后数第 $k$ 个元素是多少。

（术语说明：队列是一种线性数据结构，遵循先进先出（FIFO，First In First Out）的原则，即最先放入的元素最先被取出。）

输入格式

第一行一个整数 $m$，表示操作个数。

接下来 $m$ 行，每行一个上面所述的操作。

输出格式

输出若干行，对于每个查询操作，输出答案。

样例输入

10
push 1
push 2
query 1
query 2
push 3
query 1
pop
query 1
push 4
query 1

样例输出

1
2
1
2
2

数据范围

对于 $100\%$ 的数据，保证 $1 \le m \le 10^6$。

对于 $push$ 操作，保证 $1 \le x \le 10^6$。

对于 $pop$ 操作，保证队列非空。

对于 $query$ 操作，保证 $k \ge 1$ 且 $k$ 不超过队列里面的元素个数。

保证所有时刻，队列长度 $len \le 1000$。