p02304 Segment Intersections: Manhattan Geometry
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
```python
# Acceptance of input
import sys

file_input = sys.stdin

n = file_input.readline()

EP = []
l = -1000000001
u = 1000000001
vs_x = set()

for line in file_input:
    x1, y1, x2, y2 = (map(int, line.split()))
    if x1 == x2:
        if y1 < y2:
            EP.append((y1, l, x1))
            EP.append((y2, u, x1))
        else:
            EP.append((y1, u, x1))
            EP.append((y2, l, x1))
        vs_x.add(x1)
    else:
        if x1 < x2:
            EP.append((y1, x1, x2))
        else:
            EP.append((y1, x2, x1))

vs_x = sorted(vs_x)

# Segment Tree(Range Sum Query)
import math

m = 2 ** math.ceil(math.log(len(vs_x), 2))
ST = [0] * (2 * m - 1)

def switch(i):
    i += m - 1
    if ST[i]:
        d = -1
    else:
        d = 1
    ST[i] += d

    while i > 0:
        i = (i - 1) // 2
        ST[i] += d

def get_sum(s, t, k, l, r):
    if r < s or t < l:
        return 0
    elif s <= l and r <= t:
        return ST[k]
    else:
        mid = (l + r) // 2
        l_sum = get_sum(s, t, k * 2 + 1, l, mid)
        r_sum = get_sum(s, t, k * 2 + 2, mid + 1, r)
        return l_sum + r_sum

# Sweep
import bisect

EP.sort()
cnt = 0

for p in EP:
    e = p[1]
    if e == l or e == u:
        vs_i = bisect.bisect_left(vs_x, p[2])
        switch(vs_i)
    else:
        l_x = bisect.bisect_left(vs_x, e)
        r_x = bisect.bisect(vs_x, p[2]) - 1
        cnt += get_sum(l_x, r_x, 0, 0, m - 1)

# Output
print(cnt)
```