D. Кая ба мөнх

хугацааны хязгаарлалт 2 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Цасны хатан хаан Каяд мөсний ширхэгүүдээр "eternity" гэсэн үгийг бүрдүүл гэж хэлсэн. Кая энэ ажлыг гүйцэлдүүлэхийг маш их хүсэж байна учир нь тэр ингэснээр суллагдах ба Цасны хатан хаан түүнд бүх дэлхийг мөн хос тэшүүр өгнө.

Цасны хатан хааны ордны ард нүднүүдээс бүрдсэн хязгааргүй талбар байгаа. Уг талбарын дээгүүр тархсан $n$ ширхэг мөсний ширхэг байгаа ба ширхэг бүр яг нэг нүд эзлэх ба ямар ч хоёр ширхэг ижил нүд эзлэхгүй. Ажлын хэр хүнд вэ гэдгийг үнэлэхийн тулд Кая булангууд нь нүднүүдийн булан дээр байрласан ба талууд нь координатын тэнхлэгтэй параллель $k × k$ нүдний хэмжээтэй квадратыг авч түүн дотор байгаа мөсний ширхэгүүдийг тоолно.

Энэ арга нь талбарын зарим хэсгийн хэр хэцүү вэ гэдэг үнэлгээг гаргана. Гэсэн ч Кая мөн нийт үнэлгээг үнэлэхийг хүсч байгаа ба дараах шалгууртай болсон: $x$ ($1 ≤ x ≤ n$) бүрийн хувьд тэр дотроо яг $x$ мөсний ширхэг байх $k × k$ хэмжээтэй квадратуудын тоог мэдэхийг хүсч байна.

Каяд Цасны хатан хааны даалгасан ажлын хэр хүнд вэ гэдгийг үнэлэхэд туслана уу.

Оролт

Оролтын эхний мөрөнд хоёр бүхэл тоон утга $n$ ба $k$ ($1 ≤ n ≤ 100 000$, $1 ≤ k ≤ 300$) байх ба харгалзан мөсний ширхэгийн тоо болон $k$ утга байна. Дараагийн $n$ мөр бүрт хоёр бүхэл тоон утга $x_{i}$ ба $y_{i}$ ($ - 10^{9} ≤ x_{i}, y_{i} ≤ 10^{9}$) байх буюу $i$-р мөсний ширхэгийг агуулж байгаа нүдний координат юм. Ямар ч хоёр мөсний ширхэг ижил нүдийг эзлэхгүй.

Гаралт

$n$ бүхэл тоон утгыг хэвлэх ба эдгээр нь яг $1, 2, ..., n$ мөсний ширхэг агуулж байгаа $k × k$ хэмжээтэй квадратуудын тоо байна.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
5 3
4 5
4 6
5 5
5 6
7 7
Гаралт
10 8 1 4 0 
Сэтгэгдлүүдийг ачааллаж байна...