Bessie và Elsie mỗi cô đã nướng \(N\) chiếc bánh (\(1 \leq N \leq 10^5\)). Mỗi chiếc trong tổng số \(2N\) chiếc bánh có một độ ngon theo đánh giá của Bessie và một độ ngon (có thể khác) theo đánh giá của Elsie.

Bessie đang nghĩ đến việc tặng một chiếc bánh của mình cho Elsie. Nếu nhận bánh từ Bessie, Elsie sẽ cảm thấy mình có nghĩa vụ tặng lại Bessie một chiếc bánh của cô. Để không tỏ ra keo kiệt cũng không quá phô trương, Elsie sẽ cố chọn một chiếc bánh mà theo đánh giá của cô, nó ngon ít nhất bằng chiếc bánh cô vừa nhận nhưng không ngon hơn quá \(D\) đơn vị (\(0 \leq D \leq 10^9\)). Có thể không tồn tại chiếc bánh như vậy; trong trường hợp đó, Elsie sẽ dùng một tên giả và tự lưu đày sang Nhật Bản.

Nhưng nếu Elsie tặng lại Bessie một chiếc bánh, Bessie cũng sẽ cố tặng Elsie một chiếc bánh mà theo đánh giá của Bessie, nó ngon ít nhất bằng chiếc bánh Elsie vừa tặng nhưng không ngon hơn quá \(D\) đơn vị. Nếu điều này là bất khả thi, Bessie cũng sẽ tự lưu đày. Nếu không, cô sẽ tặng chiếc bánh đã chọn cho Elsie. Chu trình này tiếp tục cho đến khi một trong hai cô bò bị lưu đày, một kết cục không vui, hoặc một cô bò nhận được chiếc bánh mà cô đánh giá có độ ngon bằng \(0\); trong trường hợp đó, việc trao đổi quà kết thúc và cả hai cô bò đều vui vẻ.

Lưu ý rằng một chiếc bánh không thể được tặng hai lần, và không cô bò nào được tặng trả lại chiếc bánh mà mình đã nhận.

Với mỗi chiếc trong \(N\) chiếc bánh mà Bessie có thể chọn làm món quà đầu tiên cho Elsie, hãy xác định số bánh nhỏ nhất có thể được tặng trong cuộc trao đổi sau đó trước khi hai cô bò trở nên vui vẻ.

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên \(N\) và \(D\).

\(2N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách, lần lượt biểu thị độ ngon của một chiếc bánh theo đánh giá của Bessie và độ ngon của chiếc bánh đó theo đánh giá của Elsie.

\(N\) dòng đầu tiên mô tả các chiếc bánh của Bessie, và \(N\) dòng còn lại mô tả các chiếc bánh của Elsie.

Mọi giá trị độ ngon được đảm bảo nằm trong khoảng \([0, 10^9]\).

Dữ liệu ra

Kết quả gồm \(N\) dòng. Dòng \(i\) chứa một số nguyên duy nhất: số bánh nhỏ nhất có thể được tặng trong một cuộc trao đổi quà vui vẻ bắt đầu bằng chiếc bánh thứ \(i\) của Bessie. Nếu không có cuộc trao đổi nào bắt đầu bằng chiếc bánh thứ \(i\) có kết thúc vui vẻ, dòng \(i\) chứa số nguyên duy nhất \(-1\).

Ví dụ

2 1
1 1
5 0
4 2
1 4

3
1

Nguồn

USACO 2017 December Contest, Gold — A Pie for a Pie

Tác giả bài toán: Dhruv Rohatgi.