#include <iostream>
#include <cstdlib>
#include <stdio.h>
#include <string>
#include <set>
#include <fstream>
#include <algorithm>
#include <math.h>
#include <map>
#include <queue>
#include <bitset>
using namespace std;
const int INF = 1e9 ;
queue < int > q[ 100000 ] ;
int S[ 100000 ] , n, m, queue_time, queue_sum, out, current_time;
vector < int > g[ 100000 ] ;
set < pair < int , int > > s;
bool Comp ( int a, int b)
{
return S[ a] < S[ b] ;
}
int main ( )
{
cin >> m;
for ( int i = 0 ; i <= m; i++ )
scanf ( "%d" , & S[ i] ) ;
for ( int i = 1 ; i < m; i++ )
{
char c = ' ' ;
int a;
while ( c ! = '\n ' )
{
scanf ( "%d%c" , & a, & c) ;
g[ i] .push_back ( a) ;
}
sort ( g[ i] .begin ( ) , g[ i] .end ( ) , Comp) ;
}
g[ 0 ] .push_back ( 1 ) ;
g[ m] .push_back ( m + 1 ) ;
cin >> n;
for ( int i = 1 ; i <= n; i++ )
{
q[ 0 ] .push ( i) ;
s.insert ( make_pair ( S[ 0 ] , 0 ) ) ;
}
while ( out ! = n)
{
pair < int , int > top = * s.begin ( ) ;
current_time = top.first ;
int server = top.second , query = q[ server] .front ( ) ;
printf ( "Query %d left server %d at time %d\n " , query, server, current_time) ;
q[ server] .pop ( ) ;
s.erase ( s.begin ( ) ) ;
if ( ! q[ server] .empty ( ) )
{
s.insert ( make_pair ( current_time + S[ server] , server) ) ;
}
if ( server == m)
{
out++ ;
continue ;
}
int index, mn = INF;
for ( int i = 0 ; i < g[ server] .size ( ) ; i++ )
{
int to = g[ server] [ i] ;
if ( S[ to] * ( q[ to] .size ( ) + 1 ) < mn)
{
mn = S[ to] * ( q[ to] .size ( ) + 1 ) ;
index = to;
}
}
if ( q[ index] .size ( ) ) queue_sum + = S[ index] * ( q[ index] .size ( ) - 1 ) * ( q[ index] .size ( ) - 1 ) ;
if ( q[ index] .size ( ) ) queue_time + = S[ index] * ( q[ index] .size ( ) - 1 ) ;
q[ index] .push ( query) ;
if ( q[ index] .size ( ) == 1 )
{
s.insert ( make_pair ( current_time + S[ index] , index) ) ;
}
}
if ( queue_time) printf ( "Average Lq = %lf\n " , ( double ) queue_sum / ( double ) queue_time) ;
printf ( "Average time in queue = %lf" , ( double ) queue_time / ( double ) n) ;
}
I2luY2x1ZGUgPGlvc3RyZWFtPgojaW5jbHVkZSA8Y3N0ZGxpYj4KI2luY2x1ZGUgPHN0ZGlvLmg+CiNpbmNsdWRlIDxzdHJpbmc+CiNpbmNsdWRlIDxzZXQ+CiNpbmNsdWRlIDxmc3RyZWFtPgojaW5jbHVkZSA8YWxnb3JpdGhtPgojaW5jbHVkZSA8bWF0aC5oPgojaW5jbHVkZSA8bWFwPgojaW5jbHVkZSA8cXVldWU+CiNpbmNsdWRlIDxiaXRzZXQ+Cgp1c2luZyBuYW1lc3BhY2Ugc3RkOwoKY29uc3QgaW50IElORiA9IDFlOTsKCnF1ZXVlIDxpbnQ+IHFbMTAwMDAwXTsKCmludCBTWzEwMDAwMF0sIG4sIG0sIHF1ZXVlX3RpbWUsIHF1ZXVlX3N1bSwgb3V0LCBjdXJyZW50X3RpbWU7Cgp2ZWN0b3IgPGludD4gZ1sxMDAwMDBdOwoKc2V0IDxwYWlyIDxpbnQsIGludD4gPiBzOwoKYm9vbCBDb21wIChpbnQgYSwgaW50IGIpCnsKCXJldHVybiBTW2FdIDwgU1tiXTsKfQoKaW50IG1haW4gKCkKewoJY2luID4+IG07CgoJZm9yIChpbnQgaSA9IDA7IGkgPD0gbTsgaSsrKQoJCXNjYW5mICgiJWQiLCAmU1tpXSk7CgoJZm9yIChpbnQgaSA9IDE7IGkgPCBtOyBpKyspCgl7CgkJY2hhciBjID0gJyAnOwoJCWludCBhOwoKCQl3aGlsZSAoYyAhPSAnXG4nKQoJCXsKCQkJc2NhbmYgKCIlZCVjIiwgJmEsICZjKTsKCQkJZ1tpXS5wdXNoX2JhY2sgKGEpOwoJCX0KCgkJc29ydCAoZ1tpXS5iZWdpbiAoKSwgZ1tpXS5lbmQgKCksIENvbXApOwoJfQoKCWdbMF0ucHVzaF9iYWNrICgxKTsKCWdbbV0ucHVzaF9iYWNrIChtICsgMSk7CgoJY2luID4+IG47CgoJZm9yIChpbnQgaSA9IDE7IGkgPD0gbjsgaSsrKQoJewoJCXFbMF0ucHVzaCAoaSk7CgkJcy5pbnNlcnQgKG1ha2VfcGFpciAoU1swXSwgMCkpOwoJfQoKCXdoaWxlIChvdXQgIT0gbikKCXsKCQlwYWlyIDxpbnQsIGludD4gdG9wID0gKnMuYmVnaW4gKCk7CgkJY3VycmVudF90aW1lID0gdG9wLmZpcnN0OwoJCWludCBzZXJ2ZXIgPSB0b3Auc2Vjb25kLCBxdWVyeSA9IHFbc2VydmVyXS5mcm9udCAoKTsKCgkJcHJpbnRmICgiUXVlcnkgJWQgbGVmdCBzZXJ2ZXIgJWQgYXQgdGltZSAlZFxuIiwgcXVlcnksIHNlcnZlciwgY3VycmVudF90aW1lKTsKCgkJcVtzZXJ2ZXJdLnBvcCAoKTsKCQlzLmVyYXNlIChzLmJlZ2luICgpKTsKCQlpZiAoIXFbc2VydmVyXS5lbXB0eSAoKSkKCQl7CgkJCXMuaW5zZXJ0IChtYWtlX3BhaXIgKGN1cnJlbnRfdGltZSArIFNbc2VydmVyXSwgc2VydmVyKSk7CgkJfQoKCQlpZiAoc2VydmVyID09IG0pCgkJewoJCQlvdXQrKzsKCQkJY29udGludWU7CgkJfQoKCQlpbnQgaW5kZXgsIG1uID0gSU5GOwoKCQlmb3IgKGludCBpID0gMDsgaSA8IGdbc2VydmVyXS5zaXplICgpOyBpKyspCgkJewoJCQlpbnQgdG8gPSBnW3NlcnZlcl1baV07CgoJCQlpZiAoU1t0b10gKiAocVt0b10uc2l6ZSAoKSArIDEpIDwgbW4pCgkJCXsKCQkJCW1uID0gU1t0b10gKiAocVt0b10uc2l6ZSAoKSArIDEpOwoJCQkJaW5kZXggPSB0bzsKCQkJfQoJCX0KCgkJaWYgKHFbaW5kZXhdLnNpemUgKCkpIHF1ZXVlX3N1bSArPSBTW2luZGV4XSAqIChxW2luZGV4XS5zaXplICgpIC0gMSkgKiAocVtpbmRleF0uc2l6ZSAoKSAtIDEpOwoJCWlmIChxW2luZGV4XS5zaXplICgpKSBxdWV1ZV90aW1lICs9IFNbaW5kZXhdICogKHFbaW5kZXhdLnNpemUgKCkgLSAxKTsKCgkJcVtpbmRleF0ucHVzaCAocXVlcnkpOwoJCWlmIChxW2luZGV4XS5zaXplICgpID09IDEpCgkJewoJCQlzLmluc2VydCAobWFrZV9wYWlyIChjdXJyZW50X3RpbWUgKyBTW2luZGV4XSwgaW5kZXgpKTsKCQl9Cgl9CgoJaWYgKHF1ZXVlX3RpbWUpIHByaW50ZiAoIkF2ZXJhZ2UgTHEgPSAlbGZcbiIsIChkb3VibGUpIHF1ZXVlX3N1bSAvIChkb3VibGUpIHF1ZXVlX3RpbWUpOwoJcHJpbnRmICgiQXZlcmFnZSB0aW1lIGluIHF1ZXVlID0gJWxmIiwgKGRvdWJsZSkgcXVldWVfdGltZSAvIChkb3VibGUpIG4pOwoKfQ==