Cho dãy số nguyên \(a_1, a_2, \dots, a_n\) và \(q\) truy vấn. Mỗi truy vấn gồm một số nguyên \(L\). Với mỗi truy vấn, hãy in ra màn hình giá trị nhỏ nhất và giá trị lớn nhất trong đoạn từ \(a_1\) đến \(a_L\).

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n\) và \(q\) (\(n, q \le 10^5\)).
• Dòng thứ hai chứa \(n\) số nguyên \(a_1, a_2, \dots, a_n\) (\(|a_i| \le 10^9\)).
• \(q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(L\) (\(1 \le L \le n\)).

Output

• Với mỗi truy vấn, in ra trên một dòng hai số nguyên lần lượt là \(\min(a_1, a_2, \dots, a_L)\) và \(\max(a_1, a_2, \dots, a_L)\).

Example

5 3
1 5 2 4 3
1
3
5

1 1
1 5
1 5

Constraints

• \(n, q \le 10^5\)
• \(|a_i| \le 10^9\)