#include <iostream>
using namespace std;

#include <list>
#include <vector>
#include <cmath>

namespace grid {
    struct Graph {

        void SafeFree();

        void SetVertexCount(int count);

        int GetVertexCount() const {
            return m_vertexCount;
        }

        Graph();

        ~Graph() {
            SafeFree();
        }

        void SetWeight(short weight, int i, int j);

        short GetWeight(int i, int j) const;


        void TopologicalSortingVariantOne(std::vector<int> &out) const;

        void GetMaximumWeightedPath(std::vector<int> &out);

    private:
        int m_vertexCount;
        std::list<int> *edgelists;
        short **adj;
        short *in;
        short *out;
        int steps;
        bool invalid_edge_lists;

    };



    struct Point2D {
        Point2D ();
        Point2D (double x, double y);
        Point2D operator - (const Point2D &other) const;

        bool operator != (const Point2D &other) const {
            return fabs(other.x - x) > 1e-9 || fabs(other.y - y) > 1e-9;
        }

        double x, y;
    };

    struct Polygon {
        std::vector<Point2D> polyline;

        bool IsDisconnected() {
            return polyline[polyline.size() - 1] != polyline[0];
        }

        void SetSize(int size) {
            polyline.resize(size);
        }

        unsigned GetSize() const {
            return polyline.size();
        }

        void SetPoint(int index, const Point2D &point) {
            polyline[index] = point;
        }

        void PushPoint(Point2D &point) {
            polyline.push_back(point);
        }

        Point2D GetPoint(int index) const {
            return polyline[index];
        }
    };

    struct Line2D {
        Line2D (const Point2D &A, const Point2D &B);
        Point2D A, B;
    };


    struct Vector {
        int xdir;
        int ydir;

        int xSource, ySource;
    };

    typedef std::list<Vector> BoundVectorList;
    typedef BoundVectorList* BoundVectorListPtr;

    struct GridVectorField {
        int lines, columns;

        GridVectorField(int lines, int columns);

        GridVectorField () {
            grid = 0;
            Reset(0, 0);
        }

        void Reset(int lines, int columns) {
            Clear();
            this->lines = lines;
            this->columns = columns;
            grid = new BoundVectorListPtr[lines * columns];
            memset(grid, 0x0, lines * columns * sizeof(BoundVectorListPtr));
        }

        void ClearSparseLists() {
        }

        ~GridVectorField () {
            Clear();
        }

        void AddVector(int i, int j, Vector &vector);
        void ClearVector( int i, int j );

        BoundVectorListPtr GetVectorList(int i, int j) const;

        void Clear();


    private:
        std::list<BoundVectorListPtr> sparseLists;
        BoundVectorListPtr *grid;
    };


    class GridVectorization
    {
    public:


    private:
        double distance2(const Point2D &P,const  Line2D &line) const ;

        double length_squared(const Point2D &A,const  Point2D &B);

        double distance1(const Point2D &A,const  Point2D &B);

        double dot(const Point2D &A,const  Point2D &B);

        double minimum_distance(const Point2D &v,const  Point2D &w,const Point2D &p);

        double cross(const Point2D &  p1, const Point2D &  p2, const Point2D &  p3);

        void BuildGraph(Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance );

    public:
        GridVectorization(void);
        ~GridVectorization(void);

        void AproximatePolygon(Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly);

        void AproximatePolygonList(std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut);

        void VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut );

        void Fill(char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue);

    private:
        char GetCell(int i, int j, char *grid, int Lines, int Columns);

        void SetCell(int i, int j, char *grid, int Lines, int Columns, char cell);

        void DetectPolygon (char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly);

        void BuildCwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void BuildCcwVectorField(char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut);

        void FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        void FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut);

        bool IsReachable(char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY);


    };
}


#include <iostream>
using namespace std;
using namespace grid;

int main ()
{
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
#endif

    char *grid;
    grid::GridVectorization vectorization;
    int n, m;
    char c;

    scanf("%d%d", &m, &n);
    grid = new char[ n * m ];


    scanf("%c", &c);

    for (int i=0; i<n; ++i)
    {
        for (int j=0; j<m; ++j)
        {
            scanf("%c", &c);
            grid[ m * i + j ] = c - '0';

            //printf("%c", c);
        }
        scanf("%c", &c);
        //printf("\n");
    }


    std::list<Polygon *> poly, poly2;
    vectorization.VectorizeGrid(grid, n, m, 2000, 2000, poly);
    vectorization.AproximatePolygonList(poly, 2, 0.96, poly2);


    Polygon *p = poly2.front();

    switch(p->GetSize())
    {
    case 5:
        printf("square\n");
        break;
    case 4:
        printf("triangle\n");
        break;
    default:
        printf("circle\n");
    }
    return 0;
}

#include <cmath>



namespace grid {

    int dirX[] = {0, 1, 0, -1};
    int dirY[] = {-1, 0, 1, 0};

    char specialGridFlag = char(-1);

    int dirX2[] = {0, 1, 0, -1, 1, 1, -1, -1};
    int dirY2[] = {-1, 0, 1, 0, -1, 1, -1, 1};

    GridVectorization::GridVectorization(void)
    {
    }

    GridVectorization::~GridVectorization(void)
    {
    }

    double GridVectorization::distance2( const Point2D &P, const Line2D &line ) const
    {
        return abs( (line.B.x - line.A.x) * (line.A.y - P.y) - ( line.A.x - P.x ) * (line.B.y - line.A.y) ) /
            sqrt(double((line.B.x - line.A.x) * (line.B.x - line.A.x) + (line.B.y - line.A.y) * (line.B.y - line.A.y)));
    }

    double GridVectorization::length_squared( const Point2D &A, const Point2D &B )
    {
        return (A.x - B.x) * (A.x - B.x) + (A.y - B.y) * (A.y - B.y);
    }

    double GridVectorization::distance1( const Point2D &A, const Point2D &B )
    {
        return sqrt(length_squared(A, B));
    }

    double GridVectorization::dot( const Point2D &A, const Point2D &B )
    {
        return A.x * B.x + A.y * B.y;
    }

    double GridVectorization::minimum_distance( const Point2D &v, const Point2D &w, const Point2D &p )
    {
        // Return minimum distance between line segment v w and point p
        double l2 = length_squared(v, w);  // i.e. |w-v|^2 -  avoid a sqrt
        if (l2 == 0.0) return distance1(p, v);   // v == w case
        // Consider the line extending the segment, parameterized as v + t (w - v).
        // We find projection of point p onto the line.
        // It falls where t = [(p-v) . (w-v)] / |w-v|^2
        double t = dot(p - v, w - v) / l2;
        if (t < 0.0) return distance1(p, v);       // Beyond the 'v' end of the segment
        else if (t > 1.0) return distance1(p, w);  // Beyond the 'w' end of the segment
        Line2D const &ref = Line2D(w, v);
        return distance2(p, ref);
    }

    double GridVectorization::cross( const Point2D & p1, const Point2D & p2, const Point2D & p3 )
    {
        return (p2.x - p1.x) * (p3.y - p1.y) - (p2.y - p1.y) * (p3.x - p1.x);
    }

    void GridVectorization::BuildGraph( Polygon &inPoly, Graph &outGraph, double const innerTolerance, double const outerTolerance )
    {
        outGraph.SetVertexCount(inPoly.GetSize());

        if(!inPoly.GetSize())
            return;

        for(unsigned i=0; i < inPoly.GetSize() - 1; ++i)
            for(unsigned j=1; j < inPoly.GetSize(); ++j) {
                bool ok = true;
                for(unsigned k = i + 1; ok && k < j; ++k) {
                    double min_distance = minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k));
                    double cross_prod = cross(inPoly.GetPoint(j), inPoly.GetPoint(k), inPoly.GetPoint(i));

                    if(min_distance >= innerTolerance && cross_prod <= 0.0) {
                        //cout << "Inner: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                    if(min_distance >= outerTolerance && cross_prod > 0.0) {
                        //cout << "Outer: (" << i << ", " << j << ") - " << k << " distance: " << minimum_distance(inPoly.GetPoint(i), inPoly.GetPoint(j), inPoly.GetPoint(k)) << "\n";
                        ok = false;
                    }
                }
                if(ok) {
                    outGraph.SetWeight( j - i - 1, i, j );
                }
            }
    }

    void GridVectorization::AproximatePolygon( Polygon &inPoly, double const innerTolerance, double const outerTolerance, Polygon &outPoly )
    {
        Graph polylineGraph;
        BuildGraph(inPoly, polylineGraph, innerTolerance, outerTolerance);
        std::vector <int> optimized;
        polylineGraph.GetMaximumWeightedPath(optimized);

        outPoly.SetSize(optimized.size());

        int last = optimized.size() - 1;

        for(int i = last; i >= 0; --i) {
            outPoly.SetPoint(last - i, inPoly.GetPoint(optimized[i]));
        }
    }

    char GridVectorization::GetCell( int i, int j, char *grid, int Lines, int Columns )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                return grid[i * Columns + j];
        }
        return 0;
    }

    void GridVectorization::SetCell( int i, int j, char *grid, int Lines, int Columns, char cell )
    {
        if(    i < Lines && j < Columns &&
            i >= 0 && j >= 0 &&
            Lines >= 0 && Columns >= 0) {
                grid[i * Columns + j] = cell;
        }
        //no effect
    }

    void GridVectorization::VectorizeGrid( char *grid, int const Lines, int const Columns, int const aabbWidth, int const aabbHeight, std::list<Polygon *> &polylistOut )
    {
        //detect shapes
        GridVectorField field;

        BuildCwVectorField(grid, Lines, Columns, 1, field);

        int startX = -1, startY = -1;
        for(int i=0; i<Lines; ++i) {
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == 1) {

                    Fill(grid, i, j, aabbWidth, aabbHeight, Lines, Columns, 1, 2);

                    Polygon *newPoly = new Polygon();

                    DetectPolygon(grid, i, j, Lines, Columns, field, *newPoly);
                    //push the polygon
                    polylistOut.push_back(newPoly);

                    //erase the polygon
                    Fill(grid, i, j, Columns, Lines, Lines, Columns, 2, 0);
                }
            }
        }
    }

    void GridVectorization::AproximatePolygonList( std::list<Polygon *> &listIn, double const innerTolerance, double const outerTolerance, std::list<Polygon *> &listOut )
    {
        for(std::list<Polygon *>::iterator it = listIn.begin(); it != listIn.end(); ++it) {
            Polygon *poly = *it;
            if(poly != 0) {
                Polygon *out = new Polygon();
                AproximatePolygon(*poly, innerTolerance, outerTolerance, *out);
                listOut.push_back(out);
            }
        }
    }

    void GridVectorization::DetectPolygon( char *grid, int const i, int const j, int const Lines, int const Columns, GridVectorField &field, Polygon &outPoly )
    {
        ///////////////////calculating the contour of the shape (based on the vector field)////////////////////////////
        BoundVectorListPtr lst = field.GetVectorList(i, j);
        BoundVectorList::iterator it;

        Vector startPos;
        Vector currentPos;

        currentPos.xdir = startPos.xdir = i;
        currentPos.ydir = startPos.ydir = j;

        Vector lastDir;
        lastDir.xdir = -2;
        lastDir.ydir = -2;
        lastDir.xSource = i;
        lastDir.ySource = j;

        Vector currentDir;
        currentDir.xdir = -3;
        currentDir.ydir = -3;

        currentDir.xSource = i;
        currentDir.ySource = j;

        std::list<Point2D> polygon;

        bool error = false;

        int cellValue = GetCell(i, j, grid, Lines, Columns);

        do {

            int ii = (int)currentPos.xdir;
            int jj = (int)currentPos.ydir;

            BoundVectorListPtr lst = field.GetVectorList(ii, jj);
            BoundVectorList::iterator it;

            if(!lst || polygon.size() > (unsigned)((Lines + 1) * (Columns + 1) * 4)) {
                printf("What?\n");
                //fuck
                error = true;
            }

            //first getting the first vector on the contour

            for(it = lst->begin(); it != lst->end(); ++it) {

                if(!IsReachable(grid, Lines, Columns, currentDir.xSource, currentDir.ySource, it->xSource, it->ySource)) continue;

                if(it->xdir == 1 && it->ydir == 0 && GetCell(ii, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == -1 && GetCell(ii, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == -1 && it->ydir == 0 && GetCell(ii-1, jj-1, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }

                else if(it->xdir == 0 && it->ydir == 1 && GetCell(ii-1, jj, grid, Lines, Columns) != cellValue) {
                    currentDir = *it;
                    //the vector is an edge

                    break;
                }
            }

            //push a vertex only when the direction has changed
            if(lastDir.xdir != currentDir.xdir || lastDir.ydir != currentDir.ydir) {
                polygon.push_back(Point2D(currentPos.xdir, currentPos.ydir));
            }

            lastDir = currentDir;
            currentPos.xdir += currentDir.xdir;
            currentPos.ydir += currentDir.ydir;

        } while ( (startPos.xdir != currentPos.xdir || startPos.ydir != currentPos.ydir) && !error);

        if(error) {
            polygon.clear();
        }
        Polygon *newPoly = &outPoly;
        int k = 0;
        for(std::list<Point2D>::iterator it = polygon.begin(); it != polygon.end(); ++it) {
            newPoly->PushPoint(*it);
            ++k;
        }

        //add the last vertex to the polygon
        newPoly->PushPoint(*polygon.begin());
    }

    void GridVectorization::FillAndBuildVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        Vector vect;
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;
                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                bool isEdge = false;
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines) {
                        if(aj >= 0 && aj < Columns) {
                            if( grid[ ai * Columns + aj ] != searchValue && grid[ ai * Columns + aj ] != fillValue)
                                isEdge = true;
                        }
                        else
                            isEdge = true;
                    }
                    else
                        isEdge = true;
                }

                if(isEdge) {

                    vect.xSource = cX;
                    vect.ySource = cY;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(cX, cY, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(cX, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(cX + 1, cY + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(cX + 1, cY, vect);

                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                grid[ ai * Columns + aj ] = fillValue;
                                queue.push_back(std::pair<int, int>(ai, aj));
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::FillAndClearVectorField(char *grid, int const i, int const j, int const Lines, int const Columns, int searchValue, int fillValue, GridVectorField &fieldOut)
    {
        std::list<std::pair<int, int> > queue;
        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

                grid[ cX * Columns + cY ] = fillValue;
                ///////////////////////////////////////////////////////////

                fieldOut.ClearVector(cX, cY);
                fieldOut.ClearVector(cX, cY + 1);
                fieldOut.ClearVector(cX + 1, cY + 1);
                fieldOut.ClearVector(cX + 1, cY);

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(ai >= 0 && ai < Lines)
                        if(aj >= 0 && aj < Columns)
                            if( grid[ ai * Columns + aj ] == searchValue ) {
                                queue.push_back(std::pair<int, int>(ai, aj));
                                grid[ ai * Columns + aj ] = fillValue;
                            }
                }
                queue.pop_front();
            }
        }
    }

    void GridVectorization::Fill( char *grid, int const i, int const j, int const aabbWidth, int const aabbHeight, int const Lines, int const Columns, int searchValue, int fillValue )
    {
        std::list<std::pair<int, int> > queue;
        int minLines, maxLines;
        int minColumns, maxColumns;

        if(searchValue == specialGridFlag) {
            //reserved
            printf("Search value is reserved!\n");
            grid[ i * Columns + j ] = fillValue;
            return;
        }

        minLines = maxLines = i;
        minColumns = maxColumns = j;

        bool stopColumns = false, stopLines = false;

        if(i != -1 && j != -1) {
            queue.push_back(std::pair<int, int>(i, j));

            while(!queue.empty()) {
                int cX = queue.front().first;
                int cY = queue.front().second;

                ///////////////////////////////////////////////////////////

                if(!stopLines) {
                    if(cX < minLines)
                        minLines = cX;

                    if(cX > maxLines)
                        maxLines = cX;
                }

                if(!stopColumns) {

                    if(cY < minColumns)
                        minColumns = cY;

                    if(cY > maxColumns)
                        maxColumns = cY;
                }

                if(maxColumns - minColumns + 1 >= aabbWidth)
                    stopColumns = true;

                if(maxLines - minLines + 1 >= aabbHeight)
                    stopLines = true;

                grid[ cX * Columns + cY ] = fillValue;

                if(stopColumns || stopLines) {
                    if(cX < minLines || cX > maxLines)
                        grid[ cX * Columns + cY ] = searchValue;

                    if(cY < minColumns || cY > maxColumns)
                        grid[ cX * Columns + cY ] = searchValue;
                }

                ///////////////////////////////////////////////////////////
                for(int k = 0; k < 4; ++k) {
                    int ai = dirX[k] + cX;
                    int aj = dirY[k] + cY;

                    if(stopLines) {
                        if(ai >= minLines && ai <= maxLines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ] == searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if( grid[ ai * Columns + aj ] == searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                    else {
                        if(ai >= 0 && ai < Lines)
                            if(stopColumns) {
                                if(aj >= minColumns && aj <= maxColumns && grid[ ai * Columns + aj ]  ==  searchValue ) {
                                    queue.push_back(std::pair<int, int>(ai, aj));
                                    grid[ ai * Columns + aj ] = specialGridFlag;
                                }
                            }
                            else {
                                if(aj >= 0 && aj < Columns)
                                    if(grid[ ai * Columns + aj ]  ==  searchValue ) {
                                        queue.push_back(std::pair<int, int>(ai, aj));
                                        grid[ ai * Columns + aj ] = specialGridFlag;
                                    }
                            }
                    }
                }
                queue.pop_front();
            }
        }
    }

    bool GridVectorization::IsReachable( char *grid, int const Lines, int const Columns, int sourceX, int sourceY, int destX, int destY )
    {
        bool passable = false;

        if(sourceX < Lines && sourceX >= 0 && sourceY < Columns && sourceY >= 0)
            if(destX < Lines && destX >= 0 && destY < Columns && destY >= 0)
                passable = true;


        if(!passable) {
            return false;
        }

        char searchValue =  grid[ sourceX * Columns + sourceY ];
        char destValue = grid[ destX * Columns + destY ];


        if(destValue != searchValue) {
            return false;
        }

        else {

            bool validDir = false;

            // backslash orientation
            if( (destX == sourceX + 1 && destY == sourceY + 1) || (sourceX == destX + 1 && sourceY == destY + 1) ) {
                char upRight = grid[ sourceX * Columns + destY ];
                char downLeft = grid[ destX * Columns + sourceY ];

                if(upRight == searchValue || downLeft == searchValue)
                    validDir = true;
            }

            //slash orientation
            if ((destX == sourceX - 1 && destY == sourceY + 1) || (sourceX == destX - 1 && sourceY == destY + 1)) {

                char upLeft = grid[ destX * Columns + sourceY ];
                char downRight = grid[ sourceX * Columns + destY ];

                if(downRight == searchValue || upLeft == searchValue)
                    validDir = true;
            }

            if(sourceX == destX || sourceY == destY)
                validDir = true;

            if(sourceX == destX &&
                sourceY == destY)
                validDir = true;

            return validDir;
        }
    }

    void GridVectorization::BuildCwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        fieldOut.Reset(Lines + 1, Columns + 1);
        for(int i=0; i<Lines; ++i)
            for(int j=0; j<Columns; ++j) {
                if(grid[i * Columns + j] == searchValue) {

                    Vector vect;
                    vect.xSource = i;
                    vect.ySource = j;

                    vect.xdir = 0;
                    vect.ydir = 1;
                    fieldOut.AddVector(i, j, vect);

                    vect.xdir = 1;
                    vect.ydir = 0;
                    //safe to do because the vector field has its own validation methods
                    fieldOut.AddVector(i, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = 0;
                    vect.ydir = -1;
                    fieldOut.AddVector(i + 1, j + 1, vect);

                    //safe to do because the vector field has its own validation methods
                    vect.xdir = -1;
                    vect.ydir = 0;
                    fieldOut.AddVector(i + 1, j, vect);
                }
            }
    }

    void GridVectorization::BuildCcwVectorField( char *grid, int const Lines, int const Columns, int searchValue, GridVectorField &fieldOut )
    {
        //counter clockwise vector field
    }

    void Graph::SafeFree()
    {
        steps = 0;
        if(adj) {

            for(int i=0; i<GetVertexCount(); ++i)
                if(adj[i])
                    free(adj[i]);
            delete []adj;
            adj = 0;
        }

        if(edgelists) {
            invalid_edge_lists = false;
            delete []edgelists;
            edgelists = 0;
        }

        if(in) {
            delete []in;
            in = 0;
        }

        if(out) {
            delete []out;
            out = 0;
        }
    }

    void Graph::SetVertexCount( int count )
    {
        SafeFree();

        if(count <= 0) {
            m_vertexCount = 0;
            return;
        }

        adj = new short*[count];
        edgelists = new list<int>[count];
        in = new short[count];
        memset(in, 0x0, count * sizeof(short));
        out = new short[count];
        memset(out, 0x0, count * sizeof(short));


        for (int i=0; i<count; ++i) {
            adj[i] = (short *)malloc(count * sizeof(short));
            if(!adj[i]) {
                printf("Couldn't allocate memory for the graph!\n");
                exit(1);
                break;
            }
        }

        m_vertexCount = count;

        for(int i=0; i<m_vertexCount; ++i) {
            memset(adj[i], -1, m_vertexCount * sizeof(short));
        }
    }

    Graph::Graph()
    {
        adj = 0;
        in = 0;
        out = 0;
        edgelists = 0;
        steps = 0;
        SetVertexCount(0);
    }

    void Graph::SetWeight( short weight, int i, int j )
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return;
        }

        if(weight >= 0 && *(adj[i] + j) < 0) {
            in[j] ++;
            out[i] ++;
            edgelists[i].push_back(j);
            //add edge
        }
        else if(weight < 0 && *(adj[i] + j) >= 0) {
            in[j] --;
            out[i] --;
            //remove edge
        }
        *(adj[i] + j) = weight;
    }

    short Graph::GetWeight( int i, int j ) const
    {
        if(i >= m_vertexCount || j >= m_vertexCount || i < 0 || j < 0) {
            return -1;
        }
        return *(adj[i] + j);
    }

    void Graph::TopologicalSortingVariantOne( std::vector<int> &out ) const
    {
        //O(m + n) steps
        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;
        std::vector<int> removed;

        int n = g.GetVertexCount();
        int count = n;

        for(int i=0; i<n; ++i) {
            removed.push_back(0);
        }

        short *in = new short[n];

        memcpy(in, g.in, n * sizeof(short));

        int steps = 0;
        while(count) {
            for(int i=0; i<n; ++i)
                if(!removed[i] && !in[i]) {
                    for(list<int>::const_iterator it = g.edgelists[i].begin(); it != g.edgelists[i].end(); ++it) {
                        in[*it]--;
                        steps++;
                    }
                    count--;
                    out.push_back(i);
                    removed[i] = 1;
                }
        }
        delete []in;
    }

    void Graph::GetMaximumWeightedPath( std::vector<int> &out )
    {
        // O(m + n)

        if(GetVertexCount() == 0)
            return;

        Graph const &g = *this;

        std::vector<int> sorted;
        std::vector<int> costs, prev;
        int last = -1;

        for(int i=0; i<g.GetVertexCount(); ++i) {
            costs.push_back(-1);
            prev.push_back(-1);
        }


        g.TopologicalSortingVariantOne(sorted);
        costs[sorted[0]] = 0;

        for(unsigned i=0; i<sorted.size(); ++i) {
            int element = sorted[i];
            for(list<int>::const_iterator it = g.edgelists[element].begin(); it != g.edgelists[element].end(); ++it) {
                if(costs[*it] < g.GetWeight(element, *it) + costs[element]) {
                    costs[*it] = g.GetWeight(element, *it) + costs[element];
                    prev[*it] = element;
                    last = *it;
                    ++steps;
                }
            }
        }

        last = g.GetVertexCount() - 1;

        for(int i = last; i != -1; i = prev[i]) {
            out.push_back(i);
        }
    }

    Point2D::Point2D()
    {
        x = 0.0;
        y = 0.0;
    }

    Point2D::Point2D( double x, double y )
    {
        this->x = x;
        this->y = y;
    }

    Point2D Point2D::operator-( const Point2D &other ) const
    {
        Point2D result;
        result.x = x - other.x;
        result.y = y - other.y;
        return result;
    }

    Line2D::Line2D( const Point2D &A, const Point2D &B )
    {
        this->A = A;
        this->B = B;
    }

    GridVectorField::GridVectorField( int lines, int columns )
    {
        grid = 0;
        Reset(lines, columns);
    }

    void GridVectorField::AddVector( int i, int j, Vector &vector )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            if(!list) {
                list = new BoundVectorList();
                sparseLists.push_back(list);
                grid[i * columns + j] = list;
            }
            list->push_back(vector);
        }
    }

    BoundVectorListPtr GridVectorField::GetVectorList( int i, int j ) const
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            BoundVectorListPtr list = grid[i * columns + j];
            return list;
        }
        return 0;
    }

    void GridVectorField::Clear()
    {
        if(grid) {
            delete []grid;
            for(std::list<BoundVectorListPtr>::iterator it = sparseLists.begin(); it != sparseLists.end(); ++it) {
                delete (*it);
            }
            sparseLists.clear();
        }
    }

    void GridVectorField::ClearVector( int i, int j )
    {
        if(i < lines && j < columns && i >= 0 && j >= 0) {
            if(grid[i * columns + j])
                grid[i * columns + j]->clear();
        }
    }
}