Bánh tặng nhau

Bessie và Elsie mỗi người làm $N$ bánh. Mỗi bánh có 2 giá trị ngon (theo Bessie và Elsie). Bessie tặng bánh cho Elsie. Elsie đáp lại bằng bánh có giá trị ngon (theo Elsie) trong khoảng $[v,v+D]$ với $v$ là giá trị bánh nhận. Chuỗi trao đổi kết thúc hạnh phúc khi nhận bánh giá trị 0. Với mỗi bánh của Bessie, tìm số bánh trao đổi ít nhất, hoặc $-1$.

Dữ liệu vào

• Dòng đầu: $N$ $D$. $2N$ dòng tiếp: giá trị Bessie, giá trị Elsie ($N$ bánh Bessie, rồi $N$ bánh Elsie).

Dữ liệu ra

• $N$ dòng: số bước tối thiểu cho mỗi bánh Bessie.

Ràng buộc

• $1\le N\le {10}^5$, $0\le D\le {10}^9$

Ví dụ