H. Сложная демоническая задача
ограничение по времени на тест
3.5 секунд
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Swing открывает фабрику блинов! Хорошая фабрика блинов должна хорошо уметь разравнивать вещи, поэтому Swing собирается протестировать свое новое оборудование на 2D матрицах.

Swing дана матрица $$$n \times n$$$ $$$M$$$, содержащая положительные целые числа. У него есть $$$q$$$ запросов, которые он хочет вам задать.

Для каждого запроса он дает вам четыре целых числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$, $$$y_2$$$ и просит вас разровнять подматрицу, ограниченную $$$(x_1, y_1)$$$ и $$$(x_2, y_2)$$$, в массив $$$A$$$. Формально, $$$A = [M_{(x1,y1)}, M_{(x1,y1+1)}, \ldots, M_{(x1,y2)}, M_{(x1+1,y1)}, M_{(x1+1,y1+1)}, \ldots, M_{(x2,y2)}]$$$.

Следующее изображение иллюстрирует разравнивание подматрицы, ограниченной красными пунктирными линиями. Оранжевые стрелки указывают направление, в котором элементы подматрицы добавляются в конец $$$A$$$, а $$$A$$$ показан внизу изображения.

После этого он спрашивает вас о значении $$$\sum_{i=1}^{|A|} A_i \cdot i$$$ (сумма $$$A_i \cdot i$$$ по всем $$$i$$$).

Входные данные

Первая строка содержит целое число $$$t$$$ ($$$1 \leq t \leq 10^3$$$) — количество наборов входных данных.

Первая строка каждого теста содержит два целых числа $$$n$$$ и $$$q$$$ ($$$1 \leq n \leq 2000, 1 \leq q \leq 10^6$$$) — размер $$$M$$$ и количество запросов.

Следующие $$$n$$$ строк содержат по $$$n$$$ целых чисел, $$$i$$$-я из которых содержит $$$M_{(i,1)}, M_{(i,2)}, \ldots, M_{(i,n)}$$$ ($$$1 \leq M_{(i, j)} \leq 10^6$$$).

Следующие $$$q$$$ строк содержат четыре целых числа $$$x_1$$$, $$$y_1$$$, $$$x_2$$$ и $$$y_2$$$ ($$$1 \leq x_1 \leq x_2 \leq n, 1 \leq y_1 \leq y_2 \leq n$$$) — границы запроса.

Гарантируется, что сумма $$$n$$$ по всем тестовым случаям не превышает $$$2000$$$, а сумма $$$q$$$ по всем тестовым случаям не превышает $$$10^6$$$.

Выходные данные

Для каждого теста выведите результаты $$$q$$$ запросов на новой строке.

Пример
Входные данные
2
4 3
1 5 2 4
4 9 5 3
4 5 2 3
1 5 5 2
1 1 4 4
2 2 3 3
1 2 4 3
3 3
1 2 3
4 5 6
7 8 9
1 1 1 3
1 3 3 3
2 2 2 2
Выходные данные
500 42 168 
14 42 5
Примечание

Во втором запросе первого набора входных данных, $$$A = [9, 5, 5, 2]$$$. Поэтому сумма равна $$$1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42$$$.