#include <bits/stdc++.h>
#define REP(i, n) for(int i = 0; i < n; i++)
#define BCK(i, n) for(int i = n-1; i >= 0; i--)
#define FWD(i, a, b) for(int i = a; i < b; i++)
#define ALL(c) (c).begin(), (c).end()
#define SIZE(c) ((int)(c).size())
#define pb push_back
#define st first
#define nd second
#define vi vector<int>
#define pi pair<int, int>
#define pll pair<long long, long long>
#define vpi vector<pi>
#define vpll vector<pll>
#define mp(a, b) make_pair(a,b)
using namespace std;
typedef long long LL;
typedef double ld;
int r,c;
struct Ride
{
int a,b,x,y,s,f;
int idx;
};
istream& operator>>(istream& is, Ride& r)
{
return is>>r.a>>r.b>>r.x>>r.y>>r.s>>r.f;
}
struct Car
{
int x = 0; int y = 0;
int stoptime = 0;
vector<int> rides;
int arriveTime(const Ride& r) const{
return max(stoptime + abs(x - r.a) + abs(y - r.b), r.s);
}
int finishTime(const Ride& r) const{
int arr = arriveTime(r);
return arr + abs(r.a-r.x) + abs(r.b-r.y);
}
void serveRide(const Ride& r){
x = r.x;
y = r.y;
stoptime = finishTime(r);
rides.pb(r.idx);
}
};
int dist(int a, int b, int x, int y){
return abs(a-x) + abs(b-y);
}
int score(const vector<Car>& cars, const vector<Ride>& rides, int b){
int ret=0;
for(auto const& car : cars){
int x=0, y=0, t=0;
for(auto i : car.rides){
const Ride& r = rides[i];
t += dist(x,y,r.a,r.b);
t = max(t, r.s);
if(t == r.s) ret += b;
ret += dist(r.a, r.b, r.x, r.y);
t += dist(r.a, r.b, r.x, r.y);
x = r.x;
y = r.y;
}
}
return ret;
}
vector<Car> firstSolution(vector<Car> cars, vector<Ride> rides){
sort(ALL(rides), [](const Ride& a, const Ride& b)
{return a.s < b.s;});
if(cars.empty()) return cars;
for(const auto& ride : rides){
auto& best = *min_element(ALL(cars), [&ride](const Car& a, const Car& b)
{return a.arriveTime(ride) < b.arriveTime(ride);});
if(best.finishTime(ride) >= ride.f) {
//cerr << "Ride " << ride.idx << " not served\n";
continue;
}
//if(best.arriveTime(ride) == ride.s)
// cerr << "Got bonus from ride " << ride.idx << '\n';
best.serveRide(ride);
}
return cars;
}
vector<Car> secondSolution(vector<Car> cars, vector<Ride> rides, float perc){
int size = cars.size() * perc;
if(cars.empty()) return cars;
//cerr << "size: " << size << " of " << cars.size() << '\n';
REP(i, size){
Car& car = cars[i];
while(1){
Ride* best = nullptr;
for(auto& ride : rides){
if(ride.s >= dist(ride.a, ride.b, car.x, car.y) + car.stoptime){
if(!best || best->s >= ride.s){
best = &ride;
}
}
}
if(!best)
break;
car.serveRide(*best);
*best = rides.back();
rides.pop_back();
}
}
FWD(i, size, SIZE(cars)){
Car& car = cars[i];
while(1){
Ride* best = nullptr;
for(auto& ride : rides){
if(ride.f > dist(ride.a, ride.b, car.x, car.y) + car.stoptime + dist(ride.a, ride.b, ride.x, ride.y)){
if(!best || dist(best->a, best->b, car.x, car.y) >= dist(ride.a, ride.b, car.x, car.y)){
best = &ride;
}
}
}
if(!best)
break;
car.serveRide(*best);
*best = rides.back();
rides.pop_back();
}
}
return cars;
}
vector<Car> thirdSolution(vector<Car> cars, vector<Ride> rides, float perc){
int size = cars.size() * perc;
if(cars.empty()) return cars;
//cerr << "size: " << size << " of " << cars.size() << '\n';
random_device rd;
mt19937 g(rd());
while(1){
bool chosen = 0;
shuffle(cars.begin(), cars.begin() + size, g);
REP(i, size){
Car& car = cars[i];
Ride* best = nullptr;
for(auto& ride : rides){
if(ride.s >= dist(ride.a, ride.b, car.x, car.y) + car.stoptime){
if(!best || best->s >= ride.s){
best = &ride;
}
}
}
if(best){
chosen = 1;
car.serveRide(*best);
*best = rides.back();
rides.pop_back();
}
}
if(!chosen) break;
}
while(1){
bool chosen = 0;
shuffle(cars.begin()+size, cars.end(), g);
FWD(i, size, SIZE(cars)){
Car& car = cars[i];
Ride* best = nullptr;
for(auto& ride : rides){
if(ride.f > dist(ride.a, ride.b, car.x, car.y) + car.stoptime + dist(ride.a, ride.b, ride.x, ride.y)){
if(!best || dist(best->a, best->b, car.x, car.y) >= dist(ride.a, ride.b, car.x, car.y)){
best = &ride;
}
}
}
if(best){
chosen = 1;
car.serveRide(*best);
*best = rides.back();
rides.pop_back();
}
}
if(!chosen) break;
}
return cars;
}
template <int div, typename func, typename... Args>
vector<Car> fourthSolution(vector<Car> cars, vector<Ride> rides, func f, Args&&... args){
vector<int> partX(div+1), partY(div+1);
partX[0] = partY[0] = 0;
FWD(i,1,div+1){
partX[i] = ((LL)r)*i/div;
partY[i] = ((LL)c)*i/div;
}
vector<Ride> rides_parts[div][div];
vector<Car> cars_parts[div][div];
for(const auto& ride : rides){
rides_parts[ride.a*div/r][ride.b*div/c].pb(ride);
}
int start=0;
REP(i,div) REP(j,div){
int part = rides_parts[i][j].size() * cars.size() / rides.size();
cars_parts[i][j].resize(part);
start += part;
}
cars.resize(cars.size() - start);
vector<Car> result;
REP(i,div) REP(j,div){
#define algo firstSolution
for(auto const& c : f(cars_parts[i][j], rides_parts[i][j], forward<Args>(args)...))
result.pb(c);
}
vector<bool> XD(rides.size());
for(auto const& c : result)
for(auto i : c.rides)
XD[i] = true;
vector<Ride> notdone;
REP(i,SIZE(XD))
if(!XD[i])
notdone.pb(rides[i]);
for(auto const& c : f(cars, notdone, forward<Args>(args)...))
result.pb(c);
#undef algo
return result;
}
int main(){
srand(time(NULL));
ios_base::sync_with_stdio(false);
int f,n,b,t;
cin>>r>>c>>f>>n>>b>>t;
vector<Ride> rides(n);
vector<Car> cars(f);
REP(i,n){
cin>>rides[i];
rides[i].idx = i;
}
vector<Car> best;
//const auto& sol1 = firstSolution(cars, rides);
best = firstSolution(cars, rides);
int bestscore = score(best, rides, b);
REP(i, 21){
float perc = 0.05f * i;
{
const auto& temp = secondSolution(cars, rides, perc);
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
{
const auto& temp = fourthSolution<2>(cars, rides, secondSolution, perc);
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
{
const auto& temp = fourthSolution<3>(cars, rides, secondSolution, perc);
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
}
REP(i, 21){
float perc = 0.05f * i;
{
const auto& temp = thirdSolution(cars, rides, perc);
cerr << "third solution " << i <<" " << score(temp, rides, b)<<endl;
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
{
const auto& temp = fourthSolution<2>(cars, rides, thirdSolution, perc);
cerr << "fourth solution " << i <<" " << score(temp, rides, b)<<endl;
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
{
const auto& temp = fourthSolution<3>(cars, rides, thirdSolution, perc);
cerr << "fourth solution " << i <<" " << score(temp, rides, b)<<endl;
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
}
{
const auto& temp = fourthSolution<2>(cars, rides, firstSolution);
cerr << "fourth solution " << score(temp, rides, b)<<endl;
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
{
const auto& temp = fourthSolution<3>(cars, rides, firstSolution);
cerr << "fourth solution " << score(temp, rides, b)<<endl;
int tempscore = score(temp, rides, b);
if(tempscore > bestscore){
bestscore = tempscore;
best = temp;
}
}
//const auto& sol2 = secondSolution(cars, rides, 0.95f);
cerr << "best score: " << score(best, rides, b) << endl;
for(const auto& car : best){
cout << car.rides.size() << ' ';
for(int i : car.rides)
cout << i << ' ';
cout << '\n';
}
return 0;
}
