Bánh tặng nhau

Hai chị em bò Bessie và Elsie, mỗi người nướng $N$ chiếc bánh. Với mỗi chiếc bánh trong tổng số $2N$ chiếc, Bessie chấm cho nó một điểm ngon và Elsie cũng chấm cho nó một điểm ngon riêng. Hai điểm này hoàn toàn độc lập với nhau.

Bessie muốn tặng Elsie một chiếc bánh của mình. Khi một con bò nhận được bánh, nó thấy có lỗi nếu không đáp lễ. Quy tắc đáp lễ như sau: gọi $v$ là điểm ngon mà chính con bò vừa nhận bánh chấm cho chiếc bánh nó nhận được, con bò đó phải chọn một chiếc bánh trong $N$ chiếc bánh của mình mà chính nó chấm điểm nằm trong đoạn $[v,v+D]$, rồi tặng lại cho con bò kia. Cứ thế, hai con bò tặng bánh qua lại cho nhau.

Chuỗi trao đổi kết thúc hạnh phúc ngay khi một con bò nhận được chiếc bánh mà chính nó chấm điểm ngon bằng $0$: nó quá xúc động nên không đáp lễ nữa.

Nếu một con bò nhận được chiếc bánh có điểm ngon (theo đánh giá của nó) khác $0$ mà nó không có chiếc bánh nào hợp lệ để đáp lễ, hoặc nếu chuỗi trao đổi cứ kéo dài mãi không bao giờ dừng, thì chuỗi đó không kết thúc hạnh phúc.

Với mỗi chiếc bánh của Bessie, hãy cho biết: nếu Bessie mở đầu bằng cách tặng đúng chiếc bánh đó, thì tổng số bánh được trao qua lại ít nhất là bao nhiêu để chuỗi kết thúc hạnh phúc (tính cả chiếc bánh Bessie tặng đầu tiên). In ra $-1$ nếu không thể kết thúc hạnh phúc.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $N$ và $D$.
• $N$ dòng tiếp theo mô tả $N$ chiếc bánh của Bessie: dòng thứ $i$ chứa hai số nguyên là điểm Bessie chấm và điểm Elsie chấm cho chiếc bánh đó.
• $N$ dòng tiếp theo mô tả $N$ chiếc bánh của Elsie, theo cùng định dạng (điểm Bessie chấm trước, điểm Elsie chấm sau).

Dữ liệu ra

• In ra $N$ dòng. Dòng thứ $i$ là đáp án cho chiếc bánh thứ $i$ của Bessie.

Ràng buộc

• $1\le N\le {10}^5$
• $0\le D\le {10}^9$
• Mọi điểm ngon là số nguyên trong đoạn $[0,{10}^9]$.

Ví dụ