#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
struct Seg {
  int l, r, x;
};
bool cmpX(const Seg& a, const Seg& b) { return a.x < b.x; }
const int MN = 5001;
int N;
vec<Seg> hor, ver;
vi bit;
void reset() { bit.assign(MN * 2, 0); }
void add(int x, int v) {
  x += 5001;
  for (; x < MN * 2; x += x & -x) bit[x] += v;
}
int sum(int x, int sum = 0) {
  x += 5001;
  for (; x; x -= x & -x) sum += bit[x];
  return sum;
}
ll C2(int x) { return x * (x - 1) / 2; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  scan(N);
  for (__typeof(0) i = 0; i < N; i++) {
    int x1, y1, x2, y2;
    scan(x1, y1, x2, y2);
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    if (x1 == x2)
      ver.push_back({y1, y2, x1});
    else if (y1 == y2)
      hor.push_back({x1, x2, y1});
  }
  sort((ver).begin(), (ver).end(), cmpX);
  ll tot = 0;
  int sz = ((int)((ver).size()));
  for (__typeof(0) i = 0; i < sz; i++) {
    vi horInRange;
    for (__typeof(0) j = 0; j < ((int)((hor).size())); j++) {
      if (hor[j].l <= ver[i].x && ver[i].x <= hor[j].r) horInRange.push_back(j);
    }
    sort((horInRange).begin(), (horInRange).end(),
         [&](int x, int y) { return hor[x].r > hor[y].r; });
    reset();
    int ptr = 0;
    for (__typeof(sz - 1) j = sz - 1; j > i; j--) {
      while (ptr < ((int)((horInRange).size())) &&
             hor[horInRange[ptr]].r >= ver[j].x) {
        add(hor[horInRange[ptr]].x, 1);
        ptr++;
      }
      int ymin = max(ver[i].l, ver[j].l), ymax = min(ver[i].r, ver[j].r);
      if (ymin <= ymax) tot += C2(sum(ymax) - sum(ymin - 1));
    }
  }
  println(tot);
  return 0;
}

### Prompt

Construct a cpp code solution to the problem outlined:

There are n segments drawn on a plane; the i-th segment connects two points (x_{i, 1}, y_{i, 1}) and (x_{i, 2}, y_{i, 2}). Each segment is non-degenerate, and is either horizontal or vertical — formally, for every i ∈ [1, n] either x_{i, 1} = x_{i, 2} or y_{i, 1} = y_{i, 2} (but only one of these conditions holds). Only segments of different types may intersect: no pair of horizontal segments shares any common points, and no pair of vertical segments shares any common points.

We say that four segments having indices h_1, h_2, v_1 and v_2 such that h_1 < h_2 and v_1 < v_2 form a rectangle if the following conditions hold:

  * segments h_1 and h_2 are horizontal; 
  * segments v_1 and v_2 are vertical; 
  * segment h_1 intersects with segment v_1; 
  * segment h_2 intersects with segment v_1; 
  * segment h_1 intersects with segment v_2; 
  * segment h_2 intersects with segment v_2. 



Please calculate the number of ways to choose four segments so they form a rectangle. Note that the conditions h_1 < h_2 and v_1 < v_2 should hold.

Input

The first line contains one integer n (1 ≤ n ≤ 5000) — the number of segments.

Then n lines follow. The i-th line contains four integers x_{i, 1}, y_{i, 1}, x_{i, 2} and y_{i, 2} denoting the endpoints of the i-th segment. All coordinates of the endpoints are in the range [-5000, 5000].

It is guaranteed that each segment is non-degenerate and is either horizontal or vertical. Furthermore, if two segments share a common point, one of these segments is horizontal, and another one is vertical.

Output

Print one integer — the number of ways to choose four segments so they form a rectangle.

Examples

Input


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


Output


7


Input


5
1 5 1 0
0 1 5 1
5 4 0 4
4 2 4 0
4 3 4 5


Output


0

Note

The following pictures represent sample cases:

<image> <image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using vec = vector<T>;
template <typename K, typename V>
using umap = unordered_map<K, V>;
template <typename K>
using uset = unordered_set<K>;
using vi = vec<int>;
using vl = vec<ll>;
using vpi = vec<pii>;
using vpl = vec<pll>;
using int128 = __int128_t;
using uint128 = __uint128_t;
template <typename I>
string intStr(I x) {
  string ret;
  while (x > 0) {
    ret += (x % 10) + '0';
    x /= 10;
  }
  reverse(ret.begin(), ret.end());
  return ret;
}
template <typename T>
inline void maxa(T& st, T v) {
  st = max(st, v);
}
template <typename T>
inline void mina(T& st, T v) {
  st = min(st, v);
}
inline void setprec(ostream& out, int prec) {
  out << setprecision(prec) << fixed;
}
template <typename T>
ostream& operator<<(ostream& out, vector<T> iter) {
  out << "[";
  for (auto t : iter) {
    out << t << ", ";
  }
  out << "]";
  return out;
}
template <typename T>
string arrayStr(T* arr, int sz) {
  string ret = "[";
  for (int i = 0; i < sz; i++) {
    ret += to_string(arr[i]) + ", ";
  }
  return ret + "]";
}
template <typename T>
void printArray(T* arr, int sz) {
  for (int i = 0; i < sz; i++) {
    cout << arr[i] << " ";
  }
  cout << "\n";
}
inline void scan() {}
template <typename F, typename... R>
inline void scan(F& f, R&... r) {
  cin >> f;
  scan(r...);
}
template <typename F>
inline void println(F t) {
  cout << t << '\n';
}
template <typename F, typename... R>
inline void println(F f, R... r) {
  cout << f << " ";
  println(r...);
}
inline void print() {}
template <typename F, typename... R>
inline void print(F f, R... r) {
  cout << f;
  print(r...);
}
template <typename F>
inline string __generic_tostring(F f) {
  stringstream ss;
  ss << f;
  return ss.str();
}
template <typename F>
inline string __join_comma(F f) {
  return __generic_tostring(f);
}
template <typename F, typename... R>
string __join_comma(F f, R... r) {
  return __generic_tostring(f) + ", " + __join_comma(r...);
}
struct Seg {
  int l, r, x;
};
bool cmpX(const Seg& a, const Seg& b) { return a.x < b.x; }
const int MN = 5001;
int N;
vec<Seg> hor, ver;
vi bit;
void reset() { bit.assign(MN * 2, 0); }
void add(int x, int v) {
  x += 5001;
  for (; x < MN * 2; x += x & -x) bit[x] += v;
}
int sum(int x, int sum = 0) {
  x += 5001;
  for (; x; x -= x & -x) sum += bit[x];
  return sum;
}
ll C2(int x) { return x * (x - 1) / 2; }
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
  scan(N);
  for (__typeof(0) i = 0; i < N; i++) {
    int x1, y1, x2, y2;
    scan(x1, y1, x2, y2);
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    if (x1 == x2)
      ver.push_back({y1, y2, x1});
    else if (y1 == y2)
      hor.push_back({x1, x2, y1});
  }
  sort((ver).begin(), (ver).end(), cmpX);
  ll tot = 0;
  int sz = ((int)((ver).size()));
  for (__typeof(0) i = 0; i < sz; i++) {
    vi horInRange;
    for (__typeof(0) j = 0; j < ((int)((hor).size())); j++) {
      if (hor[j].l <= ver[i].x && ver[i].x <= hor[j].r) horInRange.push_back(j);
    }
    sort((horInRange).begin(), (horInRange).end(),
         [&](int x, int y) { return hor[x].r > hor[y].r; });
    reset();
    int ptr = 0;
    for (__typeof(sz - 1) j = sz - 1; j > i; j--) {
      while (ptr < ((int)((horInRange).size())) &&
             hor[horInRange[ptr]].r >= ver[j].x) {
        add(hor[horInRange[ptr]].x, 1);
        ptr++;
      }
      int ymin = max(ver[i].l, ver[j].l), ymax = min(ver[i].r, ver[j].r);
      if (ymin <= ymax) tot += C2(sum(ymax) - sum(ymin - 1));
    }
  }
  println(tot);
  return 0;
}

```