Trong giờ nghỉ, giáo sư X nghĩ ra một trò chơi "nhanh tay nhanh mắt" cho sinh viên với \(n\) đồng xu. Ban đầu \(n\) đồng xu được xếp theo thứ tự từ \(1\) tới \(n\) trên mặt đất, mỗi đồng xu có hai mặt: mặt ngửa của đồng xu thứ \(i\) ghi số \(a_i\), mặt sấp của đồng xu thứ \(i\) ghi số \(b_i\).

Phép lật với tham số \(c\) thực hiện như sau: Chọn tất cả các đồng xu có số ở mặt ngửa nhỏ hơn hoặc bằng \(c\) và lật chúng lại. Khi mỗi đồng xu bị lật, mặt ngửa trở thành mặt sấp và ngược lại, mặt sấp trở thành mặt ngửa.

Các sinh viên được cho biết trạng thái ban đầu của \(n\) đồng xu và một dãy \(m\) phép lật với các tham số \(c_1, c_2, ..., c_m\) cho trước. Nhiệm vụ của các sinh viên là phải cho biết dãy các số ghi trên mặt ngửa của các đồng xu sau \(m\) phép lật theo đúng thứ tự đã cho.

Input

• Dòng đầu tiên chứa hai số nguyên dương \(n, m \leq 2\cdot 10^5\)
• \(n\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(a_i, b_i \leq 10^9\)
• \(m\) dòng tiếp theo, dòng thứ \(j\) chứa số nguyên dương \(c_j \leq 10^9\)

Output

• In ra một dòng \(n\) số nguyên là dãy các số ghi trên mặt ngửa của các đồng xu theo đúng thứ tự từ đồng xu \(1\) tới đồng xu \(n\) sau khi đã thực hiện \(m\) phép lật đã cho.
• Các số trên một dòng được/phải ghi cách nhau bởi dấu cách.

Example

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

4 1 8 2 3