Берляндский лес был высажен несколько десятилетий назад в форме бесконечной сетки с деревом в каждой ячейке. Теперь деревья выросли, и они образуют довольно плотную структуру.
Такую плотную, на самом деле, что пожар стал реальной опасностью для леса. Это лето выдалось необычно жарким в Берляндии, и некоторые деревья загорелись!
Секунда, в которую начался пожар, считается секундой $$$0$$$. Каждую секунду пожар захватывал все соседние неповрежденные деревья ко всем горящим на данный момент деревьям. Дерево считается соседним, если оно находится в соседней по стороне или по углу ячейке. К счастью, после $$$t$$$ секунд работники Берлянского пожарного отделения добрались до пожара и мгновенно потушили его.
Теперь они хотят высчитать разрушительную мощь пожара. Пусть $$$val_{x, y}$$$ будет секундой, в которую дерево в ячейке $$$(x, y)$$$ загорелось. Разрушительная мощь — это сумма $$$val_{x, y}$$$ по всем $$$(x, y)$$$ сгоревших деревьев.
Разумеется, все работники пожарного отделения — пожарные, а не программисты, поэтому они просят Вас помочь им с вычислением разрушительной мощи пожара.
Ответ может быть довольно большим, потому выведите его по модулю $$$998244353$$$.
В первой строке записаны два целых числа $$$n$$$ и $$$t$$$ ($$$1 \le n \le 50$$$, $$$0 \le t \le 10^8$$$) — количество деревьев, которые изначально загорелись, и время, к которому пожарное отделение прибыло на место пожара, соответственно.
В каждой из следующих $$$n$$$ строк записаны по два целых числа $$$x$$$ и $$$y$$$ ($$$-10^8 \le x, y \le 10^8$$$) — позиции деревьев, которые изначально загорелись.
Очевидно, позиция клетки $$$(0, 0)$$$ на этой сетке и направления осей не играют роли, так как сама сетка бесконечна, и ответ не зависит от этой информации.
Гарантируется, что все заданные позиции попарно различны.
Сетка бесконечная, поэтому пожар не останавливается, как только он достигнет $$$-10^8$$$ или $$$10^8$$$. Он продолжается и за эти границы.
Выведите единственное целое число — сумма $$$val_{x, y}$$$ по всем $$$(x, y)$$$ сгоревших деревьев по модулю $$$998244353$$$.
1 2 10 11
40
4 1 2 2 1 3 0 2 2 4
18
3 0 0 0 -2 1 1 1
0
Здесь представлена визуализация первых трех примеров. Серые клетки имеют $$$val = 0$$$, оранжевые — $$$val = 1$$$ и красные — $$$val = 2$$$.
