#include <bits/stdc++.h>
using namespace std;
const long double EPS = 1e-14;
const long long maxn = 10050;
const long long mod = 1e9 + 7;
bool in[maxn];
struct BIT {
 private:
  long long tree[maxn + 10];

 public:
  void add(long long x, long long v = 1) {
    for (x++; x < maxn; x += x & -x) tree[x] += v;
  }
  long long get(long long x) {
    long long ret = 0;
    for (x++; x; x -= x & -x) ret += tree[x];
    return ret;
  }
  long long range(long long l, long long r) {
    if (l > r) return 0;
    return get(r) - (l > 0 ? get(l - 1) : 0);
  }
} bit;
struct Segment {
  long long x1, y1, x2, y2;
} seg[maxn];
vector<long long> max_y[maxn], min_y[maxn];
inline bool cmp(const long long &a, const long long &b) {
  return seg[a].y2 > seg[b].y2;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<long long> hor;
  for (long long i = 0; i < n; ++i) {
    cin >> seg[i].x1 >> seg[i].y1 >> seg[i].x2 >> seg[i].y2;
    seg[i].x1 += 5000;
    seg[i].x2 += 5000;
    seg[i].y1 += 5000;
    seg[i].y2 += 5000;
    if (seg[i].y1 > seg[i].y2) {
      swap(seg[i].y1, seg[i].y2);
      swap(seg[i].x1, seg[i].x2);
    }
    if (seg[i].x1 == seg[i].x2) {
      max_y[seg[i].y2].push_back(i);
      min_y[seg[i].y1].push_back(i);
    } else {
      hor.push_back(i);
    }
  }
  long long ans = 0;
  sort((hor).begin(), (hor).end(), cmp);
  for (long long i = 0; i < (long long)(hor).size(); ++i) {
    for (long long j = 0; j < n; ++j)
      if (in[j]) {
        in[j] = false;
        bit.add(seg[j].x1, -1);
      }
    long long maxi = maxn - 1;
    while (maxi >= seg[hor[i]].y2) {
      for (auto x : max_y[maxi]) {
        assert(!in[x]);
        bit.add(seg[x].x1, 1);
        in[x] = true;
      }
      maxi--;
    }
    long long mini = maxn - 1;
    while (mini > seg[hor[i]].y2) {
      for (auto x : min_y[mini]) {
        assert(in[x]);
        bit.add(seg[x].x1, -1);
        in[x] = false;
      }
      mini--;
    }
    long long a = seg[hor[i]].x1, b = seg[hor[i]].x2;
    for (long long j = i + 1; j < (long long)(hor).size(); ++j) {
      if (seg[hor[j]].y2 == seg[hor[i]].y2) continue;
      while (mini > seg[hor[j]].y2) {
        for (auto x : min_y[mini])
          if (in[x]) {
            in[x] = false;
            bit.add(seg[x].x1, -1);
          }
        mini--;
      }
      long long c = seg[hor[j]].x1, d = seg[hor[j]].x2;
      if (a > b) swap(a, b);
      if (c > d) swap(c, d);
      long long x = bit.range(max(a, c), min(b, d));
      ans += x * (x - 1) / 2;
    }
  }
  cout << ans << '\n';
  return 0;
}

### Prompt

Generate a Cpp solution to the following problem:

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;
const long double EPS = 1e-14;
const long long maxn = 10050;
const long long mod = 1e9 + 7;
bool in[maxn];
struct BIT {
 private:
  long long tree[maxn + 10];

 public:
  void add(long long x, long long v = 1) {
    for (x++; x < maxn; x += x & -x) tree[x] += v;
  }
  long long get(long long x) {
    long long ret = 0;
    for (x++; x; x -= x & -x) ret += tree[x];
    return ret;
  }
  long long range(long long l, long long r) {
    if (l > r) return 0;
    return get(r) - (l > 0 ? get(l - 1) : 0);
  }
} bit;
struct Segment {
  long long x1, y1, x2, y2;
} seg[maxn];
vector<long long> max_y[maxn], min_y[maxn];
inline bool cmp(const long long &a, const long long &b) {
  return seg[a].y2 > seg[b].y2;
}
signed main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cout.tie(0);
  long long n;
  cin >> n;
  vector<long long> hor;
  for (long long i = 0; i < n; ++i) {
    cin >> seg[i].x1 >> seg[i].y1 >> seg[i].x2 >> seg[i].y2;
    seg[i].x1 += 5000;
    seg[i].x2 += 5000;
    seg[i].y1 += 5000;
    seg[i].y2 += 5000;
    if (seg[i].y1 > seg[i].y2) {
      swap(seg[i].y1, seg[i].y2);
      swap(seg[i].x1, seg[i].x2);
    }
    if (seg[i].x1 == seg[i].x2) {
      max_y[seg[i].y2].push_back(i);
      min_y[seg[i].y1].push_back(i);
    } else {
      hor.push_back(i);
    }
  }
  long long ans = 0;
  sort((hor).begin(), (hor).end(), cmp);
  for (long long i = 0; i < (long long)(hor).size(); ++i) {
    for (long long j = 0; j < n; ++j)
      if (in[j]) {
        in[j] = false;
        bit.add(seg[j].x1, -1);
      }
    long long maxi = maxn - 1;
    while (maxi >= seg[hor[i]].y2) {
      for (auto x : max_y[maxi]) {
        assert(!in[x]);
        bit.add(seg[x].x1, 1);
        in[x] = true;
      }
      maxi--;
    }
    long long mini = maxn - 1;
    while (mini > seg[hor[i]].y2) {
      for (auto x : min_y[mini]) {
        assert(in[x]);
        bit.add(seg[x].x1, -1);
        in[x] = false;
      }
      mini--;
    }
    long long a = seg[hor[i]].x1, b = seg[hor[i]].x2;
    for (long long j = i + 1; j < (long long)(hor).size(); ++j) {
      if (seg[hor[j]].y2 == seg[hor[i]].y2) continue;
      while (mini > seg[hor[j]].y2) {
        for (auto x : min_y[mini])
          if (in[x]) {
            in[x] = false;
            bit.add(seg[x].x1, -1);
          }
        mini--;
      }
      long long c = seg[hor[j]].x1, d = seg[hor[j]].x2;
      if (a > b) swap(a, b);
      if (c > d) swap(c, d);
      long long x = bit.range(max(a, c), min(b, d));
      ans += x * (x - 1) / 2;
    }
  }
  cout << ans << '\n';
  return 0;
}

```