#----------------------------------------------------------------------------#
#                                                                            #
# Matthew Reeves                                                             #
# This program determines the performance of scheduling algorithms           #
#                                                                            #
#----------------------------------------------------------------------------#

import re

# initialize lists
t_fcfs = []
a_fcfs = []
l_fcfs = []

t_sstf = []
a_sstf = []
l_sstf = []

t_scan = []
a_scan = []
l_scan = []

t_cscan = []
a_cscan = []
l_cscan = []

complete_fcfs = []
complete_sstf = []
complete_scan = []
complete_cscan = []

line = raw_input()

# read first line of input containing system data for simulation
matchObj = re.match( r'(\d+)\s(\d+)\s(\d+)\s(\d+)\s(\d+)\s(\d+)$', line, re.M|re.I)

if matchObj:

    nc = int(matchObj.group(1))
    nt = int(matchObj.group(2))
    ns = int(matchObj.group(3))
    s1 = int(matchObj.group(4))
    s2 = int(matchObj.group(5))
    d = int(matchObj.group(6))

line = raw_input()

# read number of disk io requests to process
matchObj = re.match( r'(\d+)$', line, re.M|re.I)

if matchObj:

    nr = int(matchObj.group(1))

for i in range(0, nr):

    line = raw_input()
    
    # read first line of input containing system data for simulation
    matchObj = re.match( r'(\d+)\s(\d+)\s(\d+)$', line, re.M|re.I)

    if matchObj:

        t = int(matchObj.group(1))
        a = int(matchObj.group(2))
        l = int(matchObj.group(3))

        # store request data separately for each simulation
        t_fcfs.append(t)
        a_fcfs.append(a)
        l_fcfs.append(l)

        t_sstf.append(t)
        a_sstf.append(a)
        l_sstf.append(l)

        t_scan.append(t)
        a_scan.append(a)
        l_scan.append(l)

        t_cscan.append(t)
        a_cscan.append(a)
        l_cscan.append(l)

# initialize completion time lists to allow direct assignment by index
for i in range(nr):
    complete_fcfs.append(0)
    complete_sstf.append(0)
    complete_scan.append(0)
    complete_cscan.append(0)
    

########################################
# loop to simulate the FCFS algorithm  #
########################################

processing = 0
time = 0
sector = 0
cylinder = 0
request = 0
start = 0
num_complete = 0

while True:

    # if not processing a request, check if next process is at submit time
    if processing==0:
        if t_fcfs[request]<=time:
            
            processing=1
            address = a_fcfs[request] # store start address for current request
            sectors_left = l_fcfs[request] # store number sectors to process

            # find the cylinder next request's address starts in
            i=1
            while i <= nc:
                if address < i*ns*nt:
                    break
                else:
                    i+=1

            next_cylinder=i-1

            # find the track next request's address starts in
            i=1
            while i <= nt:
                if address < next_cylinder*i*ns:
                    break
                else:
                    i+=1

            next_track=i-1

            next_sector = address/((next_cylinder+1)*(next_track+1))

            # find difference between current cylinder, and cylinder for address
            cyl_diff = abs(next_cylinder - cylinder)

            # determine the seek time to move to new cylinder
            if cyl_diff == 0:
                seek_time = 0
            elif cyl_diff <= d:
                seek_time = cyl_diff*s1
            else:
                seek_time = cyl_diff*s2

    # checks if request is being processed and head movement complete
    if processing==1 and seek_time == 0:
        cylinder = next_cylinder
        
        # checks if head at start address, if so begins processing
        if sector == next_sector:
            start = 1

        # decrements numbers of sectors left for request to process
        if start == 1:
            sectors_left -= 1

        # if all sectors processed, flag as complete, reset local variables
        if sectors_left < 0:
            complete_fcfs[request] = time
            request += 1
            processing = 0
            start = 0
            num_complete+=1

    # tracks seek time while moving heads if heads not already in position        
    elif processing==1 and seek_time > 0:
        seek_time -= 1

    # if all requests processed, break out of loop
    if num_complete == nr:
        break

    # increment time unit, and sector number under head
    time += 1
    sector += 1

    # if reached last sector, reset to sector 0
    if sector == ns:
        sector = 0

    
########################################
# loop to simulate the SSTF algorithm  #
########################################

processing = 0
time = 0
sector = 0
cylinder = 0
request = 0
start = 0
num_complete = 0

while True:

    # if not processing a request, check if next process is at submit time
    if processing==0:

        shortest_seek_request = 0
        address=a_sstf[0]

        # finds the cylinder first request's address starts in
        i=1
        while i <= nc:
            if address < i*ns*nt:
                break
            else:
                i+=1

        next_cylinder=i-1

        # find difference between current cylinder, and cylinder for address
        cyl_diff = abs(next_cylinder - cylinder)

        # determine the seek time to move to new cylinder
        if cyl_diff == 0:
            seek_time = 0
        elif cyl_diff <= d:
            seek_time = cyl_diff*s1
        else:
            seek_time = cyl_diff*s2

        shortest_seek_time = seek_time
        
        # loop to find the queued request with shortest seek time
        for x in range(nr):
            # find the cylinder next request's address starts in
            i=1
            while i <= nc:
                if address < i*ns*nt:
                    break
                else:
                    i+=1

            next_cylinder=i-1

            # find difference between current cylinder, and cylinder for address
            cyl_diff = abs(next_cylinder - cylinder)

            # determine the seek time to move to new cylinder
            if cyl_diff == 0:
                seek_time = 0
            elif cyl_diff <= d:
                seek_time = cyl_diff*s1
            else:
                seek_time = cyl_diff*s2

            if seek_time < shortest_seek_time:
                request = x
                shortest_seek_time = seek_time            
        
        if t_sstf[request]<=time:
            
            processing=1
            address = a_sstf[request] # store start address for current request
            sectors_left = l_sstf[request] # store number sectors to process

            # find the cylinder next request's address starts in
            i=1
            while i <= nc:
                if address < i*ns*nt:
                    break
                else:
                    i+=1

            next_cylinder=i-1

            # find the track next request's address starts in
            i=1
            while i <= nt:
                if address < next_cylinder*i*ns:
                    break
                else:
                    i+=1

            next_track=i-1

            next_sector = address/((next_cylinder+1)*(next_track+1))

            # find difference between current cylinder, and cylinder for address
            cyl_diff = abs(next_cylinder - cylinder)

            # determine the seek time to move to new cylinder
            if cyl_diff == 0:
                seek_time = 0
            elif cyl_diff <= d:
                seek_time = cyl_diff*s1
            else:
                seek_time = cyl_diff*s2

    # checks if request is being processed and head movement complete
    if processing==1 and seek_time == 0:
        cylinder = next_cylinder
        
        # checks if head at start address, if so begins processing
        if sector == next_sector:
            start = 1

        # decrements numbers of sectors left for request to process
        if start == 1:
            sectors_left -= 1

        # if all sectors processed, flag as complete, reset local variables
        if sectors_left < 0:
            complete_sstf[request] = time
            request += 1
            processing = 0
            start = 0
            num_complete+=1

    # tracks seek time while moving heads if heads not already in position        
    elif processing==1 and seek_time > 0:
        seek_time -= 1

    # if all requests processed, break out of loop
    if num_complete == nr:
        break

    # increment time unit, and sector number under head
    time += 1
    sector += 1

    # if reached last sector, reset to sector 0
    if sector == ns:
        sector = 0
    
########################################
# loop to simulate the SCAN algorithm  #
########################################

processing = 0
time = 0
sector = 0
cylinder = 0
request = 0
start = 0
num_complete = 0

while True:

    # if not processing a request, check if next process is at submit time
    if processing==0:
        if t_scan[request]<=time:
            
            processing=1
            address = a_scan[request] # store start address for current request
            sectors_left = l_scan[request] # store number sectors to process

            # find the cylinder next request's address starts in
            i=1
            while i <= nc:
                if address < i*ns*nt:
                    break
                else:
                    i+=1

            next_cylinder=i-1

            # find the track next request's address starts in
            i=1
            while i <= nt:
                if address < next_cylinder*i*ns:
                    break
                else:
                    i+=1

            next_track=i-1

            next_sector = address/((next_cylinder+1)*(next_track+1))

            # find difference between current cylinder, and cylinder for address
            cyl_diff = abs(next_cylinder - cylinder)

            # determine the seek time to move to new cylinder
            if cyl_diff == 0:
                seek_time = 0
            elif cyl_diff <= d:
                seek_time = cyl_diff*s1
            else:
                seek_time = cyl_diff*s2

    # checks if request is being processed and head movement complete
    if processing==1 and seek_time == 0:
        cylinder = next_cylinder
        
        # checks if head at start address, if so begins processing
        if sector == next_sector:
            start = 1

        # decrements numbers of sectors left for request to process
        if start == 1:
            sectors_left -= 1

        # if all sectors processed, flag as complete, reset local variables
        if sectors_left < 0:
            complete_scan[request] = time
            request += 1
            processing = 0
            start = 0
            num_complete+=1

    # tracks seek time while moving heads if heads not already in position        
    elif processing==1 and seek_time > 0:
        seek_time -= 1

    # if all requests processed, break out of loop
    if num_complete == nr:
        break

    # increment time unit, and sector number under head
    time += 1
    sector += 1

    # if reached last sector, reset to sector 0
    if sector == ns:
        sector = 0

########################################
# loop to simulate the CSCAN algorithm #
########################################

processing = 0
time = 0
sector = 0
cylinder = 0
request = 0
start = 0
num_complete = 0

while True:

    # if not processing a request, check if next process is at submit time
    if processing==0:
        if t_cscan[request]<=time:
            
            processing=1
            address = a_cscan[request] # store start address for current request
            sectors_left = l_cscan[request] # store number sectors to process

            # find the cylinder next request's address starts in
            i=1
            while i <= nc:
                if address < i*ns*nt:
                    break
                else:
                    i+=1

            next_cylinder=i-1

            # find the track next request's address starts in
            i=1
            while i <= nt:
                if address < next_cylinder*i*ns:
                    break
                else:
                    i+=1

            next_track=i-1

            next_sector = address/((next_cylinder+1)*(next_track+1))

            # find difference between current cylinder, and cylinder for address
            cyl_diff = abs(next_cylinder - cylinder)

            # determine the seek time to move to new cylinder
            if cyl_diff == 0:
                seek_time = 0
            elif cyl_diff <= d:
                seek_time = cyl_diff*s1
            else:
                seek_time = cyl_diff*s2

    # checks if request is being processed and head movement complete
    if processing==1 and seek_time == 0:
        cylinder = next_cylinder
        
        # checks if head at start address, if so begins processing
        if sector == next_sector:
            start = 1

        # decrements numbers of sectors left for request to process
        if start == 1:
            sectors_left -= 1

        # if all sectors processed, flag as complete, reset local variables
        if sectors_left < 0:
            complete_cscan[request] = time
            request += 1
            processing = 0
            start = 0
            num_complete+=1

    # tracks seek time while moving heads if heads not already in position        
    elif processing==1 and seek_time > 0:
        seek_time -= 1

    # if all requests processed, break out of loop
    if num_complete == nr:
        break

    # increment time unit, and sector number under head
    time += 1
    sector += 1

    # if reached last sector, reset to sector 0
    if sector == ns:
        sector = 0

########################################
# Output results of all 4 simulations  #
########################################

# output results from FCFS simulation
print "Results for FCFS algorithm"
print "=========================="

# determines completion time of last completed request
print "I/O operations completed at time", complete_fcfs[nr-1]

sum_time = 0

# add all request run times together to determine sum
for i in range(nr):
    sum_time += (complete_fcfs[i]-t_fcfs[i])

# calculates average run time
avg_time = float(sum_time)/nr

print "Average response time = %.2f" % avg_time
if nr > 1:

    # calculate standard deviation
    summation = 0

    for i in range(nr):
        summation += ((complete_fcfs[i]-t_fcfs[i])-avg_time)**2

    std_dev = (summation/float(nr-1))**(0.5)
    
    print "Standard deviation of response times = %.2f" % std_dev
else:
    print "Standard deviation cannot be calculated"
print ""

###########################################################################

# output results from SSTF simulation
print "Results for SSTF algorithm"
print "=========================="

# determines completion time of last completed request
print "I/O operations completed at time", complete_sstf[nr-1]

sum_time = 0

# add all request run times together to determine sum
for i in range(nr):
    sum_time += (complete_sstf[i]-t_sstf[i])

# calculates average run time
avg_time = float(sum_time)/nr

print "Average response time = %.2f" % avg_time
if nr > 1:

    # calculate standard deviation
    summation = 0

    for i in range(nr):
        summation += ((complete_sstf[i]-t_sstf[i])-avg_time)**2

    std_dev = (summation/float(nr-1))**(0.5)
    
    print "Standard deviation of response times = %.2f" % std_dev
else:
    print "Standard deviation cannot be calculated"
print ""

###########################################################################

# output results from SCAN simulation
print "Results for SCAN algorithm"
print "=========================="

# determines completion time of last completed request
print "I/O operations completed at time", complete_scan[nr-1]

sum_time = 0

# add all request run times together to determine sum
for i in range(nr):
    sum_time += (complete_scan[i]-t_scan[i])

# calculates average run time
avg_time = float(sum_time)/nr

print "Average response time = %.2f" % avg_time
if nr > 1:

    # calculate standard deviation
    summation = 0

    for i in range(nr):
        summation += ((complete_scan[i]-t_scan[i])-avg_time)**2

    std_dev = (summation/float(nr-1))**(0.5)
    
    print "Standard deviation of response times = %.2f" % std_dev
else:
    print "Standard deviation cannot be calculated"
print ""

###########################################################################

# output results from CSCAN simulation
print "Results for CSCAN algorithm"
print "=========================="

# determines completion time of last completed request
print "I/O operations completed at time", complete_cscan[nr-1]

sum_time = 0

# add all request run times together to determine sum
for i in range(nr):
    sum_time += (complete_cscan[i]-t_cscan[i])

# calculates average run time
avg_time = float(sum_time)/nr

print "Average response time = %.2f" % avg_time
if nr > 1:

    # calculate standard deviation
    summation = 0

    for i in range(nr):
        summation += ((complete_cscan[i]-t_cscan[i])-avg_time)**2

    std_dev = (summation/float(nr-1))**(0.5)
    
    print "Standard deviation of response times = %.2f" % std_dev
else:
    print "Standard deviation cannot be calculated"
print ""