An có một BST được tạo từ \(N\) số nguyên dương phân biệt. An muốn tìm tổ tiên chung gần nhất (LCA) của hai nút có giá trị \(u\) và \(v\) trong BST.

Tổ tiên chung gần nhất của hai nút \(u\) và \(v\) là nút nằm sâu nhất trên cây mà cả \(u\) và \(v\) đều là hậu duệ.

Hãy giúp An viết chương trình tìm LCA của hai nút trong BST.

Đị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 hai số nguyên \(u\) và \(v\) (\(1 \le u, v \le 10^9\), dữ liệu đảm bảo \(u\) và \(v\) tồn tại trong BST).

Định dạng đầu ra

• Với mỗi truy vấn, in ra giá trị của tổ tiên chung gần nhất của \(u\) và \(v\).

Ví dụ

Input:

7 2
5 3 7 2 4 6 8
2 4
2 8

Output:

3
5

Giải thích:

• LCA của \(2\) và \(4\) là \(3\).
• LCA của \(2\) và \(8\) là \(5\).