Chạy qua cầu

Có $n$ cây cầu được đặt nối tiếp nhau: cầu thứ $i$ bắt đầu ngay tại điểm kết thúc của cầu thứ $i-1$. Bạn phải chạy qua toàn bộ $n$ cây cầu từ trái sang phải.

Cầu thứ $i$ có độ dài $l_i$ và một giới hạn thời gian $t_i$: nếu bạn đặt chân vào đầu cầu thứ $i$ tại thời điểm $T$ thì bạn phải rời khỏi cầu đó chậm nhất tại thời điểm $T+t_i$ (được phép tới đúng vào thời điểm $T+t_i$).

Tốc độ chạy bình thường của bạn là $0.5$, nghĩa là chạy hết một đoạn dài $s$ mất $2s$ giây. Ngoài ra bạn có các chai nước tăng lực giống hệt nhau: uống một chai làm tốc độ tăng gấp đôi (lên thành $1$) trong $r$ giây. Bạn chỉ được uống tại các thời điểm nguyên, việc uống diễn ra tức thời, và nếu uống một chai tại thời điểm $T$ thì chai tiếp theo chỉ có thể uống sớm nhất tại thời điểm $T+r$.

Bạn bắt đầu ở đầu cầu thứ nhất tại thời điểm $0$ và luôn chạy liên tục (không được dừng lại). Hãy tìm số chai nước tăng lực ít nhất cần dùng để chạy qua hết tất cả các cầu. Nếu số đó không vượt quá ${10}^5$ thì phải chỉ ra các thời điểm uống.

Dữ liệu vào

• Dòng đầu chứa hai số nguyên $n$ và $r$.
• Dòng thứ hai chứa $n$ số nguyên $l_1,l_2,\dots ,l_n$.
• Dòng thứ ba chứa $n$ số nguyên $t_1,t_2,\dots ,t_n$.

Dữ liệu ra

• Dòng đầu in ra $k$ là số chai nước ít nhất phải dùng, hoặc $-1$ nếu không có cách nào chạy qua hết các cầu.
• Nếu có đáp án và $k\le {10}^5$ thì dòng thứ hai in ra $k$ số nguyên là các thời điểm uống nước, theo thứ tự tăng dần. Nếu có nhiều đáp án, in ra đáp án nào cũng được.

Ràng buộc

• $1\le n\le 2·{10}^5$
• $1\le r\le {10}^{12}$
• $1\le l_i\le 5·{10}^6$
• $1\le t_i\le {10}^7$

Ví dụ