OIG III - aqu

// https://szkopul.edu.pl/problemset/problem/J4wIQqR4YCpTUr-d-in1DKnt/site/?key=statement
// OIG III (3 etap)

#include <algorithm>
#include <array>
#include <iostream>

constexpr int MAX_N = 1000 + 7;

std::array<std::array<long long, 2 * MAX_N>, 2 * MAX_N> t;

int x(int a, int b, int n) {
    return -b + a + n;
}

int y(int a, int b) {
    return a + b - 1;
}

int main() {
    std::ios_base::sync_with_stdio(0);
    std::cin.tie(0);
    std::cout.tie(0);

    int n, r;
    std::cin >> n >> r;

    long long pom = 0;
    int px = 0, py = 0, kx = 0, ky = 0;

    for (int b = 1; b <= n; b++) {
        for (int a = 1; a <= n; a++) {
            std::cin >> t[x(a, b, n)][y(a, b)];
        }
    }

    for (int b = 1; b < n * 2; b++) {
        for (int a = 1; a < n * 2; a++) {
            t[a][b] += t[a][b - 1] + t[a - 1][b] - t[a - 1][b - 1];
        }
    }

    int rx, ry, l, xx, yy;
    int x1, x2, y1, y2;
    long long prawy_gorny = 0, lewy_gorny = 0, lewy_dolny = 0;
    for (int a = 0; a < r; a++) {
        std::cin >> ry >> rx >> l;

        xx = x(rx, ry, n);
        yy = y(rx, ry);

        x1 = std::max(1, xx - l);
        y1 = std::max(1, yy - l);
        x2 = std::min(2 * n - 1, xx + l);
        y2 = std::min(2 * n - 1, yy + l);
        std::cout << t[x2][y2] + t[x1 - 1][y1 - 1] - t[x1 - 1][y2] - t[x2][y1 - 1] << std::endl;
    }

    return 0;
}