For given $n$ segments which are parallel to X-axis or Y-axis, find the number of intersections of them.

Constraints

* $1 \leq n \leq 100,000$
* $ -1,000,000,000 \leq x_1, y_1, x_2, y_2 \leq 1,000,000,000$
* Two parallel segments never overlap or touch.
* The number of intersections $\leq 1,000,000$

Input

In the first line, the number of segments $n$ is given. In the following $n$ lines, the $i$-th segment is given by coordinates of its end points in the following format:

$x_1 \; y_1 \; x_2 \; y_2$

The coordinates are given in integers.

Output

Print the number of intersections in a line.

Example

Input

6
2 2 2 5
1 3 5 3
4 1 4 4
5 2 7 2
6 1 6 3
6 5 6 7


Output

3
#include <iostream>
#include <fstream>
#include <string>
#include <iomanip>
#include <math.h>
#include <stdbool.h>
#include <algorithm>
#include <vector>
#include <map>
#include <set>
//#include <chrono>
using namespace std;

bool myComp(vector<int> a, vector<int> b) { 
    return ( a[0] < b[0] ) || ( a[0]==b[0] && a[1]<b[1] );
}

int main(){
    #if 0
    std::ifstream in("input.txt");
    std::cin.rdbuf(in.rdbuf());
    #endif

    int n;
    cin >> n;

    int xmin = pow(10,9);
    int xmax = - pow(10,9);

    vector<vector<int> > vviSegments;
    for (int i=0; i<n; i++){
        int x0, y0, x1, y1;
        cin >> x0 >> y0 >> x1 >> y1;
        if ( x0 > x1 ) swap(x0, x1);
        if ( y0 > y1 ) swap(y0, y1);

        if ( x0 < xmin ) xmin = x0;
        if ( xmax < x1 ) xmax = x1;

        vector<int> viSegment(4);
        viSegment[0] = y0;
        viSegment[1] = 0; //Left
        viSegment[2] = x0;
        viSegment[3] = x1;
        if (y0 == y1){
            vviSegments.push_back(viSegment);
        }
        else {
            viSegment[0] = y0;
            viSegment[1] = -1; //Bottom
            vviSegments.push_back(viSegment);
            viSegment[0] = y1;
            viSegment[1] = 1; //Top
            vviSegments.push_back(viSegment);
        }
    }

    // std::chrono::system_clock::time_point start,end;
    // start = std::chrono::system_clock::now();

    // sort
    sort(vviSegments.begin(), vviSegments.end(), *myComp);

    // divide
    int N = xmax - xmin + 1;
    int L = int( sqrt(N) );
    int M = int(N / L) + 1;

    //cout << N << " " << L << " " << M << endl;

    // step function
    map<int, int> LSM;
    map<int, set<int> > BST;

    // Number of Cross
    long int numCross = 0;

    for (int i=0; i < vviSegments.size(); ++i){
        vector<int> viSegment = vviSegments[i];
        int y = viSegment[0];
        int whichEdge = viSegment[1];
        int x0 = viSegment[2] - xmin;
        int x1 = viSegment[3] - xmin;

        if ( whichEdge == -1 ){
            int m = int(x0 / L);
            int b = x0 % L;
            LSM[m+1] += 1;
            BST[m].insert(b);
            //cout << "+" << x0 << " " << "m:" << m << " b:" << b << endl;
        }
        if ( whichEdge == 0 ){
            int m0 = int(x0 / L);
            int m1 = int(x1 / L);
            int b0 = x0 % L;
            int b1 = x1 % L;

            //cout << x0 << " " << x1 << " ";

            int step0 = distance( BST[m0].lower_bound(0), BST[m0].upper_bound(b0) );
            int step1 = distance( BST[m1].lower_bound(0), BST[m1].upper_bound(b1) );
            int extra = ( BST[m0].find(b0) != BST[m0].end() )? 1 : 0;
            numCross += step1 - step0 + extra;

            //cout << " : " << step0 << " " << step1 << " " << extra << ":";

            for(map<int,int>::iterator it = LSM.begin(); it != LSM.end(); ++it) {
                if(it->first > m1) break;
                if(it->first > m0) {
                    numCross += it->second;
                    //cout << " key:" << it->first << " value:" << it->second;
                }
            }
            //cout << " : " << numCross << endl;
        }
        if ( whichEdge == 1 ){
            int m = int(x0 / L);
            int b = x0 % L;
            LSM[m+1] -= 1;
            BST[m].erase(b);
            //cout << "-" << x0 << " " << "m:" << m << " b:" << b << endl;
        }
    }

    // end = std::chrono::system_clock::now();

    // auto elapsed = std::chrono::duration_cast< std::chrono::milliseconds >(end - start).count();
    // std::cout << elapsed <<"ms"<< std::endl;

    cout << numCross << endl;
    return 0;
}
