Условие:
Дано масив a довжини n та число s, для кожного індексу i(1≤i≤n) потрібно знайти підмасив, який включає елемент з індексу i і має максимальну можливу суму, що не перевищує s, і або вивести цю суму, або сказати, що це неможливо.
Більш формально, для кожного i(1≤i≤n) потрібно знайти такі l,r(l≤i≤r), що ∑ \nj=l\nr
a \nj
≤s і ∑ \nj=l\nr
a \nj
є найбільшою можливою, та вивести ∑ \nj=l\nr
a \nj
.
Вхідні дані
Кожен тест містить кілька тестових випадків. Перший рядок містить кількість тестових випадків t(1≤t≤4⋅10
5
). Опис тестових випадків йде далі.
Перший рядок кожного тестового випадку містить два цілі числа n (1≤n≤10
6
) та s (−10
9
≤s≤10
9
).
Другий рядок містить n цілих чисел a \ni
(−10
9
≤a \ni
≤10
9
), що представляють елементи масиву.
Гарантується, що сума n по всіх тестових випадках не перевищує 10
6
.
Вихідні дані
Для кожного тестового випадку, для кожного i (1≤i≤n), виведіть або ціле число — відповідь для цього i, або x, якщо це неможливо.
