Valeriy và Deque

Cho một hàng đợi hai đầu (deque) gồm $n$ phần tử. Phần tử thứ $i$ có giá trị $a_i$.

Mỗi thao tác được thực hiện như sau: lấy ra hai phần tử ở đầu bên trái của deque, gọi lần lượt là $A$ và $B$. Sau đó:

• Nếu $A>B$: ghi $A$ vào đầu deque, ghi $B$ vào cuối deque.
• Ngược lại: ghi $B$ vào đầu deque, ghi $A$ vào cuối deque.

Ví dụ, nếu deque là $[2,3,4,5,1]$ thì sau một thao tác ta ghi $B=3$ vào đầu và $A=2$ vào cuối, được $[3,4,5,1,2]$.

Có $q$ truy vấn, mỗi truy vấn cho một số nguyên $m_j$. Với mỗi truy vấn, hãy cho biết hai phần tử $A$ và $B$ được lấy ra ở thao tác thứ $m_j$. Các truy vấn độc lập với nhau; $A$ và $B$ phải được in theo đúng thứ tự chúng được lấy ra khỏi deque.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $q$ — số phần tử của deque và số truy vấn.
• Dòng thứ hai chứa $n$ số nguyên $a_1,a_2,\dots ,a_n$.
• $q$ dòng tiếp theo, mỗi dòng chứa một số nguyên $m_j$.

Dữ liệu ra

Với mỗi truy vấn, in ra hai số $A$ và $B$ — hai phần tử được lấy ra ở thao tác thứ $m_j$.

Ràng buộc

• $2\le n\le {10}^5$
• $0\le q\le 3·{10}^5$
• $0\le a_i\le {10}^9$
• $1\le m_j\le {10}^{18}$

Ví dụ