Nhỏ lớn lớn nhỏ

Cho mảng số nguyên ~a~ độ dài ~n~ và ~q~ truy vấn, mỗi truy vấn bao gồm một số nguyên ~x~, yêu cầu:

• Tìm phần tử nhỏ nhất thỏa mãn lớn hơn hoặc bằng ~x~.
• Tìm phần tử nhỏ nhất thỏa mãn lớn hơn ~x~.
• Tìm phần tử lớn nhất thỏa mãn nhỏ hơn hoặc bằng ~x~.
• Tìm phần tử lớn nhất thỏa mãn nhỏ hơn ~x~.

Input

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~ ~(1 \le n,q \le 5.10^5)~.
• Dòng thứ hai chứa ~n~ số nguyên mảng ~a~ ~(1 \le a_i \le 10^9)~.
• ~q~ dòng tiếp theo, mỗi dòng chứa số nguyên ~x~ ~(1 \le x \le 10^9)~ mô tả truy vấn.

Output

• Với mỗi truy vấn, in ra trên một dòng lần lượt là giá trị phần tử nhỏ nhất thỏa mãn lớn hơn hoặc bằng ~x~, phần tử nhỏ nhất thỏa mãn lớn hơn ~x~, phần tử lớn nhất thỏa mãn nhỏ hơn hoặc bằng ~x~ và phần tử lớn nhất thỏa mãn nhỏ hơn ~x~. Nếu không có phần tử thỏa mãn, in ra "None".

Samples

6 6
1 2 3 4 5 6
1
2
3
4
5
6

1 2 1 None 
2 3 2 1 
3 4 3 2 
4 5 4 3 
5 6 5 4 
6 None 6 5

3 1
5 4 10
8

10 10 5 5

Scoring

• Subtask ~1~ ~-~ ~50~ điểm: ~n,q \le 5000~
• Subtask ~2~ ~-~ ~50~ điểm: Không có ràng buộc gì thêm