В Нижнем Новгороде идëт $$$2221$$$ год. Люди уже давно живут в гигантских небоскрëбах и передвигаются на летающих машинах. Под землëй был обнаружен старый город - отголосок далëкого прошлого. Туда стали водить экскурсии, а это место прозвали Нижний Нижний Новгород. И вот недавно там обнаружили старинное метро, некоторые станции которого нужно отреставрировать, чтобы проводить экскурсии и там. Рабочее название у древней подземки - Нижний Нижний Нижний Новгород. Старинное нижегородское метро представляет из себя $$$n$$$ станций. Некоторые пары станций соединены двунаправленными туннелями. Всего таких туннелей $$$m$$$. Рабочие пронумеровали станции числами от $$$1$$$ до $$$n$$$. Цена реставрации станции под номером $$$i$$$ равна $$$c_i$$$ рублей. Реставрация происходит так:

Сначала выбирается целое число $$$s\ (1 \leq s \leq n)$$$ - номер стартовой станции. Затем рабочие рассматривают все станции, до которых можно доехать от стартовой не более чем по $$$d$$$ туннелям, в том числе и сама станция под номером $$$s$$$. Несколько (больше нуля) станций из рассматриваемых будут реставрировать, однако, деньги на реставрацию выделяют суммами по $$$k$$$ рублей, поэтому требуется, чтобы суммарная стоимость реставрации выбранных станций делилась на $$$k$$$. Вам нужно для всех возможных стартовых станций $$$i$$$ от $$$1$$$ до $$$n$$$ сказать, какое должно быть минимальное $$$d$$$, чтобы среди всех рассмотренных станций можно было выбрать несколько таких, что суммарная стоимость их реставрации делилась на $$$k$$$. Заметьте, что стартовая станция не обязательно будет выбрана для реставрации.