E. Moon hates Kilani's Stacks (Grey)
time limit per test
2.5 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Kilani gave Moon his least favorite data structure: a stack with a maximum capacity of $$$L$$$. Moon can perform the following two operations:

  • Push $$$x$$$: add an element with value $$$x$$$ to the top of the stack. If the stack already contains $$$L$$$ elements, the operation does nothing.
  • Pop: remove the element at the top of the stack. If the stack is empty, the operation does nothing.

You are given a sequence of $$$n$$$ operations, each of which is either type $$$1$$$ (Push) or type $$$2$$$ (Pop).

Then, you are given $$$q$$$ queries. In each query, you are given three integers $$$l$$$, $$$i$$$, and $$$k$$$.

For each query, consider a stack with capacity $$$l$$$, and apply only the first $$$i$$$ operations from the given sequence. After performing these operations, determine the value of the $$$k$$$th element in the stack (counted from the bottom, i.e., the bottom element is the first element).

If $$$k$$$ is greater than the current number of elements in the stack, print $$$-1$$$.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases.

For each test case:

  • The first line contains two integers $$$n$$$ and $$$q$$$ ($$$1 \le n, q \le 3 \cdot 10^5$$$) — the number of operations and the number of queries.
  • The next $$$n$$$ lines describe the operations. Each line is one of the following:
    • push $$$x$$$ — push an integer $$$x$$$ onto the stack ($$$1 \le x \le 10^9$$$).
    • pop — remove the top element of the stack.
  • The next $$$q$$$ lines describe the queries. Each line contains three integers $$$l$$$, $$$i$$$, and $$$k$$$ ($$$1 \le l, i, k \le n$$$).

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$, and the sum of $$$q$$$ over all test cases does not exceed $$$3 \cdot 10^5$$$.

Output

For each test case, output $$$q$$$ lines.

For each query, print a single integer — the value of the $$$k$$$th element in the stack after applying the first $$$i$$$ operations on a stack with capacity limit $$$l$$$.

If the stack contains fewer than $$$k$$$ elements after these operations, print $$$-1$$$.

Example
Input
1
5 2
push 5
push 2
pop
push 4
pop
1 5 1
2 5 1
Output
-1
5