На човні у магазин
Limits: 2 sec., 256 MiB
Зеник знає, що магазини “4/7”, в яких є знижки на продукти для канапок, розміщені в селах вздовж річки Дністер. Він знайшов в гуртожитку човен (чого тільки там не знайдеш) і планує на ньому поплисти по дешеві інгредієнти. Усе, що він знає про цю річку, що початково через неї тече w літрів води за годину, а також вздовж річки розташовано n сіл в яких є струмки, що впадають у Дністер.
Зеник зробить усе для того аби дістати їжу, отож він вирішив, що йому необхідно дізнатись для кожного села скільки літрів води за годину протікає в Дністрі повз дане село. Він знає порядок сіл вздовж річки, а також скільки є струмків, перед відповідним селом, які впадають у Дністер та скільки по кожному з них тече літрів води за годину. Допоможіть йому визначити необхідну інформацію.
Input
У першому рядку задано два цілих числа n і w — кількість сіл та початкова кількість води, що протікає за годину часу.
У наступних n рядках задано інформацію про струмки в відповідному селі у такому форматі: перше число в рядку k відповідає за кількість струмків в цьому селі, після нього є ще k цілих чисел vi — скільки води протікає за годину у відповідному струмку.
Села задані в порядку за течією річки.
Output
Виведіть n чисел, по одному в рядок: кількість літрів води за годину, яка протікає в Дністрі повз відповідне село (в порядку в якому вони задані).
Constraints
1≤n,k≤105,
сума по всіх k≤105,
15 тестів з обмеженнями 1≤w,vi≤104,
10 тестів з обмеженнями 1≤w,vi≤109.
Samples
| Input (stdin) | Output (stdout) |
|---|---|
| 3 4 3 1 1 5 2 4 7 2 7 11 | 11 22 40 |
Notes
Зауважте, що струмки збільшують кількість води що протікає в Дністрі за годину.