#include <bits/stdc++.h>
using namespace std;
const int N = 1000001, M = 11111111;
long long MOD = 998244353, inv2 = (MOD + 1) / 2;
int INF = int(1e9);
long double eps = 1e-8;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
long double pi = acos(-1.0L);
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
struct heng {
  int x1, x2, y;
} a[N];
bool cmp1(heng a, heng b) { return a.y < b.y; }
struct shu {
  int y1, y2, x;
} b[N], c[N];
bool cmp2(shu a, shu b) { return a.y2 > b.y2; }
int t[N << 2], n, m;
void init() {
  int n1 = read();
  n = 0, m = 0;
  int x1, y1, x2, y2;
  for (int i = (int)1; i <= (int)n1; i++) {
    x1 = read(), y1 = read(), x2 = read(), y2 = read();
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    if (y1 == y2)
      a[++n].x1 = x1, a[n].x2 = x2, a[n].y = y1;
    else
      b[++m].y1 = y1, b[m].y2 = y2, b[m].x = x1;
  }
}
void build(int l, int r, int p) {
  t[p] = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
}
inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void update(int l, int r, int x, int y, int p) {
  if (l == r) {
    t[p] += y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(l, mid, x, y, p << 1);
  else
    update(mid + 1, r, x, y, p << 1 | 1);
  pushup(p);
}
int query(int l, int r, int x, int y, int p) {
  if (x <= l && r <= y) return t[p];
  int mid = (l + r) >> 1;
  int res = 0;
  if (x <= mid) res += query(l, mid, x, y, p << 1);
  if (y > mid) res += query(mid + 1, r, x, y, p << 1 | 1);
  return res;
}
void solve() {
  sort(a + 1, a + n + 1, cmp1);
  sort(b + 1, b + m + 1, cmp2);
  long long ans = 0;
  for (int i = (int)1; i <= (int)n; i++) {
    build(-5000, 5000, 1);
    int m1 = 0;
    for (int j = (int)1; j <= (int)m; j++)
      if (b[j].y1 <= a[i].y) c[++m1] = b[j], update(-5000, 5000, c[m1].x, 1, 1);
    int k = m1;
    for (int j = (int)i + 1; j <= (int)n; j++) {
      while (k && c[k].y2 < a[j].y) update(-5000, 5000, c[k].x, -1, 1), k--;
      int x = max(a[i].x1, a[j].x1), y = min(a[i].x2, a[j].x2);
      if (x > y) continue;
      int s = query(-5000, 5000, x, y, 1);
      ans += 1ll * s * (s - 1) / 2;
    }
  }
  printf("%I64d\n", ans);
}
int main() {
  init();
  solve();
  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;
const int N = 1000001, M = 11111111;
long long MOD = 998244353, inv2 = (MOD + 1) / 2;
int INF = int(1e9);
long double eps = 1e-8;
int dx[4] = {-1, 1, 0, 0};
int dy[4] = {0, 0, -1, 1};
long double pi = acos(-1.0L);
int read() {
  int v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
long long readll() {
  long long v = 0, f = 1;
  char c = getchar();
  while (c < 48 || 57 < c) {
    if (c == '-') f = -1;
    c = getchar();
  }
  while (48 <= c && c <= 57) v = (v << 3) + v + v + c - 48, c = getchar();
  return v * f;
}
struct heng {
  int x1, x2, y;
} a[N];
bool cmp1(heng a, heng b) { return a.y < b.y; }
struct shu {
  int y1, y2, x;
} b[N], c[N];
bool cmp2(shu a, shu b) { return a.y2 > b.y2; }
int t[N << 2], n, m;
void init() {
  int n1 = read();
  n = 0, m = 0;
  int x1, y1, x2, y2;
  for (int i = (int)1; i <= (int)n1; i++) {
    x1 = read(), y1 = read(), x2 = read(), y2 = read();
    if (x1 > x2) swap(x1, x2);
    if (y1 > y2) swap(y1, y2);
    if (y1 == y2)
      a[++n].x1 = x1, a[n].x2 = x2, a[n].y = y1;
    else
      b[++m].y1 = y1, b[m].y2 = y2, b[m].x = x1;
  }
}
void build(int l, int r, int p) {
  t[p] = 0;
  if (l == r) return;
  int mid = (l + r) >> 1;
  build(l, mid, p << 1);
  build(mid + 1, r, p << 1 | 1);
}
inline void pushup(int p) { t[p] = t[p << 1] + t[p << 1 | 1]; }
void update(int l, int r, int x, int y, int p) {
  if (l == r) {
    t[p] += y;
    return;
  }
  int mid = (l + r) >> 1;
  if (x <= mid)
    update(l, mid, x, y, p << 1);
  else
    update(mid + 1, r, x, y, p << 1 | 1);
  pushup(p);
}
int query(int l, int r, int x, int y, int p) {
  if (x <= l && r <= y) return t[p];
  int mid = (l + r) >> 1;
  int res = 0;
  if (x <= mid) res += query(l, mid, x, y, p << 1);
  if (y > mid) res += query(mid + 1, r, x, y, p << 1 | 1);
  return res;
}
void solve() {
  sort(a + 1, a + n + 1, cmp1);
  sort(b + 1, b + m + 1, cmp2);
  long long ans = 0;
  for (int i = (int)1; i <= (int)n; i++) {
    build(-5000, 5000, 1);
    int m1 = 0;
    for (int j = (int)1; j <= (int)m; j++)
      if (b[j].y1 <= a[i].y) c[++m1] = b[j], update(-5000, 5000, c[m1].x, 1, 1);
    int k = m1;
    for (int j = (int)i + 1; j <= (int)n; j++) {
      while (k && c[k].y2 < a[j].y) update(-5000, 5000, c[k].x, -1, 1), k--;
      int x = max(a[i].x1, a[j].x1), y = min(a[i].x2, a[j].x2);
      if (x > y) continue;
      int s = query(-5000, 5000, x, y, 1);
      ans += 1ll * s * (s - 1) / 2;
    }
  }
  printf("%I64d\n", ans);
}
int main() {
  init();
  solve();
  return 0;
}

```