#include <cstdio>
#include <algorithm>
#include <vector>



#define nmax 810
#define pb push_back
#define f first
#define s second
#define mp make_pair
using namespace std;

struct point {int x, y;};
vector <pair <point, point> > seg;
vector <pair <int, int> > BEG;
vector <pair <int, int> > D [nmax];
vector <pair <point, point> > PP [nmax];
point ins [nmax], P1 , P2 ;
int n, m, nrbenzi;
//Beg - cbin1, D - cbin2;
inline bool cmp (const point &a, const point &b) {
    return a.x == b.x ? (a.y < b.y) : (a.x < b.x);
}
inline int det (int x1, int x2, int y1, int y2, int a) {
    return ((y2 - y1) +y1 *( (a - x1) * (x2 - x1)) / ((a - x1) * (x2 - x1)));
}
double ceas_trig (point p0, point p1, point p2) {
    return ((p1.x - p0.x) * (p2.y - p0.y) - (p2.x - p0.x) * (p1.y - p0.y));
}
void preproc ()
{
    int i;
    int mijx, mijy;
    point bx1, bx2;
    // |
    BEG.pb (mp (0, seg [0].f.x));
    for (nrbenzi = 2; nrbenzi <= n; nrbenzi++)
    {
        // |extract* * * * coordx|
        bx1 = ins [nrbenzi - 1];
        bx2 = ins [nrbenzi];
        while (nrbenzi <= n && ins [nrbenzi].x == ins [nrbenzi + 1].x) ++nrbenzi;
        printf ("BX %d %d %d %d BX\n", bx1.x, bx1.y, bx2.x, bx2.y);
        for (i = 0; i < n; i++) {
            if (seg [i].f.x >= bx2.x || seg [i].s.x <= bx1.x) continue;// | |
            if (seg [i].f.x <= bx2.x && seg [i].s.x >= bx1.x) { // | - |

                if (seg [i].s.x < bx2.x) { // | -|
                    if (seg [i].f.x < bx1.x) {//-|- |
                        mijx = seg [i].s.x + bx1.x >> 1;
                                                mijy = det (seg [i].f.x, seg [i].f.y, seg [i].s.x, seg [i].s.y, bx1.x);
                        mijy >>= 1;
                        D [BEG.size () + 1].pb (mp (mijx, mijy));
                        PP [BEG.size () + 1].pb (mp (seg [i].f, seg [i].s));
                        //printf ("****%d %d***\n", seg [i].f.x, bx1.x);
                    } else { // |-|
                        mijx = seg [i].s.x + seg [i].f.x >> 1;
                        mijy = seg [i].s.y + seg [i].f.y >> 1;
                        D [BEG.size () + 1].pb (mp (mijx, mijy));
                        PP [BEG.size () + 1].pb (mp (seg [i].f, seg [i].s));
                    }
                }
                else if (seg [i].s.x > bx2.x) {
                    mijy = det (seg [i].f.x, seg [i].f.y, seg [i].s.x, seg [i].s.y, bx1.x);
                    mijx = bx2.x + seg [i].f.x >> 1;
                    mijy >>= 1;
                    D [BEG.size () + 1].pb (mp (mijx, mijy));//printf ("?!?@?@#?\n");
                    PP [BEG.size () + 1].pb (mp (seg [i].f, seg [i].s));
                }
            }
        }
        if (D [nrbenzi].size ()) {
            printf ("Mij beg*******************\n");
            for (i = 0; i < D [nrbenzi].size (); i++) printf ("%d %d, ", D [nrbenzi][i].f, D [nrbenzi][i].s);
            printf ("\nmij end***************************************\n");
        }
        BEG.pb (mp (bx1.x, bx2.x)); // aici cauti binar 1
    }
}
inline int bin1_search (int x, int y)
{
    int st, dr, mij;
    for (st = 1, dr = m, mij = st + dr >> 1; st <= dr; mij = st + dr >> 1) {
        if (BEG [mij].f <= x && BEG [mij].s >= x) return mij;
        else if (BEG [mij].f > x) dr = mij - 1;
        else if (BEG [mij].s < x) st = mij + 1;
    }
    return 1;
}
inline int funct (point P1, point P2, int x1, int y1)
{
    point P3;
    P3.x = x1; P3.y = y1;
    return ceas_trig (P1, P2, P3);
}
inline int bin2_search (int band, int x, int y)
{
    int sol, soll = 1, st, dr, mij;
    for (st = 0, dr = D [band].size (), mij = st + dr >> 1; st <= dr; mij = st + dr >> 1) {
        sol = funct (PP [band][mij].f, PP [band][mij].s, x, y);
        if (sol > 0) {
            soll = mij;
            dr = mij - 1;
        }
        else if (sol < 0) st = mij + 1;
    }
    return soll;
}
int main () {
    int i, a, b, band, nr = 0;
    freopen ("poligon.in", "r", stdin);
    freopen ("poligon.out", "w", stdout);

    scanf ("%d%d\n", &n, &m);
    scanf ("%d%d\n", &ins [1].x, &ins [1].y);

    //seg.pb (mp (P1, P2)); //seg.pb (mp (P1, P2));
    for (i = 2; i <= n; i++) {
        scanf ("%d%d\n", &ins [i].x, &ins [i].y);
        P1.x = ins [i - 1].x;
        P1.y = ins [i - 1].y;
        P2.x = ins [i].x;
        P2.y = ins [i].y;
        if (P1.x > P2.x) seg.pb (mp (P2, P1));
        else seg.pb (mp (P1, P2));
    }if (ins [n].x > ins [1].x) seg.pb (mp (ins [1], ins [n]));
    else seg.pb (mp (ins [n], ins [1]));
    for (i = 0; i < n; i++)
        printf ("%d %d %d %d\n", seg [i].f.x, seg [i].f.y, seg [i].s.x, seg [i].s.y);
    //sort (seg.begin (), seg.end (), cmp);
    sort (ins + 1, ins + n + 1, cmp);
    for (i = 1; i <= n; i++)
        printf ("%d %d\n", ins [i].x, ins [i].y);
    printf ("---------------------------------------\n");
    preproc ();
    printf ("********************************************************\n");
    m = BEG.size ();
    for (i = 0; i < BEG.size (); i++)
        for (int j = 0; j < PP [i].size (); j++)
            printf ("%d %d %d %d\n", PP [i][j].f.x,PP [i][j].f.y, PP [i][j].s.x, PP [i][j].s.y);
    /*while (m--) {
        scanf ("%d%d\n", &a, &b);
        band = bin1_search (a, b);
        i = bin2_search (band, a, b);
        if (i & 1) { printf ("ESTE\n");++nr;}
        else printf ("NU ESTE\n");
    }*/
    //for (i = 1; i <= nrbenzi; i++) printf ("%d %d\n", V [i].x, V [i].y);
    return 0;
}