package contest190816; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.Arrays; import java.util.InputMismatchException; public class E2 { InputStream is; PrintWriter out; String INPUT = ""; void solve() { int n = ni(), m = ni(); int gr = ni()-1, gc = ni()-1; int[][] a = new int[n][]; for(int i = 0;i < n;i++)a[i] = na(m); // (K^2+1)*D <= (H+W)(K^2+99) int B = 100; int[] dr = { 1, 0, -1, 0 }; int[] dc = { 0, 1, 0, -1 }; int[][][] ds = new int[B][n][m]; for(int k = 1;k < B;k++){ for(int i = 0;i < n;i++)Arrays.fill(ds[k][i], Integer.MAX_VALUE / 2); MinHeap q = new MinHeap(n*m); q.add(gr*m+gc, 0); ds[k][gr][gc] = 0; while(q.size() > 0){ int cur = q.argmin(); q.remove(cur); int r = cur/m, c = cur%m; for(int d = 0;d < 4;d++){ int nr = r + dr[d], nc = c + dc[d]; if(nr >= 0 && nr < n && nc >= 0 && nc < m){ int nd = ds[k][r][c] + a[nr][nc] + k*k; if(nd < ds[k][nr][nc]){ ds[k][nr][nc] = nd; q.update(nr*m+nc, nd); } } } } } int D = 506; int[][][] uds = new int[D][n][m]; for(int i = 0;i < D;i++){ for(int j = 0;j < n;j++){ Arrays.fill(uds[i][j], Integer.MAX_VALUE / 2); } } uds[0][gr][gc] = 0; for(int dep = 1;dep < D;dep++){ for(int r = 0;r < n;r++){ for(int c = 0;c < m;c++){ for(int d = 0;d < 4;d++){ int nr = r + dr[d], nc = c + dc[d]; if(nr >= 0 && nr < n && nc >= 0 && nc < m){ int nd = uds[dep-1][r][c] + a[nr][nc]; if(nd < uds[dep][nr][nc]){ uds[dep][nr][nc] = nd; } } } } } } EnvelopeLinear[][] els = new EnvelopeLinear[n][m]; for(int i = 0;i < n;i++){ for(int j = 0;j < m;j++){ els[i][j] = new EnvelopeLinear(300); for(int k = D-1;k >= 1;k--){ if(uds[k][i][j] < 999999999){ els[i][j].add(k, uds[k][i][j]); } } els[i][j].slopes = Arrays.copyOf(els[i][j].slopes, els[i][j].p); els[i][j].intercepts = Arrays.copyOf(els[i][j].intercepts, els[i][j].p); els[i][j].xs = Arrays.copyOf(els[i][j].xs, els[i][j].p); } } int Q = ni(); for(int i = 0;i < Q;i++){ int x = ni()-1, y = ni()-1, K = ni(); if(K < B){ out.println(ds[K][x][y] + (long)K*K+a[gr][gc]); }else{ long ans = els[x][y].min((long)K*K) + (long)K*K+a[gr][gc]; out.println(ans); } } } public static class EnvelopeLinear { public static final long INF = Long.MIN_VALUE; public long[] xs; public long[] intercepts, slopes; public int p; public EnvelopeLinear(int n) { xs = new long[n]; intercepts = new long[n]; slopes = new long[n]; p = 0; } public void clear() { p = 0; } public void add(long slope, long intercept) { assert p == 0 || slopes[p-1] >= slope; while(p > 0){ int i = p-1; if(p > 1 && (intercept+(double)xs[i]*slope <= intercepts[i]+(double)xs[i]*slopes[i] || intercept+xs[i]*slope <= intercepts[i]+xs[i]*slopes[i])){ // x=xs[i] p--; continue; } if(slope == slopes[i]){ if(intercept >= intercepts[i]){ return; }else{ p--; continue; } } // y=sx+i vs y=Sx+I // sx+i=Sx+I // x=(i-I)/(S-s) long num = intercept-intercepts[i]; long den = slopes[i]-slope; long nx = num < 0 ? num/den : (num+den-1)/den; xs[p] = nx; intercepts[p] = intercept; slopes[p] = slope; p++; return; } xs[p] = INF; intercepts[p] = intercept; slopes[p] = slope; p++; } public int argmin(int x) { if(p <= 0)return -1; int ind = Arrays.binarySearch(xs, 0, p, x); if(ind < 0)ind = -ind-2; return ind; } public long min(long x) { if(p <= 0)return Long.MIN_VALUE; int ind = Arrays.binarySearch(xs, 0, p, x); if(ind < 0)ind = -ind-2; return slopes[ind]*x + intercepts[ind]; } } public static class MinHeap { public int[] a; public int[] map; public int[] imap; public int n; public int pos; public static int INF = Integer.MAX_VALUE; public MinHeap(int m) { n = m+2; a = new int[n]; map = new int[n]; imap = new int[n]; Arrays.fill(a, INF); Arrays.fill(map, -1); Arrays.fill(imap, -1); pos = 1; } public int add(int ind, int x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); } return ret != -1 ? a[ret] : x; } public int update(int ind, int x) { int ret = imap[ind]; if(imap[ind] < 0){ a[pos] = x; map[pos] = ind; imap[ind] = pos; pos++; up(pos-1); }else{ int o = a[ret]; a[ret] = x; up(ret); down(ret); // if(a[ret] > o){ // up(ret); // }else{ // down(ret); // } } return x; } public int remove(int ind) { if(pos == 1)return INF; if(imap[ind] == -1)return INF; pos--; int rem = imap[ind]; int ret = a[rem]; map[rem] = map[pos]; imap[map[pos]] = rem; imap[ind] = -1; a[rem] = a[pos]; a[pos] = INF; map[pos] = -1; up(rem); down(rem); return ret; } public int min() { return a[1]; } public int argmin() { return map[1]; } public int size() { return pos-1; } private void up(int cur) { for(int c = cur, p = c>>>1;p >= 1 && a[p] > a[c];c>>>=1, p>>>=1){ int d = a[p]; a[p] = a[c]; a[c] = d; int e = imap[map[p]]; imap[map[p]] = imap[map[c]]; imap[map[c]] = e; e = map[p]; map[p] = map[c]; map[c] = e; } } private void down(int cur) { for(int c = cur;2*c < pos;){ int b = a[2*c] < a[2*c+1] ? 2*c : 2*c+1; if(a[b] < a[c]){ int d = a[c]; a[c] = a[b]; a[b] = d; int e = imap[map[c]]; imap[map[c]] = imap[map[b]]; imap[map[b]] = e; e = map[c]; map[c] = map[b]; map[b] = e; c = b; }else{ break; } } } } void run() throws Exception { // int n = 250, m = 250, q = 500000; // Random gen = new Random(); // StringBuilder sb = new StringBuilder(); // sb.append(n + " "); // sb.append(m + " "); // sb.append(1 + " "); // sb.append(1 + " "); // for (int i = 0; i < n*m; i++) { // sb.append(gen.nextInt(99)+1 + " "); // } // sb.append(q + " "); // for (int i = 0; i < q; i++) { // sb.append(gen.nextInt(n)+1 + " "); // sb.append(gen.nextInt(m)+1 + " "); // sb.append(gen.nextInt(1000000)+1 + " "); // } // INPUT = sb.toString(); // is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); long s = System.currentTimeMillis(); solve(); out.flush(); if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // Thread t = new Thread(null, null, "~", Runtime.getRuntime().maxMemory()){ // @Override // public void run() { // long s = System.currentTimeMillis(); // solve(); // out.flush(); // if(!INPUT.isEmpty())tr(System.currentTimeMillis()-s+"ms"); // } // }; // t.start(); // t.join(); } public static void main(String[] args) throws Exception { new E2().run(); } private byte[] inbuf = new byte[1024]; public int lenbuf = 0, ptrbuf = 0; private int readByte() { if(lenbuf == -1)throw new InputMismatchException(); if(ptrbuf >= lenbuf){ ptrbuf = 0; try { lenbuf = is.read(inbuf); } catch (IOException e) { throw new InputMismatchException(); } if(lenbuf <= 0)return -1; } return inbuf[ptrbuf++]; } private boolean isSpaceChar(int c) { return !(c >= 33 && c <= 126); } private int skip() { int b; while((b = readByte()) != -1 && isSpaceChar(b)); return b; } private double nd() { return Double.parseDouble(ns()); } private char nc() { return (char)skip(); } private String ns() { int b = skip(); StringBuilder sb = new StringBuilder(); while(!(isSpaceChar(b))){ // when nextLine, (isSpaceChar(b) && b != ' ') sb.appendCodePoint(b); b = readByte(); } return sb.toString(); } private char[] ns(int n) { char[] buf = new char[n]; int b = skip(), p = 0; while(p < n && !(isSpaceChar(b))){ buf[p++] = (char)b; b = readByte(); } return n == p ? buf : Arrays.copyOf(buf, p); } private int[] na(int n) { int[] a = new int[n]; for(int i = 0;i < n;i++)a[i] = ni(); return a; } private long[] nal(int n) { long[] a = new long[n]; for(int i = 0;i < n;i++)a[i] = nl(); return a; } private char[][] nm(int n, int m) { char[][] map = new char[n][]; for(int i = 0;i < n;i++)map[i] = ns(m); return map; } private int[][] nmi(int n, int m) { int[][] map = new int[n][]; for(int i = 0;i < n;i++)map[i] = na(m); return map; } private int ni() { return (int)nl(); } private long nl() { long num = 0; int b; boolean minus = false; while((b = readByte()) != -1 && !((b >= '0' && b <= '9') || b == '-')); if(b == '-'){ minus = true; b = readByte(); } while(true){ if(b >= '0' && b <= '9'){ num = num * 10 + (b - '0'); }else{ return minus ? -num : num; } b = readByte(); } } private static void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } }