小红的数据结构
题号:NC316141
时间限制:C/C++/Rust/Pascal 2秒,其他语言4秒
空间限制:C/C++/Rust/Pascal 256 M,其他语言512 M
64bit IO Format: %lld

题目描述

\hspace{15pt}小红有一个未知的容器,它可能是栈(stack)或队列(queue)。初始时容器为空。
\hspace{15pt}给定一个长度为 n 的数组 a,小红会进行共 q 次如下两种操作:
\hspace{23pt}\bullet 操作一:向容器中压入一个元素 x
\hspace{23pt}\bullet 操作二:从容器中弹出一个元素。
\hspace{15pt}已知所有弹出操作产生的输出序列对应给定的数组 a,且操作是合法的(即不会对空容器执行弹出操作)。请你判断:如果既可能是栈也可能是队列(即两种容器都能产生相同的输出),输出 \texttt{both};如果只可能是栈,输出 \texttt{stack};如果只可能是队列,输出 \texttt{queue};如果两种都不可能(即无论栈还是队列都无法产生给定的输出),输出 \texttt{-1}

输入描述:

\hspace{15pt}第一行两个整数 n, q (1 \leqq n \leqq q \leqq 2 \times 10^5),分别表示输出数组 a 的长度和操作的总次数。
\hspace{15pt}第二行包含 n 个整数 a_1, a_2, \dots, a_n\left(1 \leqq a_i \leqq 10^9 \right),表示弹出操作得到的输出序列。
\hspace{15pt}接下来 q 行,每行描述一个操作:
\hspace{23pt}\bullet若输入为 \texttt{1 x}\left(1 \leqq x \leqq 10^9 \right),表示向容器中压入整数 x
\hspace{23pt}\bullet若输入为 \texttt{2},表示从容器中弹出一个元素。
\hspace{15pt}保证操作合法(不会对空容器执行弹出),且弹出操作的次数恰好为 n

输出描述:

\hspace{15pt}输出一行一个字符串,表示答案:\texttt{stack}\texttt{queue}\texttt{both}\texttt{-1}
示例1

输入

复制
1 2
1
1 1
2

输出

复制
both
示例2

输入

复制
1 3
1
1 1
1 2
2

输出

复制
queue
示例3

输入

复制
1 3
2
1 1
1 2
2

输出

复制
stack
示例4

输入

复制
1 3
2
1 1
1 1
2

输出

复制
-1