Harryxun/sft_time huggingface dataset:
### BUGGY CODE ###

def main():
    n = int(input())
    s = input()
    q = int(input())
    k = list(map(int, input().split()))
    for ki in k:
        D=M=DM=C=0
        for i, c in enumerate(s):
            if c == "D":
                D += 1
            elif c == "M":
                M += 1
                DM += D
            elif c == "C":
                C += DM
            if i >= ki-1:
                j = i-ki+1
                if s[j] == "D":
                    D -= 1
                    DM -= M
                elif s[j] == "M":
                    M -= 1
        print(C)

if __name__ == "__main__":
    main()

### FIXED CODE ###

# コピペ https://atcoder.jp/contests/dwacon5th-prelims/submissions/7670569
# 自分の https://atcoder.jp/contests/dwacon5th-prelims/submissions/7822126
# とほぼ変わらないのに自分のものはTLEするので検証
n=int(input())
s=input()
q=int(input())
for i in list(map(int,input().split())):
    a=0
    v=[0,0,0]
    for j in range(n):
        if s[j]=="D":
            v[0]+=1
        elif s[j]=="M":
            v[1]+=1
            v[2]+=v[0]
        if j>=i:
            if s[j-i]=="D":
                v[0]-=1
                v[2]-=v[1]
            elif s[j-i]=="M":
                v[1]-=1
        if s[j]=="C":
            a+=v[2]
    print(a)
### BUGGY CODE ###

'''
参考: https://beta.atcoder.jp/contests/agc026/submissions/2849460
'''

if __name__ == '__main__':
    n = int(input())
    s = input()

    s_left = s[:n]
    s_right = s[n:]
    m = dict()

    '''
    1 << n　は　2 ** n
    '''
    
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red += s_left[j]
            else:
                s_blue += s_left[j]
        if (s_red, s_blue) in m:
            m[(s_red, s_blue)] += 1
        else:
            m[(s_red, s_blue)] = 1

    ans = 0
    for i in range(2 ** n):
        s_red, s_blue = '', ''
        for j in range(n):
            if i & (2 ** j):
                s_red += s_right[j]
            else:
                s_blue += s_right[j]

        s_red = s_red[::-1]
        s_blue = s_blue[::-1]
        
        if (s_red, s_blue) in m:
            ans += m[(s_red, s_blue)]
    print(ans)

### FIXED CODE ###

def main():
    from collections import defaultdict

    N = int(input())
    S = input()

    L, R = S[:N], S[N * 2 - 1:N - 1:-1]

    def make_counter(s: str) -> defaultdict(int):
        ret = defaultdict(int)
        for bit in range(1 << N):
            red, blue = '', ''
            for j in range(N):
                if (bit >> j) & 1:
                    red += s[j]
                else:
                    blue += s[j]

            ret[red + '_' + blue] += 1
        return ret

    ld = make_counter(L)
    rd = make_counter(R)

    print(sum(ld[key] * rd[key] for key in ld))


if __name__ == '__main__':
    main()
### BUGGY CODE ###

l=int(input())
a=list(map(int,input().strip().split()))
q=int(input())
for i in range(q):
  m,n=map(int,input().strip().split())
  for i in range(len(a)):
    if a[i]==m:
        a[i]=n
  print(sum(a))
        


### FIXED CODE ###

t=int(input())
import math
a=list(map(int,input().strip().split()))
q=int(input())
h=[0]*(1000000+1)
sumi=0
for i in range(len(a)):
    h[a[i]]+=1
    sumi+=a[i]
 
for i in range(q):
    b,c=map(int,input().strip().split())
    #print(h)
    sumi+=h[b]*(c-b)
    h[c]+=h[b]
    h[b]=0
    #print(h)
    print(sumi)
        
        
        
    #a=list(map(int,input().strip().split()))
### BUGGY CODE ###

S = input()
T = input()
q = int(input())
for i in range(q):
	a,b,c,d = map(int, input().split())
	s = S[a-1:b]
	t = T[c-1:d]
	x = (s.count("A") + 2 * s.count("B")) % 3
	y = (t.count("A") + 2 * t.count("B")) % 3
	if x == y:
		print("YES")
	else:
		print("NO")

### FIXED CODE ###

S = input()
T = input()
q = int(input())

s = [0]
t = [0]
v = 0
for c in S:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	s.append(v)
v = 0
for c in T:
	v = (v + (ord(c) - ord("A") + 1)) % 3
	t.append(v)
for i in range(q):
	a,b,c,d = map(int, input().split())
	x = (3 + s[b] - s[a-1]) % 3
	y = (3 + t[d] - t[c-1]) % 3
	if x == y:
		print("YES")
	else:
		print("NO")
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    S = input().strip()
    Q = int(input())

    s = S
    for _ in range(Q):
        query = input().split()

        if query[0] == "1":
            s = s[::-1]
        elif query[0] == "2":
            F, C = query[1], query[2]
            if F == "1":
                s = C + s
            elif F == "2":
                s = s + C

    print(s)


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque
import sys
input = sys.stdin.readline

def main():
    S = list(input().strip())
    Q = int(input())

    d = deque(S)
    mode = True

    for _ in range(Q):
        query = input().split()

        if query[0] == "1":
            mode = not mode
        elif query[0] == "2":
            F, C = query[1], query[2]
            if F == "1":
                if mode:
                    d.appendleft(C)
                else:
                    d.append(C)
            elif F == "2":
                if mode:
                    d.append(C)
                else:
                    d.appendleft(C)

    s = list(d)
    if not mode:
        s = s[::-1]

    print(''.join(s))

if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = [int(input()) for i in range(n)]

for i in range(n):
  b = a[i]
  del a[i]
  print(max(a))
  a.insert(i, b)

### FIXED CODE ###

n = int(input())
a = [int(input()) for i in range(n)]
m_num = max(a)
m_index = [i for i, x in enumerate(a) if x == m_num]

if len(m_index) > 1:
  for i in range(n):
    print(m_num)
else:
  if len(a) == 1:
    print(a[0])
  else:
    m2_num = sorted(a)[-2]
    for i in range(n):
      if (i in m_index):
        print(m2_num)
      else:
        print(m_num)
### BUGGY CODE ###

N=int(input())
X=list(map(int,input().split()))

for i in range(N):
    t=X[i]
    X.pop(i)
    print(sorted(X)[(N-1)//2])
    X.insert(i,t)

### FIXED CODE ###

N=int(input())
X=list(map(int,input().split()))
X_s=sorted(X)
ans1=X_s[N//2]
ans2=X_s[N//2-1]
for i in X:
    print(ans1*(i<=ans2) or ans2)
### BUGGY CODE ###

import sys

p = 10 ** 9 + 7
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if n != len(set(a)) or m!= len(set(b)):
  print(0)
  sys.exit()
a.sort()
b.sort()
a.reverse()
b.reverse()

a = a + [0]
b = b + [0]
max_a = 0
max_b = 0
q = 1
for x in range(n*m, 0, -1):
  if a[max_a] >= x:
    max_a += 1
  if b[max_b] >= x:
    max_b += 1
  if x in a and x in b:
    q *= 1
  elif x in a:
    q = q * max_b % p
  elif x in b:
    q = q * max_a % p
  else:
    q = q * (max_a * max_b - (n * m - x)) % p
print(q)
    
    
    

### FIXED CODE ###

from bisect import bisect
import sys

p = 10 ** 9 + 7
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

if n != len(set(a)) or m!= len(set(b)):
  print(0)
  sys.exit()
A = set(a)
B = set(b)
a.sort()
b.sort()

q = 1
for x in range(n*m, 0, -1):
  if x in A and x in B:
    q *= 1
  elif x in A:
    q = q * max(m - bisect(b, x), 0)  % p
  elif x in B:
    q = q * max(n - bisect(a, x), 0) % p
  else:
    u = bisect(a, x)
    v = bisect(b, x)
    q = q * (max((n-u) * (m-v) - (n * m - x), 0) % p) % p
print(q)
### BUGGY CODE ###

# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# B リスト⇒辞書（その代わり累積和が遅くなる）

# 初期入力

import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))


l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B ={i:0 for i in range(N+1)}
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        cum_sum =[0]*N
        cum_sum[0] =B[0]
        for i in range(N-1):
            cum_sum[i+1] =cum_sum[i] +B[i+1]
        A =cum_sum
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
            ##
    
print(*A)


### FIXED CODE ###

# imos法
# 長さNの1次元配列において、「ある連続する区間に、ある数vを足す」という操作をK回繰り返した結果を高速で求める
# 
    
# 初期入力
    
import sys
input = sys.stdin.readline
N,K = (int(i) for i in input().split())
A = list(map(int, input().split()))
    
    
l =0
r =N
cumulative_sum =[0]*N
#操作数が電球の数より多いとき
if N <=K:
    A=[N]*N
# imos法
else:
    for j in range(K):
        B =[0]*(N+1)
        for i in range(N):
            index =A[i]
            if i-index <0:
                l=0
            else:
                l =i -index
            if i +index +1 >=N:
                r =N 
            else:
                r =i +index +1
            B[l] +=1 
            B[r] -=1
        #累積和(imos法) 
        from itertools import accumulate
        del B[-1]
        A =list(accumulate(B))
        if sum(A) ==N*N:
            print(*A)
            sys.exit(0)
    
print(*A)
### BUGGY CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import bisect
#負の数がa個、0がb-a個
a=bisect.bisect_left(A,0)
b=bisect.bisect_right(A,0)
Z=A[a:b]
H=A[:a]
S=A[b:]
#print(H,Z,S,A)
l=-10**19
r=10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  #正×正・負×負が該当
  if mid>0:
    for i in S:
      d=bisect.bisect_right(S,mid//i)
      cnt+=d
  if mid>0:
    for i in H:
      d=bisect.bisect_right(H,(-mid-1)//(-i))
      cnt+=len(H)-d
  for i in A:
    if i!=0 and i**2<=mid:
      cnt-=1
  cnt//=2
  #0が含まれる計算が該当
  if mid>=0:
    e=len(S)+len(H)
    d=N*(N-1)//2-e*(e-1)//2
    cnt+=d
  
  #正×負の計算
  for i in S:
    d=bisect.bisect_right(H,mid//i)
    cnt+=d
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)

### FIXED CODE ###

N,K=map(int, input().split())
A=list(map(int, input().split()))
A=sorted(A)
import numpy as np
A=np.array(A,dtype="int64")
Z=A[A==0]
H=A[A<0]
S=A[A>0]
l,r=-10**19,10**19
while r-l>1:
  mid=(r+l)//2
  cnt=0
  cnt+=A.searchsorted(mid//S,side="right").sum()
  cnt+=(N-A.searchsorted((-mid-1)//(-H),side="right")).sum()
  cnt-=np.count_nonzero(A*A<=mid)
  if mid>=0:
    cnt+=len(Z)*N 
  cnt//=2
  if cnt>=K:
    r=mid
  else:
    l=mid 
print(r)
### BUGGY CODE ###

import math

n,m = map(int,input().split())

a = list(map(int,input().split()))

for _ in range(m):
    maxv = a.index(max(a))
    a[maxv] = a[maxv]/2

a = list(map(math.floor,a))

print(sum(a))

### FIXED CODE ###

import math
import heapq

n,m = map(int,input().split())

a = list(map(int,input().split()))
a = list(map(lambda x:x*(-1),a))
heapq.heapify(a)

for _ in range(m):
    max = heapq.heappop(a)
    max = max/2
    heapq.heappush(a,max)

a = list(map(lambda x:x*(-1),a))
a = list(map(math.floor,a))

print(sum(a))
### BUGGY CODE ###

import datetime
import string
import re
import math

K=int(input())
if K % 2 == 0 or K % 5 == 0:
    print("-1")
else:
    s = 7
    count = 1
    while True:
        if s % K == 0:
            print(count)
            break
        else:
            count += 1
            s = 10*s + 7

### FIXED CODE ###

import datetime
import string
import re
import math

K=int(input())
if K % 2 == 0 or K % 5 == 0:
    print("-1")
else:
    s = 7
    count = 1
    while True:
        if s % K == 0:
            print(count)
            break
        else:
            count += 1
            s = (s % K)*10 + 7
### BUGGY CODE ###

N, C = map(int, input().split())
D = [tuple(map(int, input().split())) for _ in range(C)]
color = [tuple(map(int, input().split())) for _ in range(N)]

wrongness = [[0, 0, 0] for _ in range(C)]

for c in range(C):
    for i in range(N):
        for j in range(N):
            wrongness[c][(i + j) % 3] += D[color[i][j] - 1][c]

ans = 10**18

for c1 in range(C):
    for c2 in range(C):
        for c3 in range(C):
            if c1 == c2 or c2 == c3 or c3 == c1:
                continue
            ans = min(ans, wrongness[c1][0] + wrongness[c2][1] + wrongness[c3][2])

print(ans)

### FIXED CODE ###

n,c = map(int,input().split())
D = [list(map(int,input().split())) for _ in range(c)]
C = [list(map(int,input().split())) for _ in range(n)]

color_count = [[0]*c for i in range(3)]
for i in range(n):
    for j in range(n):
        color_count[(i+j)%3][C[i][j]-1] += 1

min_wrongness = 10**9

for i in range(c):
    for j in range(c):
        for k in range(c):
            if i!=j and j!=k and k!=i:
                wrongness = 0
                for l in range(3):
                    for m in range(c):
                        if l == 0:
                            wrongness += D[m][i]*color_count[l][m]
                        elif l == 1:
                            wrongness += D[m][j]*color_count[l][m]
                        else:
                            wrongness += D[m][k]*color_count[l][m]
                min_wrongness = min(min_wrongness,wrongness)
                
print(min_wrongness)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, A: "List[int]"):

    for k in range(K):
        B = [0] * N

        for i in range(N):
            l = max(0, i - A[i])
            r = i + A[i]

            B[l] += 1
            if r + 1 < N:
                B[r + 1] -= 1

        for i in range(1, N):
            B[i] += B[i - 1]

        A = B.copy()
        if sum(A) == N*K:
            break
    print(*A)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == "__main__":
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(N: int, K: int, A: "List[int]"):

    for k in range(K):
        B = [0] * N

        for i in range(N):
            l = max(0, i - A[i])
            r = i + A[i]

            B[l] += 1
            if r + 1 < N:
                B[r + 1] -= 1

        for i in range(1, N):
            B[i] += B[i - 1]

        A = B.copy()
        if sum(A) == N*N:
            break
    print(*A)

    return


# Generated by 1.1.7.1 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word

    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    K = int(next(tokens))  # type: int
    A = [int(next(tokens)) for _ in range(N)]  # type: "List[int]"
    solve(N, K, A)


if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque
n=int(input())
A=deque()
B=deque()
ans=0
for i in range(n):
    a,b=map(int,input().split())
    A.appendleft(a)
    B.appendleft(b)
for i in range(n):
    if A[i]%B[i]!=0:
        k=B[i]-(A[i]%B[i])
        ans+=k
        A=list(map(lambda x:x+k,A))
print(ans)

### FIXED CODE ###

from collections import deque
n=int(input())
A=deque()
B=deque()
ans=0
for i in range(n):
    a,b=map(int,input().split())
    A.appendleft(a)
    B.appendleft(b)
while A:
    A[0]+=ans
    if A[0]%B[0]!=0:
        k=B[0]-(A[0]%B[0])
        ans+=k
    A.popleft()
    B.popleft()

print(ans)
### BUGGY CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0
    for i in range(1000):
        iii = '{:03d}'.format(i)
        j = 0
        for k in range(n):
            if s[k] == iii[j]:
                j += 1
                if j == 3:
                    ret += 1
                    break

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))


### FIXED CODE ###

# coding: utf-8


def solve(*args: str) -> str:
    n = int(args[0])
    s = args[1]
    ret = 0

    index = [[] for _ in range(10)]
    for i in range(n):
        index[int(s[i])].append(i)

    for i in range(1000):
        iii = '{:03d}'.format(i)
        cur = -1
        found = False

        for e, j in enumerate(iii):
            found = False

            for k in index[int(j)]:
                if cur < k:
                    found = True
                    cur = k
                    break

            if not found:
                break

        if found:
            ret += 1

    return str(ret)


if __name__ == "__main__":
    print(solve(*(open(0).read().splitlines())))
### BUGGY CODE ###

import math 
A,B,n=map(int,input().split())
step = math.ceil(B/A)
ans=0
for i in range(1,n+1,step):
  tmp=math.floor(A*i/B)-(A*math.floor(i/B))
  if tmp>ans:
    ans=tmp
print(ans)


### FIXED CODE ###

import math
a,b,n=map(int,input().split())
c=min(b-1,n)
f=math.floor(a*c/b)
print(f)
### BUGGY CODE ###

x1 = input()
x2 = [1]*int(x1)

for k,v in enumerate(input().split(" ")):
    x2[k] = int(v)

result =  1
for xv in x2:
  result = xv * result

if 10**18 < result : result = -1
print(result) 


### FIXED CODE ###

x1 = input()
x2 = [int(i) for i in input().split(" ")]

result = 0
if 0 in x2:
  None 
else:
  result = 1
  for xv in x2:
     result = xv * result
  
     if 10**18 < result : 
        result = -1
        break


print(result)
### BUGGY CODE ###

n = int(input())
A = []
cnt = 0
append = A.append
for i in range(n):
    m = input()
    if m in A:
        pass
    else:
        append(m)
        cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
A = [input() for i in range(n)]
print(-len(A) + len(set(A)) + n)
### BUGGY CODE ###

n = int(input())
li = list(map(int,input().split()))
li.sort()
dp = [1]*n
done = [0]*n
done[0] = 1

for i in range(n):
    for j in range(i+1,n):
        if done[j] != 1:
            if li[j]==li[i]:
                done[i]=0
                done[j]=0
                dp[i]=0
                dp[j]=0
            elif li[j]%li[i]==0:
                done[j]=0
                dp[j]=0

print(sum(dp))

### FIXED CODE ###

n  = int(input())
li = list(map(int,input().split()))
ok = set()
ng = set()
mul = set()

ans = 0

for i in li:
    if i not in ok:
        ok.add(i)
    else:
        ng.add(i)

for i in ok:
    for j in range(2,10**6):
        if i*j > 10**6:
            break
        else:
            mul.add(i*j)

for i in ok:
    if i not in mul:
        if i not in ng:
            ans+=1

print(ans)
### BUGGY CODE ###

n = int(input())
A = [0]
A.extend(list(map(int,input().split())))
pair = 0

for i in range(1,n+1):
  for j in range(i+1,n+1):
    num = abs(i-j)
    if A[i]+A[j] == num:
      pair += 1
      
print(pair)

### FIXED CODE ###

n = int(input())
A = [0]
A.extend(list(map(int,input().split())))
B = {}
pair = 0

for i in range(1,n+1):
  if i+A[i] in B:
    B[i+A[i]] += 1
  else:
    B[i+A[i]] = 1
  
for j in range(2,n+1):
  if j-A[j] in B:
    pair += B[j-A[j]]

print(pair)
### BUGGY CODE ###

K,S = map(int,input().split())
ans = 0

for x in range(K+1):

    for y in range(x+1):

        for z in range(y+1):


            if x + y + z == S:

                #print(x,y,z)

                if x == y and y == z:

                    ans += 1

                elif x == y or y == z:

                    ans += 3

                else:

                    ans += 6

print (ans)

### FIXED CODE ###


K,S = map(int,input().split())

ans = 0

for x in range(K+1):

    for y in range(K+1):

        if x+y <= S and S - x - y <= K:

            ans += 1

print (ans)
### BUGGY CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
 
C = [card_set[1] for card_set in BC for j in range(card_set[0])]
A.extend(C)
 
A = sorted(A, reverse=True)
result = [A[i] for i in range(n)]
print(sum(result))

### FIXED CODE ###

import sys

input = sys.stdin.readline
n, m = map(int, input().split())
A = list(map(int, input().split()))
BC = [list(map(int, input().split())) for _ in range(m)]
BC.sort(key=lambda x: -x[1])

maxi = n*2
extend = A.extend
[extend([ls[1]] * ls[0]) for ls in BC if len(A) <= maxi]
A.sort(reverse=True)

print(sum(A[:n]))
### BUGGY CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        ans[i] = -1
    
que = deque()
que.append([root, path[root]])
while que:
    u, V = que.pop()
    for child in V:
        ans[child] = u
        que.append([child, path[child]])

for i in range(N):
    print(ans[i]+1)

### FIXED CODE ###

from collections import deque
N, M = map(int, input().split())
graph = [] 
for i in range(N + M - 1):
    a, b = map(int, input().split())
    graph += [[a,b]]

path = [[] for i in range(N)]  
parent = [[] for i in range(N)]
ans = [-1 for i in range(N)]
for p in graph:
    parent[p[1]-1] += [p[0]-1]
    path[p[0]-1] += [p[1]-1]

root = -1
for i in range(N):
    if parent[i] == []:
        root = i
        parent[i] = [-1]
visited = [0 for i in range(N)]
visited[root] = 1

que = deque()
for v in path[root]:
    ans[v] = root
    if len(parent[v]) > 1:
        parent[v].remove(root) 
    else: que.append([root, v])
while que:
    u, V = que.popleft()
    for v in path[V]:
        if len(parent[v]) > 1:
            parent[v].remove(V)
        else:
            que.append([V, v])
for i in range(N):
    print(parent[i][0]+1)
### BUGGY CODE ###

import bisect

n = int(input())
vx, vy = [], []
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((x1, y1, y2))
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vy.append((y1, x1, x2))
vy.sort()

ans = 0

for x, y1, y2 in vx:
    it1 = bisect.bisect(vy, (y1, float('-inf')))
    it2 = bisect.bisect(vy, (y2 + 1, float('-inf')))
    for y, x1, x2 in vy[it1:it2]:
        if x1 <= x <= x2:
            ans += 1

print(ans)

### FIXED CODE ###

import bisect


class BIT:
    def __init__(self, n):
        self.tree = [0] * (n + 1)
        self.n = n

    def add(self, i, v):
        while i <= self.n:
            self.tree[i] += v
            i += i & -i

    def _sum(self, i):
        ret = 0
        while i:
            ret += self.tree[i]
            i -= i & -i
        return ret

    def sum(self, l, h):
        return self._sum(h) - self._sum(l - 1)


n = int(input())
vx = []
xs = set()
for _ in range(n):
    x1, y1, x2, y2 = map(int, input().split())
    if x1 == x2:
        if y1 > y2:
            y1, y2 = y2, y1
        vx.append((y1, float('-inf'), x1))
        vx.append((y2, float('inf'), x1))
        xs.add(x1)
    else:
        if x1 > x2:
            x1, x2 = x2, x1
        vx.append((y1, x1, x2))
vx.sort()

bit = BIT(len(xs))
xs = [float('-inf')] + sorted(xs)
ix = {v: i for i, v in enumerate(xs)}
ans = 0

for y, j, x2 in vx:
    if j == float('-inf'):
        bit.add(ix[x2], 1)
    elif j == float('inf'):
        bit.add(ix[x2], -1)
    else:
        i1 = bisect.bisect_left(xs, j)
        i2 = bisect.bisect(xs, x2) - 1
        ans += bit.sum(i1, i2)

print(ans)
### BUGGY CODE ###

K=int(input())
def x():
    count=0
    for i in range(K):
        count+=(10**i)*7
        if count%K==0:
            return i+1
    return -1
x()
ans=x()
print(ans)

### FIXED CODE ###

K=int(input())
def x():
    count=0
    for i in range(K):
        count =(10*count+7)%K#余りからいく
        if count==0:
            return i+1
    return -1    
print(x())