Trong một BST, predecessor của một giá trị \(x\) là phần tử lớn nhất trong BST nhỏ hơn \(x\). Successor của \(x\) là phần tử nhỏ nhất trong BST lớn hơn \(x\).

An có một BST được tạo từ \(N\) số nguyên dương phân biệt. An muốn tìm predecessor và successor của một giá trị \(x\) (có thể \(x\) không tồn tại trong BST).

Hãy giúp An viết chương trình tìm predecessor và successor.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên dương \(N\) và \(Q\) (\(1 \le N, Q \le 10^3\)).
• Dòng thứ hai chứa \(N\) số nguyên dương phân biệt \(a_1, a_2, \dots, a_N\) (\(1 \le a_i \le 10^9\)).
• \(Q\) dòng tiếp theo, mỗi dòng chứa một số nguyên \(x\) (\(1 \le x \le 10^9\)).

Định dạng đầu ra

• Với mỗi truy vấn, in ra predecessor và successor trên một dòng, cách nhau bởi một khoảng trắng.
• Nếu không có predecessor, in ra \(NONE\).
• Nếu không có successor, in ra \(NONE\).

Ví dụ

Input:

7 3
5 3 7 2 4 6 8
4
9
1

Output:

3 5
8 NONE
NONE 2

Giải thích:

• Predecessor của \(4\) là \(3\), successor là \(5\).
• \(9\): predecessor là \(8\), không có successor.
• \(1\): không có predecessor, successor là \(2\).