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 <complex>
#include <vector>
#include <algorithm>
#include <functional>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

// セグメントツリーのライブラリ
template<typename T>
class SegmentTree {
public:
    // _n:必要サイズ, _def:初期値かつ単位元, _operation:クエリ関数,
    // _update:更新関数
    SegmentTree(size_t _n, T _def, std::function<T(T, T)> _operation,
        std::function<T(T, T)> _update)
        : def(_def), operation(_operation), update(_update) {
        n = 1;
        while (n < _n) {
            n *= 2;
        }
        node = std::vector<T>(2 * n - 1, def);
    }

    // 場所i(0-indexed)の値をxで更新
    void change(int i, T x) {
        i += n - 1;
        node[i] = update(node[i], x);
        while (i > 0) {
            i = (i - 1) / 2;
            node[i] = operation(node[i * 2 + 1], node[i * 2 + 2]);
        }
    }

    // [a, b)の区間クエリを実行
    T query(int a, int b) {
        return _query(a, b, 0, 0, n);
    }

    // 添字でアクセス
    T operator[](int i) {
        return node[i + n - 1];
    }

    int n;                       // 葉の数
    std::vector<T> node;              // データを格納するvector
private:
    T def;                       // 初期値かつ単位元
    std::function<T(T, T)> operation; // 区間クエリで使う処理
    std::function<T(T, T)> update;    // 点更新で使う処理

    // 区間[a,b)の総和。ノードk=[l,r)に着目している。
    T _query(int a, int b, int k, int l, int r) {
        if (r <= a || b <= l) return def; // 交差しない
        if (a <= l && r <= b)
            return node[k]; // a,l,r,bの順で完全に含まれる
        else {
            T c1 = _query(a, b, 2 * k + 1, l, (l + r) / 2); // 左の子
            T c2 = _query(a, b, 2 * k + 2, (l + r) / 2, r); // 右の子
            return operation(c1, c2);
        }
    }
};

int main() {

    int n;
    cin >> n;

    // x座標，イベント, y座標(min), y座標(max)
    vector<tuple<int, int, int, int>>  events;

    vector<int> vy;

    for (int i = 0; i < n; ++i) {
        int x1, y1, x2, y2;
        cin >> x1 >> y1 >> x2 >> y2;
        if (x1 == x2) { // 縦
            events.emplace_back(x1, 0, min(y1, y2), max(y1, y2));
            vy.emplace_back(y1);
            vy.emplace_back(y2);
        }
        else { // 横
            events.emplace_back(min(x1, x2), -1, y1, 0);
            events.emplace_back(max(x1, x2), 1, y1, 0);
            vy.emplace_back(y1);
        }
    }

    sort(events.begin(), events.end());

    // y座標の圧縮を行う
    sort(vy.begin(), vy.end());
    vy.erase(unique(vy.begin(), vy.end()), vy.end());

    map<int, int> mp;
    for (int i = 0, n = vy.size(); i < n; ++i) {
        mp[vy[i]] = i;
    }

    long long ans = 0LL;

    auto update = [](int a, int b) {return a + b; };
    auto operation = [](int a, int b) {return a + b; };
    SegmentTree<int> seg(n, 0, operation, update);

    //for (auto& [x, e, y1, y2] : events) {
    for (auto& event : events) {
        int e = get<1>(event);
        int y1 = get <2>(event);
        int y2 = get<3>(event);
        if (e == -1)seg.change(mp[y1], +1); // 追加
        else if (e == 1) seg.change(mp[y1], -1); // 削除
        else { // チェック
            ans += seg.query(mp[y1], mp[y2] + 1);
        }
    }

    cout << ans << endl;

}
