На човні у магазин

Limits: 2 sec., 256 MiB

Зеник знає, що магазини “4/7”, в яких є знижки на продукти для канапок, розміщені в селах вздовж річки Дністер. Він знайшов в гуртожитку човен (чого тільки там не знайдеш) і планує на ньому поплисти по дешеві інгредієнти. Усе, що він знає про цю річку, що початково через неї тече \(w\) літрів води за годину, а також вздовж річки розташовано \(n\) сіл в яких є струмки, що впадають у Дністер.

Зеник зробить усе для того аби дістати їжу, отож він вирішив, що йому необхідно дізнатись для кожного села скільки літрів води за годину протікає в Дністрі повз дане село. Він знає порядок сіл вздовж річки, а також скільки є струмків, перед відповідним селом, які впадають у Дністер та скільки по кожному з них тече літрів води за годину. Допоможіть йому визначити необхідну інформацію.

Input

У першому рядку задано два цілих числа \(n\) і \(w\) — кількість сіл та початкова кількість води, що протікає за годину часу.

У наступних \(n\) рядках задано інформацію про струмки в відповідному селі у такому форматі: перше число в рядку \(k\) відповідає за кількість струмків в цьому селі, після нього є ще \(k\) цілих чисел \(v_i\) — скільки води протікає за годину у відповідному струмку.

Села задані в порядку за течією річки.

Output

Виведіть \(n\) чисел, по одному в рядок: кількість літрів води за годину, яка протікає в Дністрі повз відповідне село (в порядку в якому вони задані).

Constraints

\(1 \le n, k \le 10^5\),

сума по всіх \(k \le 10^5\),

\(15\) тестів з обмеженнями \(1 \le w, v_i \le 10^4\),

\(10\) тестів з обмеженнями \(1 \le w, v_i \le 10^9\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 4 3 1 1 5 2 4 7 2 7 11	11 22 40

Notes

Зауважте, що струмки збільшують кількість води що протікає в Дністрі за годину.