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

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())

uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)

ans = 0

for group in uf.roots():
    ans = max(ans, len(uf.members(group)))

print(ans)

### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())


N, M = map(int, input().split())

uf = UnionFind(N)
for i in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    uf.union(a, b)

ans = 0

for i in range(N):
    ans = max(ans, uf.size(i))
    
print(ans)
### BUGGY CODE ###

from collections import deque
h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            q.append((i,j, 0))
            board[i][j] = "."

dx=[1,0,-1,0]
dy=[0,1,0,-1]

while q:
    i,j,cnt = q.popleft()
    if board[i][j] != ".":
        continue
    board[i][j] = cnt
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w:
            q.append((i+x, j+y, cnt+1))
ans = 0
for i in range(h):
    ans = max(ans, max(board[i]))
print(ans)


### FIXED CODE ###

from collections import deque
dx=[1,0,-1,0]
dy=[0,1,0,-1]

h, w = list(map(int, input().split()))
board = [list(input()) for i in range(h)]
q = deque()
for i in range(h):
    for j in range(w):
        if board[i][j] == "#":
            board[i][j] = True
            q.append((i, j, 0))
        else:
            board[i][j] = False

ans = 0
while q:
    i,j,cnt = q.popleft()
    for x, y in zip(dx,dy):
        if 0<=i+x<h and 0<=j+y<w and not board[i+x][j+y]:
            board[i+x][j+y] = True
            q.append((i+x, j+y, cnt+1))
            ans = max(ans, cnt+1)
print(ans)
### BUGGY CODE ###

from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = make_multi_list(0, [3, C])
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

print(ans)


### FIXED CODE ###

from copy import deepcopy
# 多次元配列を作成する
def make_multi_list(initial, degree):
    ans = [initial for _ in range(degree[-1])]
    for d in reversed(degree[:-1]):
        ans = [deepcopy(ans) for _ in range(d)]
    return ans


N, C = map(int, input().split())
INF = float("inf")
D = []
for i in range(C):
    D.append(list(map(int, input().split())))
c = []
for i in range(N):
    c.append([n - 1 for n in list(map(int, input().split()))])

# 前計算
cost = make_multi_list(0, [3, C])
for i in range(N):
    for j in range(N):
        for k in range(C):
            cost[(i + j) % 3][k] += D[c[i][j]][k]

ans = INF
for i in range(C):
    for j in range(C):
        if i == j:
            continue
        for k in range(C):
            if k in (i, j):
                continue
            ans = min(ans, cost[0][i] + cost[1][j] + cost[2][k])

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

N, K = map(int, input().split())
p = list(map(int, input().split()))
n = 0
I = 0
for i in range(N-(K-1)):
  if sum(p[i:i+K]) > n: 
    n = sum(p[i:i+K])
    I = i
ans = 0
for i in range(K):
  ans += (p[I+i]+1) / 2
print(ans)

### FIXED CODE ###

N, K = map(int, input().split())
p = list(map(int, input().split()))

a = 0
for i in range(N - K + 1):
  if i == 0:
    b = sum(p[0:K])
  else:
    b = b - p[i-1] + p[i + K - 1]
  
  if b > a:
    a = b
    f = i

ans = 0
for j in range(K):
  ans += (p[f + j] + 1) / 2

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

def primes(n):
	is_prime = [True] * (n+1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5)+1):
		if not is_prime[i]:
			continue
		for j in range(i*2, n+1, i):
			is_prime[j] = False
	return [i for i in range(n+1) if is_prime[i]]

Primes=primes(100000)
Q=int(input())
for i in range(Q):
    l,r=map(int,input().split())
    ans=0
    for j in range(l,r+1,2):
        if j in Primes and (j+1)//2 in Primes:
            ans+=1
    print(ans)

### FIXED CODE ###

def primes(n):
	is_prime = [True] * (n+1)
	is_prime[0] = False
	is_prime[1] = False
	for i in range(2, int(n**0.5)+1):
		if not is_prime[i]:
			continue
		for j in range(i*2, n+1, i):
			is_prime[j] = False
	return is_prime

is_Prime=primes(10**5)
count=[]
cnt=0
for i in range(10**5+1):
  if is_Prime[i] and is_Prime[(i+1)//2]:
    cnt+=1
  count.append(cnt)

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  print(count[r]-count[l-1])
### BUGGY CODE ###

# coding: utf-8
# 日本語を入力できるようにするために上記一文が必要


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


sum = 0
for i in range(N - 1 ):
        for j in range(i+1, N):
                sum = sum +  A_input[i] * A_input[j]

print(sum % (10**9 + 7) )

### FIXED CODE ###

# coding: utf-8
# 日本語を入力できるようにするために上記一文が必要


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

j_sum = 0
for j in range(N):
        j_sum = j_sum + A_input[j]


sum = 0
for i in range(N - 1 ):
        j_sum = j_sum - A_input[i]
        sum = sum +  A_input[i] * j_sum

print(sum % (10**9 + 7) )
### BUGGY CODE ###

from collections import Counter
import bisect


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    negA = []
    idx_negA = []
    for i, a in enumerate(A):
        negA.append(i - a)
        idx_negA.append(i)

    negA = sorted(negA)
    ans = 0
    for i in range(N):
        searched_idx = bisect.bisect_left(negA, i + A[i])

        if searched_idx == N:
            continue
        else:
            if idx_negA[searched_idx] > i:
                while negA[searched_idx] == i + A[i] and searched_idx <= N - 1:
                    ans += 1
                    if searched_idx == N - 1:
                        break
                    searched_idx += 1

    print(ans)


### FIXED CODE ###

from collections import Counter
import bisect


def make_divisors(n):
    divisors = []
    for i in range(1, int(n ** 0.5) + 1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n // i)

    # divisors.sort()
    return divisors


if __name__ == '__main__':
    N = int(input())
    A = list(map(int, input().split()))
    negA = []
    idx_negA = []
    for i, a in enumerate(A):
        negA.append(i - a)
        idx_negA.append(i)

    cnt_negA = Counter(negA)
    negA_keys = sorted(cnt_negA.keys())
    ans = 0
    for i in range(N):
        if i + A[i] in cnt_negA:
            ans += cnt_negA[i + A[i]]
    print(ans)
### BUGGY CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = int(input())

a = inpl()

t = 1

for i in a:
    t *= i

if t > 1000000000000000000:
    print(-1)
else:
    print(t)


### FIXED CODE ###

import sys
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = int(input())
a = inpl()
flag = 0
t = 1
for i in range(0, n):
    if a[i] == 0:
        flag = 1
        print(0)
        break

aaa = 0

if not flag:
    
    for i in range(0, n):
        t *= a[i]
        if t > 1000000000000000000:
            print(-1)
            aaa = 1
            break
    if not aaa:
        print(t)
### BUGGY CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    sys.setrecursionlimit(10**7)
    INF = 10**18
    MOD = 10**9 + 7
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    _LI = lambda : [int(x)-1 for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())
    SI = lambda : sys.stdin.readline().rstrip()

    N = NI()
    P = LI()

    s = [[0] * N for _ in range(N)]
    for i in range(N):
        for j in range(N):
            s[i][j] = min(i,N-1-i,j,N-1-j)

    r = [[1] * N for _ in range(N)]

    ans = 0
    for p in P:
        x = (p-1)//N
        y = (p-1) % N
        ans += s[x][y]
        r[x][y] = 0
        q = collections.deque()
        q.append((x,y,s[x][y]))
        while q:
            a,b,c = q.pop()
            nc = c + r[a][b]
            for da,db in ((1,0),(0,1),(-1,0),(0,-1)):
                na = a + da; nb = b + db
                if 0 <= na < N and 0 <= nb < N:
                    if s[na][nb] <= nc: continue
                    s[na][nb] = nc
                    q.append((na,nb,nc))
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys,queue,math,copy,itertools,bisect,collections,heapq

def main():
    LI = lambda : [int(x) for x in sys.stdin.readline().split()]
    NI = lambda : int(sys.stdin.readline())

    N = NI()
    P = LI()

    s = []
    for i in range(N):
        for j in range(N):
            s.append(min(i,N-1-i,j,N-1-j))

    r = [1] * (N*N)

    ans = 0
    q = []
    for p in P:
        p -= 1
        ans += s[p]
        r[p] = 0
        q.append(p)
        while q:
            a = q.pop()
            nc = s[a] + r[a]

            if a >= N:
                if s[a-N] > nc:
                    s[a-N] = nc
                    q.append(a-N)
            if a + N < N*N:
                if s[a+N] > nc:
                    s[a+N] = nc
                    q.append(a+N)
            if a % N:
                if s[a-1] > nc:
                    s[a-1] = nc
                    q.append(a-1)
            if a % N < N -1:
                if s[a+1] > nc:
                    s[a+1] = nc
                    q.append(a+1)

    print(ans)

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

import copy

n = int(input())
s = list(list(input()) for i in range(n))
count = 0

for i in range(n):
  for j in range(i + 1, n):
    test = copy.copy(s[j])
    for k in s[i]:
      if(k in test):
        test.remove(k)
    if(len(test) == 0):
      count += 1

print(count)


### FIXED CODE ###

import collections

n = int(input())
s = list(''.join(sorted(input())) for i in range(n))
c = collections.Counter(s)
num = 0

for i in set(s):
  n = c[i]
  num += (n * (n - 1)//2)
print(num)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import math
a = int(input())
b = round(math.sqrt(a))
while a % b != 0:
    b+=1
c = int(a / b)
print(b+c-2)

### FIXED CODE ###

# -*- coding: utf-8 -*-
import math
a = int(input())
b = round(math.sqrt(a))
while a % b != 0:
    b -= 1
c = int(a / b)
print(b + c - 2)
### BUGGY CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF for _ in range(H+1)]

DP[0] = 0

for h in range(H+1):
    for (damage, mp)  in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])

### FIXED CODE ###

import sys

H, N = map(int, input().split())
MAGICS = list(list(map(int, input().split())) for _ in range(N))

INF = sys.maxsize
MAX = max(x[0] for x in MAGICS)
DP = [INF] * (H+1)

DP[0] = 0

for h in range(H+1):
    for (damage, mp) in MAGICS:
        DP[h] = min(DP[max(h - damage, 0)] + mp, DP[h])

print(DP[H])
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
ans = 0
l_1 = []
l_2 = []

for i in range(N):
  l_1.append(A[i]+i)
  l_2.append(i-A[i])
  
for num in l_1:
  ans += l_2.count(num)
      
print(ans)


### FIXED CODE ###

from collections import defaultdict
 
n = int(input())
a = list(map(int, input().split()))
ap = defaultdict(int)
for i in range(n):
    ap[i - a[i]] += 1

ans= 0
for i in range(n):
    ans += ap[a[i] + i]
print(ans)
### BUGGY CODE ###

import sys
from functools import lru_cache
Q = int(input())
LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

@lru_cache(maxsize=None)
def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

like = [False] * (10 ** 5 + 1)
for x in range(1, len(like), 2):
    like[x] = isprime(x) and isprime((x + 1) // 2)

for l, r in LR:
    ans = len([1 for x in like[l:r+1] if x])
    print(ans)

### FIXED CODE ###

import sys
from functools import lru_cache
Q = int(input())
LR = [tuple(map(int, sys.stdin.readline().split())) for _ in range(Q)]

@lru_cache(maxsize=None)
def isprime(x):
    if x == 1:
        return False
    i = 2
    while i * i <= x:
        if x % i == 0:
            return False
        i += 1
    return True

s = [0] * (10 ** 5 + 1)
for x in range(1, len(s)):
    s[x] = s[x-1]
    if isprime(x) and isprime((x + 1) // 2):
        s[x] += 1

for l, r in LR:
    ans = s[r] - s[l-1]
    print(ans)
### BUGGY CODE ###

import math

H, N = list(map(int, input().split()))
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

dp = [0]*(H+1)

dp[0] = 0

for i in range(1,H+1):
    dp_min = math.inf
    for j in range(N):
        dp_min = min(dp_min, dp[max(0,i-A[j])] + B[j])
    dp[i] = dp_min

print(dp[H])

### FIXED CODE ###

import math

H, N = list(map(int, input().split()))
A = [0]*N
B = [0]*N
for i in range(N):
    A[i], B[i] = list(map(int, input().split()))

dp = [0]*(H+1)

dp[0] = 0

for i in range(1,H+1):
    dp_min = math.inf
    for j in range(N):
        dp_min = min(dp_min, dp[max(0,i-A[j])] + B[j])
    dp[i] = dp_min

print(dp[H])
### BUGGY CODE ###

n,m=map(int,input().split())
res=0
for i in range(m//n+1)[::-1]:
    if m%i==0:
        res=i
        break

print(res)

### FIXED CODE ###

N,M = map(int, input().split())
L = []
 
for i in range(1,int(M**0.5)+1):
    if M % i == 0:
        L.append(i)
        L.append(int(M / i))
L1 = [i for i in L if M / i >= N]
print(max(L1))
### BUGGY CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        power = 1
        for s in S[::-1]:
            ints += int(s) * power
            r = ints % P
            rcounts[r] += 1
            power *= 10
        c = 0
        for v in rcounts:
            c += v*(v-1)//2
        return c
    print(solve(N, P, S))

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

if P == 2 or P == 5:
    def solve25(N, P, S):
        c = 0
        for i in range(N-1, -1, -1):
            if int(S[i]) % P == 0:
                # 以降桁を増やしてもOK
                c += i+1
        return c
    print(solve25(N, P, S))
else:
    def solve(N, P, S):
        rcounts = [0] * P
        rcounts[0] = 1 # sそのものが割り切れた場合に引き算する相手がいないから
        ints = 0
        for i, s in enumerate(S[::-1]):
            ints += int(s) * pow(10, i, P)
            r = ints % P
            rcounts[r] += 1
        c = 0
        for v in rcounts:
            c += v*(v-1)//2
        return c
    print(solve(N, P, S))
### BUGGY CODE ###

import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    ans=0
    # for i in range(N):
    #     for j in range(N):
    #         if i != j and A[i]%A[j]==0:
    #             break
    #         elif j==N-1:
    #             ans+=1

    for i,a in enumerate(A):
        a_set=set(make_divisors(a))
        if a_set.isdisjoint(set(A[:i])|set(A[i+1:])):
            ans+=1

    print(ans)

def make_divisors(n):
    lower_divisors , upper_divisors = [], []
    i = 1
    while i*i <= n:
        if n % i == 0:
            lower_divisors.append(i)
            if i != n // i:
                upper_divisors.append(n//i)
        i += 1
    return lower_divisors + upper_divisors[::-1]

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import os
import itertools
from collections import deque

def main():
    if os.getenv("ENV")=='LOCAL':
        sys.stdin = open(os.path.dirname(__file__)+'/input.txt', 'r')

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

    A.sort()
    ans=0
    # print(A)

    T=[True]*A[-1]
    # T[0]=False

    for i,a in enumerate(A):
        if T[a-1]:
            j=2*a
            while j <= A[-1]:
                T[j-1]=False
                j+=a
            if not i+1==len(A):
                if A[i]==A[i+1]:
                    T[a-1]=False

    for a in A:
        if T[a-1]:
            ans+=1

    print(ans)

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

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

def gcd_list(numbers):
    return reduce(math.gcd, numbers)

K = int(input())
ans = 0
for a in range(1,200+1):
  for b in range(1, 200+1):
    for c in range(1, 200+1):
      ans += gcd(a,b,c) 
print(ans)

### FIXED CODE ###

import math
from functools import reduce

def gcd(*numbers):
    return reduce(math.gcd, numbers)

K = int(input())
three = 0
six = 0
same = 0
for a in range(1,K+1):
  for b in range(a, K+1):
    for c in range(b, K+1):
      if(a != b and b != c and a != c):
        six += gcd(a,b,c)
      elif(a == b and b == c and c == a):
        same += a
      else:
        three += gcd(a,b,c)

print(six * 6 + three * 3 + same)
### BUGGY CODE ###

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

n,k=mdata()
lis=[]
dp=[0]*(n)
dp[0]=1
for i in range(k):
    l,r=mdata()
    for j in range(l,r+1):
        lis.append(j)
lis.sort()
for i in range(1,n):
    for j in lis:
        if j>i:
            break
        dp[i]=(dp[i]+dp[i-j])%mod
out(dp[-1])

### FIXED CODE ###

import sys, math
import io, os
#data = io.BytesIO(os.read(0,os.fstat(0).st_size)).readline
from bisect import bisect_left as bl, bisect_right as br, insort
from heapq import heapify, heappush, heappop
from collections import defaultdict as dd, deque, Counter
# from itertools import permutations,combinations
def data(): return sys.stdin.readline().strip()
def mdata(): return list(map(int, data().split()))
def outl(var): sys.stdout.write(' '.join(map(str, var)) + '\n')
def out(var): sys.stdout.write(str(var) + '\n')
from decimal import Decimal
# from fractions import Fraction
# sys.setrecursionlimit(100000)
mod = 998244353
INF=float('inf')

n,k=mdata()
set1=set()
dp=[0]*(n)
s=[0]*n
lis=sorted([mdata() for i in range(k)],key=lambda x:x[0])
for i,j in lis:
    for m in range(i,j+1):
        set1.add(m)
m=lis[0][0]
for i in range(m,n):
    for j in range(k):
        if lis[j][0]>=i:
            break
        dp[i]+=s[i-lis[j][0]]-s[i-min(lis[j][1],i-1)-1]
    if i in set1:
        dp[i]+=1
    dp[i]%=mod
    s[i]=dp[i]+s[i-1]
out(dp[-1])
### BUGGY CODE ###

T = input()

replace = ""
target = []
for i in range(len(T)):
    if (T[i] == "?"):
        replace += "D"
    else:
        replace += T[i]

print(replace)

### FIXED CODE ###

T = input()

print(T.replace("?", "D"))
### BUGGY CODE ###

from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd,numbers)

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

def func(i):
    res = []
    for j,a in enumerate(A):
        if i == j:
            continue
        res.append(a)
    return res

ans = 0

for i in range(N):
    res = gcd_list(func(i))
    if res > ans:
        ans = res

print(ans)

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def gcd_list(numbers):
    return reduce(gcd,numbers)

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

res1 = [gcd(A[-1],a) for a in A]

min_res = min(res1)
index = res1.index(min_res)

res1 = [A[i] for i in range(N) if i != index]
res2 = A[:N-1]

res1 = gcd_list(res1)
res2 = gcd_list(res2)

print(max(res1,res2))
### BUGGY CODE ###

from collections import Counter

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

kosu = [0] * N

for i in range(N):
    kosu = Counter(A)

tempSum = 0
for i in range(N):
    tempSum += kosu[i+1] * (kosu[i+1] - 1) // 2


def C(N):
    if N <= 0:
        return 0
    else:
        return N*(N-1)//2


for a in A:
    print(tempSum - C(kosu[a]) + C(kosu[a] - 1))




### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))

cnt = Counter(A)

ans = 0
for v in cnt.values():
    ans += v * (v - 1) // 2

for k in A:
    # n*(n-1)//2 - (n-1)*(n-2)//2 = n - 1
    print(ans - (cnt[k] - 1))