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\)).
Примечание
Во втором запросе первого набора входных данных, \(A = [9, 5, 5, 2]\). Поэтому сумма равна \(1 \cdot 9 + 2 \cdot 5 + 3 \cdot 5 + 4 \cdot 2 = 42\).