import queue as Q
import time as t

R = C = F = N = B = T = None

last = 0


def tick(name):
    global last
    current = t.time()
    if last == 0:
        print("Starting count:", name, "Time now:", current)
    else:
        print(name, "Time now:", current, "Delta:", current - last)
    last = current


class Location(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y
        self.loc = self

    def __str__(self):
        return "(" + str(self.x) + "," + str(self.y) + ")"


class Trip(object):
    def __init__(self, id, a, b, x, y, s, f):
        self.id = id
        self.start = Location(a, b)
        self.end = Location(x, y)
        self.startTime = s
        self.finishTime = f
        self.distance = dist(self.start, self.end)


class Car(object):
    def __init__(self, id, loc):
        self.id = id
        self.loc = loc
        self.rides = []
        self.next_end_time = 0

    def __lt__(self, other):
        return self.next_end_time < other.next_end_time


def main():
    global Rows, Columns, Cars, Bonus, Steps
    tick("Starting")
    in_file = 'a.in'
    out_file = 'a.out'

    trips = []
    with open(in_file) as f:
        for i, line in enumerate(iter(f)):
            line = line.strip()
            if i == 0:
                r, c, f, n, b, t = list(map(int, line.split()))
                Rows = r
                Columns = c
                Cars = f
                Rides = n
                Bonus = b
                Steps = t
            else:
                cur_trip = Trip(i - 1, *list(map(int, line.split())))
                trips.append(cur_trip)

    tick("Loaded from file")
    cars = [Car(i, Location(0, 0)) for i in range(Cars)]
    tick("Created cars array")
    ### LOGIC GOES HERE ###
    trips = filter_impossible_trips(trips, cars, 0, by_endtime=True, by_bouns=False)
    tick("Filtered impossible trips")
    carsQueue = Q.PriorityQueue()
    for car in cars:
        carsQueue.put(car)

    currentTurn = 0
    finishTime = 1
    tick("Starting the fun")
    while currentTurn < Steps and not carsQueue.empty() and len(trips):
        car = carsQueue.get()
        currentTurn = car.next_end_time
        finishTime += 1
        if finishTime % 300 == 0:
            tick("Reached: " + str(finishTime))
        ride = best_trip_for_car(car, trips, currentTurn, Bonus)
        if ride:
            assign_ride_to_car(car, ride, currentTurn)
            trips.remove(ride)
            carsQueue.put(car)

    tick("Done")
    allocation = (cars[i].rides for i in range(Cars))
    tick("Really done")
    ### LOGIC ENDS HERE ###

    with open(out_file, 'w') as f:
        for route in allocation:
            f.write('{} '.format(len(route)))
            for ride in route:
                f.write('{} '.format(ride))
            f.write('\n')
    tick("Done writing to file")


def can_get_points(loc, trip, current_turn, bonus):
    d = dist(loc, trip.start)
    if d + trip.distance + current_turn > trip.finishTime:
        return 0
    if d + current_turn < trip.startTime:
        return bonus + trip.distance
    return trip.distance


def dist(loc1, loc2):
    return abs(loc1.loc.x - loc2.loc.x) + abs(loc1.loc.y - loc2.loc.y)


def best_end_time(car, trip, now_time):
    return max(trip.startTime, now_time + dist(car.loc, trip.start)) + trip.distance


def best_trip_for_car(car, trips, now_time, bonus):
    best_trip = trips[0]
    i = 0
    current_value = 280341289056
    for trip in trips:
        p = can_get_points(car, trip, now_time, bonus)
        if p != 0:
            time = best_end_time(car, trip, now_time)
            val = value(time, p, now_time)
            if val < current_value:
                current_value = val
                best_trip = trip
        i += 1
    if not can_get_points(car, best_trip, now_time, bonus):
        return None
    return best_trip


def value(time, score, now_time):
    return (time - now_time) - score


def assign_ride_to_car(car, trip, now_time):
    car.rides.append(trip.id)
    car.next_end_time = best_end_time(car, trip, now_time)
    car.loc = trip.end


def filter_impossible_trips(trips, cars, current_turn, by_endtime=True, by_bouns=False):
    filtered = []
    for trip in trips:
        d_from_vehicles = min(dist(trip.start, car.loc) for car in cars)
        if by_bouns and d_from_vehicles > (trip.startTime - current_turn):
            continue
        if by_endtime and (trip.distance + trip.startTime > trip.finishTime) or (
                d_from_vehicles + trip.distance + current_turn > trip.finishTime):
            continue
        filtered.append(trip)
    return filtered


if __name__ == '__main__':
    before = t.time()
    main()
    after = t.time()
    print("Total:", after - before)