По результатам замеров глубин в озере Тургояк была составлена карта. Она имеет вид прямоугольной таблицы, каждая из ячеек которой содержит либо неотрицательное целое число — глубину в каком-то месте озера, либо число $$$-1$$$, означающее, что в этом месте замеры не проводились, и глубина неизвестна.
Гидрологи утверждают, что дно на измеренном участке не может иметь резких перепадов. Это означает, что глубины в ячейках, соседних по стороне, должны отличаться не более чем на $$$v$$$. Это касается как известных, так и неизвестных (тех, вместо которых в таблице указано число $$$-1$$$) глубин.
По заданной карте определите, существует ли набор неотрицательных целых глубин, точно соответствующий всем замерам, или в данных есть противоречия, и сделанные замеры были неточными.
В первой строке входных данных содержится три неотрицательных целых числа $$$n$$$, $$$m$$$ и $$$v$$$ ($$$1 \le n \cdot m \le 10^5$$$, $$$0 \le v \le 10^9$$$) — размеры карты и максимальный допустимый перепад глубин.
В следующих $$$n$$$ строках входных данных содержатся по $$$m$$$ целых чисел $$$d_{ij}$$$ ($$$-1 \le d_{ij} \le 10^9$$$) — информация о глубинах.
Выведите строку «Yes», если существует набор глубин, соответствующий всем замерам, и «No» иначе.
Вы можете вывести ответ в любом регистре (верхнем или нижнем). Например, строки «yEs», «yes», «Yes» и «YES» будут распознаны как положительные ответы.
3 5 213 -1 14 -1 1012 -1 -1 -1 -114 -1 17 -1 -1
Yes
2 4 1023 -1 -1 5531 36 42 49
No
1 2 091 92
No
В первом примере из условия подходит, например, такой набор глубин:
| $$$13$$$ | $$$13$$$ | $$$14$$$ | $$$12$$$ | $$$10$$$ |
| $$$12$$$ | $$$14$$$ | $$$16$$$ | $$$14$$$ | $$$12$$$ |
| $$$14$$$ | $$$16$$$ | $$$17$$$ | $$$15$$$ | $$$13$$$ |
Во втором примере из условия заполнить ячейки с неизвестными глубинами невозможно. С одной стороны, неизвестная глубина рядом с $$$23$$$ должна быть не больше $$$33$$$. С другой стороны, неизвестная глубина рядом с $$$55$$$ должна быть не меньше $$$45$$$. Значит, разность между ними составляет как минимум $$$12$$$ — противоречие.
В третьем примере из условия противоречие содержится в уже замеренных глубинах. Дно должно быть абсолютно ровным, но соседние глубины отличаются на $$$1$$$.