#include <iostream>
#include <cassert>
#include <map>
#include <sstream>
#include <algorithm>
#include <cstring>
#include <set>
#include <fstream>
#include <cmath>
#include <queue>
#include <cstdlib>

using namespace std;

int gx, gy; // goal x, goal y

// 50.0 on kävelynopeus, koska yksi yksikkö on 100m
const double WALK_SPEED = 50.0;
double max_speed = WALK_SPEED; // jossei nopeampia tule

const int MAXX = 100;
const int MAXY = 100;

struct sit;
struct transit;

sit* ptrs[MAXX+1][MAXY+1] = {}; // 100, 100 on sallittu, joten siksi "yhtä isompi"

int md(int x1, int y1, int x2, int y2);
double ed(int x1, int y1, int x2, int y2);
double normalize_time(double time);

typedef vector<transit> mtype;
mtype TR[MAXX+1][MAXY+1];

struct sit {
    int x, y;
    double time_spent;
    sit* prev;
    char prevtran;

    double cmp() const {
        return time_spent + ed(x,y,gx,gy)/max_speed;
    }
};

struct transit {
    char type; // matkanteon tyyppi, '0' on kävely
    int dx, dy; // destination x, destination y
    double time; // kauanko tällä matkustusvälineellä menee aikaa
    vector<double> times; // milloin tämä matkustusväline lähtee (tunteja tasatunnin jälkeen)
};

int md(int x1, int y1, int x2, int y2) { // Manhattan distance
    return abs(x1-x2) + abs(y1-y2);
}

double ed(int x1, int y1, int x2, int y2) { // Euclidean distance
    double xd = x1-x2, yd = y1-y2;
    return sqrt(xd*xd+yd*yd);
}

// siirtymävektorit kaikkiin neljään pääilmansuuntaan
int dx[4] = {1,-1,0,0};
int dy[4] = {0,0,1,-1};

// onko ehdotettu paikka enää kartalla?
bool in_range(sit* s) {
    return s->x >= 0 && s->y >= 0 && s->x <= MAXX && s->y <= MAXY;
}

// vertailuluokka, jolla järjestetään tilanteet setissä
struct cmp {
    bool operator ()(sit* s1, sit* s2) {
        if(s1->cmp() == s2->cmp()) {
            if(s1->x == s2->x) return s1->y < s2->y;
            return s1->x < s2->x;
        }
        return s1->cmp() < s2->cmp();
    }
};


// lisäysfunktio; katsotaan onko tähän paikkaan päästy jo nopeammin
// jos ei -> lisätään uusi arvo ja pistetään pointteri muistiin
// muistista voidaan löytää nopeasti onko tähän ruutuun löydetty jo
// joku reitti ja paljonko aikaa oli kulutettu tuolloin

bool add(multiset<sit*,cmp>& pq, sit* ns) {
    if(ptrs[ns->x][ns->y] == 0) {
        ptrs[ns->x][ns->y] = ns;
        pq.insert(ns);
        return true;
    } else {
        if(ptrs[ns->x][ns->y]->cmp() > ns->cmp()) {
            sit* old = ptrs[ns->x][ns->y];
            ptrs[ns->x][ns->y] = ns;
            pq.erase(old);
            pq.insert(ns);
            return true;
        }
    }
    return false;
}

// kuinka kauan liikennevälinettä pitää odottaa?
double time_to_wait(double cur, double leaving_time) {
    cur = normalize_time(cur);
    leaving_time = normalize_time(leaving_time);
    // epsilontarkastus, jos lähtöajan ja nykyisen ajan erotus
    // on tarpeeksi pieni, on kyseessä sama aika -> ei myöhästytä
    // jatkoyhteydestä
    if(abs(leaving_time - cur) < 0.00001) return 0;
    if(leaving_time < cur) leaving_time++;
    double ret = leaving_time - cur;
    return ret;
}

void astar(multiset<sit*,cmp>& pq) {
    // prioriteettijonon ensimmäinen alkio
    sit* cur = *pq.begin();
    bool ok = false;
    while(!pq.empty()) {
        cur = *pq.begin(); pq.erase(cur);
        // ollaanko jo maalissa
        if(cur->x == gx && cur->y == gy) {
            ok = true;
            break;
        }

        // kävellään kaikkiin pääilmansuuntiin
        for(int i = 0; i < 4; ++i) {
            sit* ns = new sit;
            ns->x = cur->x + dx[i];
            ns->y = cur->y + dy[i];
            ns->time_spent = cur->time_spent + 1.0/WALK_SPEED;
            ns->prev = cur;
            ns->prevtran = '0';
            if(in_range(ns)) {
                if(!add(pq,ns)) delete ns;
            } else delete ns;
        }

        // sitten käydään läpi kaikki kulkuvälineet, jotka pysähtyvät tällä
        // pysäkillä, ja hypätään niiden kaikkien kyytiin ja työnnetään
        // mukaan prioriteettijonoon

        for(int i = 0; i < (int)TR[cur->x][cur->y].size(); ++i) {
            double min_wait = 1e9;
            for(int j = 0; j < (int)TR[cur->x][cur->y][i].times.size(); ++j) {
                min_wait = min(min_wait,time_to_wait(cur->time_spent,
                            TR[cur->x][cur->y][i].times[j]));
            }
            sit* ns = new sit;
            ns->x = TR[cur->x][cur->y][i].dx;
            ns->y = TR[cur->x][cur->y][i].dy;
            ns->prev = cur;
            ns->prevtran = TR[cur->x][cur->y][i].type;

            ns->time_spent = cur->time_spent + TR[cur->x][cur->y][i].time
                + min_wait;
            if(!add(pq,ns)) delete ns;
        }
    }

    // tätä ei pitäisi tapahtua, mutta kertookin lähinnä jostain hölmöstä
    // virhetilanteesta jos tällainen ilmoitus tulee
    if(!ok) cout<<"Did not find a route :o"<<endl;

    cout<<"Time spent: "<<cur->time_spent<<" hours"<<endl;

    // ja sitten lopullinen reitti, "väärässä" järjestyksessä kylläkin
    while(cur != NULL) {
        cout<<cur->x<<" "<<cur->y<<" "<<cur->time_spent<<" "<<cur->prevtran<<endl;
        cur = cur->prev;
    }

}

// emme ole kiinnostuneita tunneista, kun haluamme tietää,
// milloin lähtee seuraava bussi/juna, johon ehdimme
double normalize_time(double time) {
    return time - floor(time);
}

int main(int argc, char** argv) {
    // argumentteina annetaan nykyiset x ja y, ja uudet x ja y,
    // joihin pyritään, eli siis muodossa x1 y1 x2 y2
    if(argc < 5) {
        cout<<"Liian vähän argumentteja"<<endl;
        return -1;
    }

    // käydään junat läpi, ja merkataan ylös kaikki pysäkit,
    // joilta junaan voi hypätä ja minne sieltä pääsee;
    // todella pitkä funktio täynnä mekaanista vääntöä,
    // tämä jos mikä me halutaan kyllä antaa opiskelijoille
    // valmiina, todella rasittava kirjoittaa

    for(int i = 'A'; i <= 'D'; ++i) {
        string filename = "";
        filename += i; filename += ".train";
        ifstream fin(filename.c_str());

        double speed;

        string str;
        getline(fin,str);
        istringstream s1(str);
        s1>>speed;

        speed *= 10;
        max_speed = max(speed,max_speed);
        getline(fin,str);
        istringstream ss(str);

        vector<double> T;

        int stime;
        while(ss>>stime) {
            T.push_back(stime);
            T.back() /= 60.0;
        }

        vector<pair<int,int> > S;

        int x, y;
        while(fin>>x>>y) {
            S.resize(S.size() + 1);
            S.back().first = x;
            S.back().second = y;
        }

        fin.close();

        double curtime = 0;

        for(int j = 0; j < (int)S.size() - 1; ++j) {
            transit tr;
            tr.type = i;
            tr.dx = S[j+1].first; tr.dy = S[j+1].second;
            tr.time = ed(S[j].first,S[j].second,tr.dx,tr.dy) / speed;
            for(int k = 0; k < (int)T.size(); ++k) {
                tr.times.push_back(normalize_time(T[k] + curtime));
            }
            TR[S[j].first][S[j].second].push_back(tr);
            curtime += tr.time;
        }

        for(int j = S.size() - 1; j >= 1; --j) {
            transit tr;
            tr.type = i;
            tr.dx = S[j-1].first; tr.dy = S[j-1].second;
            tr.time = ed(S[j].first,S[j].second,tr.dx,tr.dy) / speed;
            for(int k = 0; k < (int)T.size(); ++k) {
                tr.times.push_back(normalize_time(T[k] + curtime));
            }
            TR[S[j].first][S[j].second].push_back(tr);
            curtime += tr.time;
        }
    }

    // ja sama busseille, aika paljon rasittavampi kirjoittaa,
    // vaikka onkin suurimmaksi osaksi copy pastea

    for(char i = '1'; i <= '6'; ++i) {
        string busfile = "";
        busfile += i; busfile += ".bus";
        ifstream fin(busfile.c_str());

        double speed;

        string str;
        getline(fin,str);
        istringstream s1(str);
        s1>>speed;
        speed *= 10;

        max_speed = max(speed,max_speed);
        getline(fin,str);
        istringstream ss(str);

        vector<double> T;

        int stime;
        while(ss>>stime) {
            T.push_back(stime);
            T.back() /= 60.0;
        }

        vector<pair<int,int> > S;

        int x, y;
        while(fin>>x>>y) {
            S.resize(S.size() + 1);
            S.back().first = x;
            S.back().second = y;
        }

        fin.close();

        busfile = ""; busfile += i; busfile += ".broute";
        fin.open(busfile.c_str());

        vector<pair<int,int> > R;
        while(fin>>x>>y) {
            R.resize(R.size() + 1);
            R.back().first = x;
            R.back().second = y;
        }
        fin.close();


        vector<int> index_table(S.size());

        int cur_route = 0;
        for(int j = 0; j < (int)S.size(); ++j) {
            while(R[cur_route] != S[j]) {
                ++cur_route;
            }
            index_table[j] = cur_route;
        }

        double curtime = 0;

        for(int j = 0; j < (int)S.size() - 1; ++j) {
            transit tr;
            tr.type = i;
            tr.dx = S[j+1].first; tr.dy = S[j+1].second;
            tr.time = (index_table[j+1] - index_table[j]) / speed;
            for(int k = 0; k < (int)T.size(); ++k) {
                tr.times.push_back(normalize_time(T[k] + curtime));
            }
            TR[S[j].first][S[j].second].push_back(tr);
            curtime += tr.time;
        }

        for(int j = (int)S.size() - 1; j >= 1; --j) {
            transit tr;
            tr.type = i;
            tr.dx = S[j-1].first; tr.dy = S[j-1].second;
            tr.time = (index_table[j] - index_table[j-1]) / speed;
            for(int k = 0; k < (int)T.size(); ++k) {
                tr.times.push_back(normalize_time(T[k] + curtime));
            }
            TR[S[j].first][S[j].second].push_back(tr);
            curtime += tr.time;
        }
    }

    // luetaan input, current x ja y, goal x ja y

    int cx, cy;
    cx = atoi(argv[1]);
    cy = atoi(argv[2]);
    gx = atoi(argv[3]);
    gy = atoi(argv[4]);

    // nollataan pointteritaulukko
    memset(ptrs,0,(MAXX+1)*(MAXY+1));

    // pistetään ensimmäinen alkio prioriteettijonoon
    sit* s1 = new sit;
    s1->x = cx; s1->y = cy; s1->time_spent = 0;
    s1->prev = NULL;

    multiset<sit*,cmp> pq;
    add(pq,s1);

    // ja sitten ajetaan itse A* prioriteettijonolle
    astar(pq);

    return 0;
}