Для масиву цілих чисел визначимо як найбільшу суму елементів будь-якого з його послідовних підмасивів (можливо, порожнього). Наприклад, f([-1, -2, -1]) = 0, а f([1, -2, 3, 1, -2, 1]) дорівнює , що досягається на .
Також, для двох масивів визначимо concat(a, b) як їхню конкатенацію. Наприклад, concat([1, 3], [2, 4]) = [1, 3, 2, 4]).
Вам надано масивів arr_1, arr_2, \ldots, arr_n. Знайдіть суму f(concat(arr_i, arr_j)) по всіх парах цілих чисел з 1 \leq i, j \leq n.
Перший рядок містить одне ціле число (1 \le t \le 10^4) — кількість тестових наборів. Далі йде опис тестових наборів.
Перший рядок кожного тестового набору містить одне ціле число (1 \leq n \leq 4\cdot 10^5) — кількість масивів.
-й з наступних рядків містить ціле число k_i та k_i цілих чисел arr_{i, 1}, arr_{i, 2}, \ldots, arr_{i, k_i} (1 \leq k_i \leq 4\cdot 10^5, -10^7 \leq arr_{i, j} \leq 10^7) — довжину arr_i та його елементи.
Гарантується, що сума довжин усіх масивів у всіх тестових наборах не перевищує 4\cdot 10^5.
Для кожного тестового набору виведіть одне ціле число — суму f(concat(arr_i, arr_j)) по всіх парах цілих чисел з 1 \leq i, j \leq n.
Приклад
У першому тестовому наборі необхідно знайти суму наступних підмасивів: f([1, 1, -10, 1, 1, -10]) = 2, f([1, 1, -10, 2, 2]) = 4, f([2, 2, 1, 1, -10]) = 6, f([2, 2, 2, 2]) = 8.
Загальна сума дорівнює 2 + 4 + 6 + 8 = 20.