#include <stdlib.h>
#include <stdio.h>
#include <string.h>
#include <math.h>
#include "courier.h"

#define TRUE 1
#define FALSE 0

// *****************
// Private variables
// *****************
int _R, _C, _M, _Q, _V;
int *_requests;
double *_graph, *_edges;

// *************
// Scoring tools
// *************

void fail(const char* s)
{
  fprintf(stderr, s);
  printf("%lf\n", 0.);
  exit(1);
}

// *****************************
// Priority queue data structure
// *****************************

typedef struct
{
  int size;
  int *key;
  double *value;
} priority_queue_t;

void priority_queue_init(priority_queue_t *q, int max_size)
{
  q->size = 0;
  q->key = (int*)malloc(max_size * sizeof(int));
  q->value = (double*)malloc(max_size * sizeof(double));
}

void priority_queue_destruct(priority_queue_t *q)
{
  free(q->key);
  free(q->value);
}

int priority_queue_empty(priority_queue_t *q)
{
  return q->size == 0;
}

void priority_queue_push(priority_queue_t *q, int k, double v)
{
  q->key[q->size] = k;
  q->value[q->size] = v;
  q->size++;
  
  int node = q->size - 1;
  while (node > 0)
  {
    int father = (node - 1) / 2;
    if (q->value[father] > q->value[node])
    {
      double v_tmp = q->value[father];
      q->value[father] = q->value[node];
      q->value[node] = v_tmp;
      int k_tmp = q->key[father];
      q->key[father] = q->key[node];
      q->key[node] = k_tmp;
    }
    node = father;
  }
}

int priority_queue_pop(priority_queue_t *q)
{
  int result = q->key[0];
  
  q->size--;
  q->key[0] = q->key[q->size];
  q->value[0] = q->value[q->size];
  
  int node = 0;
  while (2 * node + 1 < q->size)
  {
    int child;
    if (2*node+2 < q->size && q->value[2*node+2] < q->value[2*node+1])
      child = 2 * node + 2;
    else
      child = 2 * node + 1;
    if (q->value[child] < q->value[node])
    {
      double v_tmp = q->value[child];
      q->value[child] = q->value[node];
      q->value[node] = v_tmp;
      int k_tmp = q->key[child];
      q->key[child] = q->key[node];
      q->key[node] = k_tmp;
    }
    node = child;
  }
  return result;
}

// ***
// API
// ***

double query(int rStart, int cStart, int length, char* path)
{
  if (_Q-- <= 0) fail("To many queries to the API\n");
  
  int *pathnodes = (int*) calloc(2*_V+10, sizeof(int));
  int *seen = (int*) calloc(_V+10, sizeof(int));

  double score = 0;
  int r = rStart, c = cStart;
  for (int i=0; i<length; i++)
  {
    int act = r * _C + c;
    pathnodes[i] = act;
    if (seen[act]) fail("Non-simple path\n");
    seen[act] = TRUE;
    if (path[i] == 'N') r--;
    else if (path[i] == 'S') r++;
    else if (path[i] == 'W') c--;
    else if (path[i] == 'E') c++;
    else fail("Invalid path (invalid character)\n");
    if (r < 0 || r >= _R || c < 0 || c >= _C)
      fail("Invalid path (walked out of city)\n");
    int next = r * _C + c;
    if (path[i] == 'N') score += _edges[2*next+1];
    if (path[i] == 'S') score += _edges[2*act+1];
    if (path[i] == 'W') score += _edges[2*next];
    if (path[i] == 'E') score += _edges[2*act];
  }
  if (seen[r * _C + c]) fail("Non-simple path\n");
  score -= _graph[rStart*_C+cStart + _V*(r*_C+c)];
  
  // Make sure score is positive
  if (score < 1e-8) score = 0;
  free(pathnodes);
  free(seen);

  return score;
}


// Spot the functional programmer.
double horizVertPath(int rCur, int cCur, int rEnd, int cEnd, int vertFirst) {
  if (cCur == cEnd && rCur == rEnd) {
    return 0;
  } else if ((vertFirst || cCur == cEnd) && rCur != rEnd) {
    // if there is vertical movement left to do, and either
    // we are set to moving vertical first, or there is no horizontal movement to make
    // Then we step vertically towards rEnd.
    if (rCur < rEnd) {
      // We are moving down.
      int cur = rCur * _C + cCur;
      double edgeLen = _edges[2*cur+1];
      return horizVertPath(rCur + 1, cCur, rEnd, cEnd, vertFirst) + edgeLen;
    } else {
      // We are moving up
      int cur = (rCur-1) * _C + cCur;
      double edgeLen = _edges[2*cur+1];
      return horizVertPath(rCur - 1, cCur, rEnd, cEnd, vertFirst) + edgeLen;
    }
  } else {
    // We must be moving horizontally if we are not moving vertically
    if (cCur < cEnd) {
      // We are moving right.
      int cur = rCur * _C + cCur;
      double edgeLen = _edges[2*cur];
      return horizVertPath(rCur, cCur + 1, rEnd, cEnd, vertFirst) + edgeLen;
    } else {
      // We are moving left
      int cur = rCur * _C + (cCur-1);
      double edgeLen = _edges[2*cur];
      return horizVertPath(rCur, cCur - 1, rEnd, cEnd, vertFirst) + edgeLen;
    }
  }
}

int main(int argc, char **argv)
{
  scanf("%d%d%d%d", &_R, &_C, &_M, &_Q);
  
  // Init graph
  _V = _R * _C;
  
  // _graph[i+_V*j] = distance from i to j
  _graph = (double*)malloc(_V * _V * sizeof(double));
  for (int i=0; i<_V*_V; i++)
    _graph[i] = 1e4;
    
  // _edge[2*i+1] = edge i <-> i+C
  // _edge[2*i] = edge i <-> i+1
  _edges = (double*)malloc(2 * _V * sizeof(double));
  
  for (int r = 0; r < _R; r++) {
    // Read _C-1 horizontal edges
    for (int c = 0; c < _C-1; c++){
      scanf("%lf", &_edges[2*(r*_C+c)]);
    }
    // Read _C vertical edges coming down from this row
    for (int c = 0; c < _C && r != (_R-1); c++) {
      scanf("%lf", &_edges[2*(r*_C+c)+1]);
    }
  }  
    
  // All pair shortest paths
  priority_queue_t q;
  priority_queue_init(&q, _V);
  for (int start=0; start<_V; start++)
  {
    _graph[start+_V*start] = 0;
    priority_queue_push(&q, start, 0);
    while (!priority_queue_empty(&q))
    {
      int act = priority_queue_pop(&q);
      double act_dist = _graph[start+_V*act];
      int r = act / _C, c = act % _C;
      for (int dr=-1; dr<=1; dr++)
      for (int dc=-1; dc<=1; dc++)
      {
        if (dr == 0 && dc == 0) continue;
        if (dr != 0 && dc != 0) continue;
        if (r+dr < 0 || r+dr >= _R) continue;
        if (c+dc < 0 || c+dc >= _C) continue;
        int next = (r+dr) * _C + (c+dc);
        double delta_dist;
        if (dr == -1) delta_dist = _edges[2*next+1];
        if (dr == 1) delta_dist = _edges[2*act+1];
        if (dc == -1) delta_dist = _edges[2*next];
        if (dc == 1) delta_dist = _edges[2*act];
        if (_graph[start+_V*next] > act_dist + delta_dist)
        {
          _graph[start+_V*next] = act_dist + delta_dist;
          priority_queue_push(&q, next, act_dist + delta_dist);
        }
      }
    }
  }
  priority_queue_destruct(&q);
  
  // Initialize user program
  init(_R, _C, _M, _Q);

  double score = 0;
  
  int length;
  char* path = (char*)malloc(2*_V * sizeof(char));
  int* pathnodes = (int*)malloc(2*_V * sizeof(int));
  int* seen = (int*)malloc(_V * sizeof(int));
 
  double best_path_total = 0, base_path_total = 0, request_path_total = 0;

  memset(seen, 0, _V * sizeof(int));
  for (int i=0; i<_M; i++)
  {
    int rStart, cStart, rEnd, cEnd;
    scanf("%d%d%d%d", &rStart, &cStart, &rEnd, &cEnd);
    
    _Q = 0; // Forbid queries
    solve(rStart, cStart, rEnd, cEnd, &length, path);
    // Compute the score
    double request_score = 0;
    int r = rStart, c = cStart;
    for (int i=0; i<length; i++)
    { 
      int act = r * _C + c;
      pathnodes[i] = act;
      if (seen[act]) fail("Non-simple path\n");
      seen[act] = TRUE;
      if (path[i] == 'N') r--;
      else if (path[i] == 'S') r++;
      else if (path[i] == 'W') c--;
      else if (path[i] == 'E') c++;
      else fail("Invalid path (invalid character)\n");
      if (r < 0 || r >= _R || c < 0 || c >= _C)
        fail("Invalid path (walked out of city)\n");
      int next = r * _C + c;
      if (path[i] == 'N') request_score += _edges[2*next+1];
      if (path[i] == 'S') request_score += _edges[2*act+1];
      if (path[i] == 'W') request_score += _edges[2*next];
      if (path[i] == 'E') request_score += _edges[2*act];
    }
    if (r != rEnd || c != cEnd)
      fail("Invalid path (Didn't end in correct location)\n");
    if (seen[r * _C + c]) fail("Non-simple path\n");
    for (int node=0; node<length; node++)
      seen[pathnodes[node]] = FALSE;

    double best_score = _graph[rStart*_C+cStart + _V*(rEnd*_C+cEnd)];
    double horizPath = horizVertPath(rStart, cStart, rEnd, cEnd, FALSE);
    double vertPath = horizVertPath(rStart, cStart, rEnd, cEnd, TRUE);
    double base_score = (horizPath + vertPath)/2;

    // Tm = base_score
    // Tf = best_score
    // T  = request_score
    // score = max(0, 100*(max(Tm, Tf + 10e-6) - t)/(max(Tm, Tf + 10e-6) - Tf))
    double maxTerm = fmax(base_score, best_score + 10e-6);
    double s = fmax(0, (maxTerm - request_score)/(maxTerm - best_score));
    
    printf("%lf\n", 100*s);
 
    best_path_total += best_score;
    base_path_total += base_score;
    request_path_total += request_score;
  }
  
  // Tm = base_path_total
  // Tf = best_path_total
  // T  = request_path_total
  // score = max(0, 100*(max(Tm, Tf + 10e-6) - t)/(max(Tm, Tf + 10e-6) - Tf))
  double maxTerm = fmax(base_path_total, best_path_total + 10e-6);
  score = 100 * fmax(0, (maxTerm - request_path_total)/(maxTerm - best_path_total));
 
  printf("Total score: %lf\n", score);
  free(path);
  free(pathnodes);
  free(seen);
}