#include <iostream.h>
#include <fstream.h>
#include <stdio.h>

enum State {load, unload, idle, moving};

struct Shipment {
  int t,o,d,w;
  bool valid;
};


struct Robot {
  State state;
  long maxLoad;
  //  double loadSum;
  int timeInLoad;
  int pos;
  Shipment sm;
};

Robot transrob[110];


Shipment shipments[1100];
int shipmentN;

double requestSum;
double idleSum;

long n,m;
long time;


void simulate() {
  int idleList[100];
  int idleN;
  bool over=false;

  idleSum = 0;
  requestSum = 0;

  while(!over) {
    idleN=0;
    //    port = time % n;

    for(int i=0; i<m; i++) {
      switch(transrob[i].state) {
      case idle : 
	idleList[idleN] = i;
	idleN++;
	break;
      case moving : 
	if(transrob[i].sm.d == transrob[i].pos) {
	  transrob[i].state = unload;
	  transrob[i].timeInLoad = 5;
	} else
	  transrob[i].pos = transrob[i].pos % n +1;
      case load :
	if(transrob[i].timeInLoad > 0)
	  transrob[i].timeInLoad--;
	else
	  transrob[i].state=moving;
      case unload :
	if(transrob[i].timeInLoad > 0)
	  transrob[i].timeInLoad--;
	else
	  transrob[i].state=idle;
      }      
    }
    bool traverse = true;
    int i;
    idleSum+=idleN;
    for(i=0; i<shipmentN && traverse; i++) {
      if(shipments[i].t > time)
	traverse = false;
      else {
	if(shipments[i].valid) {
	  // find a robot	
	  bool found = false;
	  int bestbot;
	  for(int j=0; j<idleN; j++) {
	    if(transrob[j].state == idle && transrob[j].maxLoad >= shipments[i].w) {
	      if(found) {
		if( (shipments[i].o-transrob[i].pos+n)%n <= (shipments[i].o-transrob[bestbot].pos+n)%n ) {
		  if( bestbot > i)
		    bestbot = i;
		}
	      } else {
		found = true;
		bestbot=j;
	      }
	    }
	  }
	  if( found ) { // really one found
	    requestSum += time - shipments[i].t;
	    transrob[bestbot].state = load;
	    transrob[bestbot].timeInLoad = 5;
	    transrob[bestbot].sm = shipments[i];
	  }
	}
      }
    }
    if(idleN == n && i == shipmentN) { // all robots idle && no more req
      printf("Average wait time   = %.3f minutes\n", (float)requestSum / (float)shipmentN);
      printf("Average utilization = %.3f %%\n", (float)idleSum / (float)time);

      return;
    }    
    //    cout << "time " << endl;
    time ++;
  }
}


int main() {
  ifstream in("centauri.in");
  
  in >> n;
  in >> m;
  while( n>0 && m > 0 ) {
    time = 0;
    for(long i=0; i < m; i++) {
      //      transrob[i].loadSum=0;
      transrob[i].state=idle;
      transrob[i].maxLoad=0;
    }
    for(long i=0; i < m; i++) in >> transrob[i].maxLoad;

    shipmentN=0;
    int t,o,d,w;
    in >> t; in >> o; in >> d; in >> w;
    while(!(t == -1 && o == -1 && d == -1 && w ==-1)) {
      shipments[shipmentN].t = t;
      shipments[shipmentN].o = o;
      shipments[shipmentN].d = d;
      shipments[shipmentN].w = w;
      shipments[shipmentN].valid = true;

      shipmentN++;
      in >> t; in >> o; in >> d; in >> w;
    }
    
    simulate();
    in >> n; in >> m;
    
  }
  
  
  return 0;
}