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

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

from collections import*
C=Counter(S)
M=min(26,len(C))

from itertools import*

ans=0
i=1
while i<=M:
    L=list(combinations(C.values(),i))
    j=0
    while j<len(L):
        a=1
        for l in L[j]:
            a=a*l%(10**9+7)
        ans+=a
        ans%=(10**9+7)
        j+=1
    i+=1

print(ans)

### FIXED CODE ###

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

from collections import*
C=Counter(S)

ans=1
for c in C.values():
    ans*=(c+1)%(10**9+7)
ans=(ans-1)%(10**9+7)

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

N = int(input())

A = list(map(int, input().split()))
a = [0] * N

for i in range(N-1):
  a[i] = A.count(i+1)

for s in range(N):
  print(a[s])

### FIXED CODE ###

N = int(input())

A = list(map(int, input().split()))
a = [0] * N

for i in range(N-1):
  k = A[i]
  a[k-1] += 1

for l in range(N):
  print(a[l])
### BUGGY CODE ###

import heapq
def SME(start,end):
    if end > N : end = N
    count = 0
    for i,x in enumerate(Whole[start:end]):
        heapq.heappush(A,[x,i])
    for j in range(start,end):
        a = heapq.heappop(A)
        if None not in ANS[a[1]:a[1]+L] : continue
        for i in range(L):
            idx = a[1] + i
            try :
                if ANS[idx] : continue
                else :
                    ANS[idx] = a[0]
                    count += 1
            except IndexError : continue
        if count > N * parameter : break
    for i in range(L):
        if ANS[i] : continue
        else : ANS[i] = min(Whole[:i+1])
    i = L
    while i < N :
        if None not in ANS[i:i+50] :
            i += 50
            continue
        if ANS[i] : 
            i += 1
            continue
        else : 
            ANS[i] = min(Whole[i+1-L:i+1])
            i+=1
    return ANS
[N,L] = [int(x) for x in input().split()]
Whole = [int(x) for x in input().split()]
A = []
parameter = 0.999
ANS = [None]*N
ANS = SME(0, N)
for i in ANS[L-1:-1]:print(i, end=" ")
print(ANS[-1])

### FIXED CODE ###

def ascend(a,b):
    mini = min(A[a:a+L])
    ans[a] = mini
    for i in range(a+1,b):
        if A[i+L-1] <= mini : mini = A[i+L-1]
        elif A[i-1] == mini : mini = min(A[i:i+L])
        ans[i] = mini

def descend(a,b):
    mini = min(A[b-1:b+L-1])
    ans[b-1] = mini
    for i in range(b-2,a-1,-1):
        if A[i] <= mini : mini = A[i]
        elif A[i+L] == mini: mini = min(A[i:i+L])
        ans[i] = mini
    
[N,L] = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
ans = [None]*(N-L+1)
count = 0;
if N > 10 ** 4:
    for i in range(100):
        if A[i+1] > A[i] : count += 1
    if count > 80 : descend(0, N-L+1)
    else : ascend(0,N-L+1)
else :
    ascend(0, N-L+1)
for i in ans[:-1] : print(i, end=" ")
print(ans[-1])
### BUGGY CODE ###

n = int(input())
mod = pow(10, 9) + 7
ans = 1
for i in range(1, n+1):
    ans *= i
print(ans%mod)

### FIXED CODE ###

n = int(input())
mod = pow(10, 9) + 7
ans = 1
for i in range(1, n+1):
    ans *= i
    ans %= mod

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

n = int(input())
print(sum(range(1,n)))

### FIXED CODE ###

n = int(input())
print((n*(n-1))//2)
### BUGGY CODE ###

s = input().split()
n=int(s[0])
x=int(s[1])-1
y=int(s[2])-1
inf=float('inf')
map=[[0]*n for i in range(n)]
map[x][y]=1
for i in range(n):
    for j in range(i+1,n):
        map[i][j]=min(abs(j-i),abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))
for i in range(1,n):
    count=0
    for j in map:
        count+=j.count(i)
    print(count)


### FIXED CODE ###

s = input().split()
n=int(s[0])
x=int(s[1])-1
y=int(s[2])-1
inf=float('inf')
map={}
for i in range(n):
    map[i]=0
for i in range(n):
    for j in range(i+1,n):
        map[min(abs(j-i),abs(x-i)+1+abs(j-y),abs(y-i)+1+abs(j-x))]+=1
for i in range(1,n):
    print(map[i])
### BUGGY CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

import re

pat = "AC"

for i in range(q):
    s_part = s[lr[i][0]-1:lr[i][1]]
    m = re.findall(pat, s_part)
    print(len(m))


### FIXED CODE ###

n, q = map(int, input().split())
s = input()
lr = [list(map(int, input().split())) for _ in range(q)]

t = [0] * (n+1)

for i in range(n):
    t[i+1] = t[i] + (1 if s[i:i+2] == "AC" else 0)

for i in range(q):
    l, r = lr[i][0]-1, lr[i][1]-1
    print(t[r] - t[l])
### BUGGY CODE ###

N = int(input())

count = [0 for _ in range(200000)]
line = [int(i) for i in input().split()]
index = []

for i in line:
	if count[i] == 0:
		index.append(i)
	count[i] += 1


for i in line:
	count[i] -= 1
	result = 0
	for j in index:
		result += (count[j]*(count[j]-1))//2
	count[i] += 1
	print(result) 


### FIXED CODE ###

N = int(input())

count = [0 for _ in range(200000)]
line = [int(i) for i in input().split()]
pattern = [0 for _ in range(200000)]
sum = 0
# index = []

for i in line:
	# if count[i] == 0:
		# index.append(i)
	count[i] += 1

for num in count:
	sum += (num*(num-1))//2



for i in line:
	if count[i] > 2:
		result = sum - (count[i]-1) 
	elif count[i] == 2:
		result = sum - 1
	elif count[i] == 1:
		result = sum
	print(result)
### BUGGY CODE ###

N, M = map(int, input().split())
ab=[]
for _ in range(M):
    ab.append(tuple(map(int, input().split())))
#print(ab)

for island in range(2,N):
    if (1,island) in ab and (island,N) in ab:
        print('POSSIBLE')
        break
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

N, M = map(int, input().split())
ab=[]
for _ in range(M):
    ab.append(tuple(map(int, input().split())))
#print(ab)

from_1=set([el[1] for el in ab if el[0]==1])
from_N=set([el[0] for el in ab if el[1]==N])
#print(from_1, from_N)
if from_1 & from_N:
    print('POSSIBLE')
else:
    print('IMPOSSIBLE')
### BUGGY CODE ###

import sys
s = sys.stdin.readline().strip()
n = int(sys.stdin.readline().strip())
for _ in range(n):
    head = ''
    tail = ''
    q = sys.stdin.readline().strip()
    if q[0] == '1':
        s = s[::-1]
    else:
        _, f, c = q.split()
        if f == '1':
            head = c
        else:
            tail = c
    s = head + s + tail
print(s)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
read = sys.stdin.read

#h,w,k = [int(i) for i in read().split()]


s = input()
u = ""
t = ""
q = int(input())
num = 0

for _ in range(q):
    a = readline().split()
    if len(a)==1:
        u,t = t,u
        num ^= 1
    else:
        f = int(a[1])
        c = a[2]
        if f==1:
            t += c
        else:
            u += c

if num:
    print(t[::-1]+s[::-1]+u)
else:
    print(t[::-1]+s+u)
### BUGGY CODE ###

s = str(input())
now = [0] * 2019
mod = 2019
ans,cnt = 0,1
lis = [int(s[-(1+i)]) for i in range(len(s))]
for num in lis:
    now[0] += 1
    num *= 10**cnt
    num %= mod
    next = [0] * mod
    for i in range(2019-num):
        next[num+i] += now[i]
    for i in range(num):
        next[i] += now[2019-num+i]
    ans += next[0]
    cnt += 1
    now = next
print(ans)

### FIXED CODE ###

s = str(input())
now = [0] * 2019
mod = 2019
ans,cnt = 0,1
lis = [int(s[-(1+i)]) for i in range(len(s))]
for num in lis:
    now[0] += 1
    num *= cnt
    num %= mod
    next = [0] * mod
    for i in range(2019-num):
        next[num+i] += now[i]
    for i in range(num):
        next[i] += now[2019-num+i]
    ans += next[0]
    cnt *= 10
    cnt %= mod
    now = next
print(ans)
### BUGGY CODE ###

def main():
  import sys
  input=sys.stdin.readline
  class BinaryIndexedTree:
    def __init__(self,n):
      self.bit=[0]*n
    def add(self,i,x):
      i+=1
      while i<=len(self.bit):
        self.bit[i-1]+=x
        i+=i&-i
    def sum_sub(self,i):
      a=0
      i+=1
      while i:
        a+=self.bit[i-1]
        i-=i&-i
      return a
    def sum(self,i,j):
      a=self.sum_sub(j+1)
      if i!=0:a-=self.sum_sub(i-1)
      return a
  n,q=map(int,input().split())
  a=list(map(lambda x:int(x)-1,input().split()))
  ans=[0]*q
  queries=[list(map(lambda x:int(x)-1,input().split()))[::-1]+[i]for i in range(q)]
  queries.sort()
  queries.append((10**20,0,0))
  lastAppeared=[-1]*n
  bitt=BinaryIndexedTree(n)
  j=0
  for i in range(n):
    if lastAppeared[a[i]]!=-1:
      bitt.add(lastAppeared[a[i]],-1)
      bitt.add(i,1)
      lastAppeared[a[i]]=i
    else:
      bitt.add(i,1)
      lastAppeared[a[i]]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=bitt.sum(l,r-1)
  print(*ans)

if __name__ == "__main__":
  main()

### FIXED CODE ###

def main():
  def add(i,x):
    i+=1
    while i<=n:
      bit[i-1]+=x
      i+=i&-i
  def sum_sub(i):
    a=0
    i+=1
    while i:
      a+=bit[i-1]
      i-=i&-i
    return a
  def sum(i,j):
    a=sum_sub(j+1)
    if i!=0:a-=sum_sub(i-1)
    return a
  
  n,q,*x=map(int,open(0).read().split())
  a=x[:n]
  queries=[]
  for i in range(q):
    l,r=x[n+i*2:n+(i+1)*2]
    l-=1
    r-=1
    queries.append(r<<40|l<<20|i)
  ans=[0]*q
  queries.sort()
  for i in range(q):
    ind=queries[i]%(1<<20)
    queries[i]>>=20
    l=queries[i]%(1<<20)
    queries[i]>>=20
    r=queries[i]
    queries[i]=[r,l,ind]
  queries.append([10*20])
  lastAppeared=[-1]*n
  bit=[0]*n
  j=0
  for i in range(n):
    if lastAppeared[a[i]-1]!=-1:
      add(lastAppeared[a[i]-1],-1)
      add(i,1)
      lastAppeared[a[i]-1]=i
    else:
      add(i,1)
      lastAppeared[a[i]-1]=i
    while queries[j][0]==i:
      r,l,ind=queries[j]
      j+=1
      ans[ind]=sum(l,r-1)
  print(*ans)
if __name__ == "__main__":
  main()
### BUGGY CODE ###

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

ans = 1
for i in range(N):
    ans *= A[i]

if (ans > 10**18):
    print(-1)
else:
    print(ans)


### FIXED CODE ###

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

if (0 in A):
    print(0)
    exit()

ans = 1
for i in range(N):
    if (ans > 10 ** 18):
        break
    ans *= A[i]

if (ans > 10**18):
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

import sys
n,y= map(int, input().split())

for a in range(n+1):
	for b in range(n+1):
		for c in range(n+1):
			if a + b + c < n:
				continue
			if a + b + c > n:
				break
			if (a + b + c == n) and (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()

print('-1 -1 -1')
sys.exit()

### FIXED CODE ###

import sys

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

for a in range(n+1):
	for b in range(n+1-a):
		c = n - a - b
		if (a * 10000 + b * 5000 + c * 1000 == y):
				print(str(a) + ' ' + str(b) + ' ' + str(c))
				sys.exit()
	
print('-1 -1 -1')
sys.exit()
### BUGGY CODE ###

s=input()
n=len(s)

ans=0

a=[]
for i in range(n):
    if s[i]=="B":
        a.append(0)
    else:
        a.append(1)

count=0
pre=-1
while True:
    if count==pre:
        break
    pre=count
    for i in range(n):
        if i+1<n and a[i]==0 and a[i+1]==1:
            a[i]=1
            a[i+1]=0
            count+=1
    
print(count)

### FIXED CODE ###

s=input()
n=len(s)

ans=0
j=0
for i in range(n):
    if s[i]=="W":
        ans+=(i-j)
        j+=1
print(ans)
### BUGGY CODE ###

x = int(input())

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
  
divisors = make_divisors(x)

for d in divisors:
  b = -d
  f = False
  while True:
    if (b+d)**5 - b**5 == x:
      f = True
      break
    elif (b+d)**5 - b**5 > x and b > 0:
      break
    b += 1
  if f:
    print(b+d, b)
    break

### FIXED CODE ###

x = int(input())

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
  
divisors = make_divisors(x)

for d in divisors:
  b = - int(x**(1/5)) - 1
  f = False
  while True:
    if (b+d)**5 - b**5 == x:
      f = True
      break
    elif (b+d)**5 - b**5 > x and b > 0:
      break
    b += 1
  if f:
    print(b+d, b)
    break
### BUGGY CODE ###

n = int(input())
list_n_ans = [1]
k = -1
ans = 0

while n >= 2:
    list_n_ans.append(n*list_n_ans[-1])
    n -= 2


n_str = str(list_n_ans[-1])


n_str_list = list(n_str)


while n_str_list[k] == "0":
    ans += 1
    k -= 1

print(ans)

### FIXED CODE ###

n = int(input())

if n % 2 == 1:
    print(0)
elif n % 2 == 0:
    ans = 0
    k = 10
    while n >= k:
        ans += n//k
        k *= 5
        
    print(ans)
### BUGGY CODE ###

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(d):
        steps_taken = len(d)-j
        if i-steps_taken < 0: break
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
    d.append(min_cost)

print(d[-1])

### FIXED CODE ###

from collections import deque

line1 = input()
n, k = [int(num) for num in line1.split(" ")]
line2 = input()
h = [int(num) for num in line2.split(" ")]

d = deque([0], k)

for i in range(1, len(h)):
    min_cost = float("inf")
    for j,cost in enumerate(reversed(d)):
        steps_taken = j+1
        if i-steps_taken < 0: break
        step_cost = abs(h[i]-h[i-steps_taken])
        min_cost = min(min_cost, cost + abs(h[i]-h[i-steps_taken]))
        if step_cost == 0: break
    d.append(min_cost)

print(d[-1])
### BUGGY CODE ###

import fractions
import copy
from functools import reduce
num = int(input())
nums = [int(s) for s in input().split()]

def gcd_list(numbers):
    return reduce(fractions.gcd, nums)
def gcd(*numbers):
    return reduce(fractions.gcd, numbers)
answer = []
for i in range(num):
  ls = copy.deepcopy(nums)
  del ls[i]
  answer.append(gcd(*ls))
print(max(answer))

### FIXED CODE ###

def gcd(a,b):
  if not a or not b:
    return 0
  else:
    while b:
      a,b = b,a%b
    return a

num = int(input())
nums = [int(s) for s in input().split()]

l = nums[0]
r = nums[-1]
left = []
right = []
for i in range(num-1):
  l,r = gcd(l,nums[i]), gcd(r,nums[-i-1])
  left.append(l)
  right.append(r)
answer = [left[-1],right[-1]]
for i in range(len(left)-1):
  answer.append(gcd(left[i],right[-i-2]))
print(max(answer))
### BUGGY CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = sorted(list(C.keys()))
    lenb = len(B)
    Boo = [True]*lenb
    s,_ = sieve((10**6)+2)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    cnt = 0

    Even = []

    for i in range(lenb):
        if B[i]%2==0:
            Even.append((B[i],i))
    lenEven = len(Even)
    evenindex = 0

    for i in range(lenb):
        if Boo[i] :
            if C[B[i]]==1:
                    cnt += 1
            if B[i]<500001:
                temp = B[i]*2 -1
                if  B[i]%2==0:
                    evenindex += 1
                    for j in range(evenindex,lenEven):
                        if Boo[Even[j][1]] and Even[j][0]>temp and Even[j][0] % B[i] == 0:
                            Boo[Even[j][1]]= False
                else:
                    for j in range(i+1,lenb):
                        if Boo[j] and s[B[j]-1]==False and B[j]>temp and B[j] % B[i] == 0:
                            Boo[j] = False

    print(cnt)


def sieve(n):
    is_prime = [True for _ in range(n+1)]
    is_prime[0] = False

    for i in range(2, n+1):
        if is_prime[i-1]:
            j = 2 * i
            while j <= n:
                is_prime[j-1] = False
                j += i
    table = [ i for i in range(1, n+1) if is_prime[i-1]]
    return is_prime, table


if __name__ == '__main__':
    main()

### FIXED CODE ###

import collections

def main():
    N  = int(input()) 
    A=list(map(int, input().split()))
    C = collections.Counter(A)
    B = list(set(A))
    B.sort()
    lenb = len(B)
    Boo = [True]*lenb
    ZENBU = [False]*(10**6+4)

    if C[1]>1:
        print(0)
        return
    if C[1]==1:
        print(1)
        return

    for i in range(lenb):
        temp = 2
        if ZENBU[B[i]]==False:
            while B[i]*temp < 1000002:
                ZENBU[B[i]*temp] = True
                temp+=1

    cnt = 0
    for i in range(lenb):
        if ZENBU[B[i]]==False and C[B[i]]==1:
            cnt += 1

    print(cnt)


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

inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        x, y, p = map(int, input().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    dx = [[inf] * N for _ in range(1<<N)]
    dy = [[inf] * N for _ in range(1<<N)]
    for i in range(1 << N):
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(X[j])
                Yline.append(Y[j])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[i][j] = min(dx[i][j], abs(x - X[j]))
                dy[i][j] = min(dy[i][j], abs(y - Y[j]))

    ans = [inf] * (N+1)
    beki2 = [1<<j for j in range(N)]
    for i in range(3**N):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki2[j]
            else:
                k += 1
                iy += beki2[j]
        cost = 0
        for j in J:
            p = P[j]
            cost += min(dx[ix][j], dy[iy][j]) * p
        ans[k] = min(ans[k], cost)
    for c in ans:
        print(c)


if __name__ == '__main__':
    main()


### FIXED CODE ###

inf = 10**15


def main():
    import sys
    input = sys.stdin.readline

    N = int(input())
    X = []
    Y = []
    P = []
    for _ in range(N):
        x, y, p = map(int, input().split())
        X.append(x)
        Y.append(y)
        P.append(p)

    dx = [[inf] * N for _ in range(1<<N)]
    dy = [[inf] * N for _ in range(1<<N)]
    for i in range(1 << N):
        Xline = [0]
        Yline = [0]
        for j in range(N):
            if i>>j&1:
                Xline.append(X[j])
                Yline.append(Y[j])
        for j in range(N):
            for x, y in zip(Xline, Yline):
                dx[i][j] = min(dx[i][j], abs(x - X[j]))
                dy[i][j] = min(dy[i][j], abs(y - Y[j]))

    ans = [inf] * (N+1)
    beki = [1<<j for j in range(N)]
    for i in range(3**(N-1)):
        M = i
        k = 0
        ix = iy = 0
        J = []
        for j in range(N-1):
            M, m = divmod(M, 3)
            if m == 0:
                J.append(j)
            elif m == 1:
                k += 1
                ix += beki[j]
            else:
                k += 1
                iy += beki[j]
        for x in range(3):
            kk = k
            ix_ = ix
            iy_ = iy
            if x == 0:
                J.append(N-1)
            elif x == 1:
                kk += 1
                ix_ += beki[N-1]
            else:
                kk += 1
                iy_ += beki[N-1]
            cost = 0
            for j in J:
                p = P[j]
                cost += min(dx[ix_][j], dy[iy_][j]) * p
            ans[kk] = min(ans[kk], cost)
    for c in ans:
        print(c)


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

import sys
sys.setrecursionlimit(2147483647)
input=sys.stdin.readline

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

print(result)  


### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)

h,w=map(int,input().split())
s=list(input() for _ in range(h))

yoko=[[0]*w for _ in range(h)]
tate=[[0]*w for _ in range(h)]

def yoko_check(y,x,cnt):
    global yoko,s
    if x==w-1:
        yoko[y][x]=cnt
        return cnt
    else:
        if s[y][x+1]=="#":
            yoko[y][x]=cnt
            return cnt
        else:
            yoko[y][x]=yoko_check(y,x+1,cnt+1)
            return yoko[y][x]


def tate_check(y,x,cnt):
    global tate,s
    if y==h-1:
        tate[y][x]=cnt
        return cnt
    else:
        if s[y+1][x]=="#":
            tate[y][x]=cnt
            return cnt
        else:
            tate[y][x]=tate_check(y+1,x,cnt+1)
            return tate[y][x]


for y in range(h):
    for x in range(w):
        if yoko[y][x]==0 and s[y][x]==".":
            yoko_check(y,x,1)
        if tate[y][x]==0 and s[y][x]==".":
            tate_check(y,x,1)

#print(tate)

result=0
for y in range(h):
    for x in range(w):
        if s[y][x]==".":
            result=max(result,tate[y][x]+yoko[y][x]-1)  

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

t = input()
if len(t) == 1:
    if t == '?':
        print('D')
    else:
        print(t)
elif len(t) == 2:
    if t == '??' or t == 'P?' or t == '?D':
        print('PD')
    elif t == 'D?':
        print('DD')
    elif t == '?P':
        print('DP')
    else:
        print(t)
else:
    ans = ''
    for i in range(len(t)):
        if i == 0:
            if t[i] == '?':
                if t[i+1] == '?':
                    ans += 'P'
                else:
                    ans += 'D'
            else:
                ans += t[i]
        elif i == len(t)-1:
            if t[len(t)-1] == '?':
                ans += 'D'
            else:
                ans += t[len(t)-1]
        else:
            if t[i+1] == '?' and t[i-1] == 'D':
                ans += 'P'
            elif t[i] == 'P' or t[i] == 'D':
                ans += t[i]
            else:
                ans += 'D'
    print(ans)

### FIXED CODE ###

print(input().replace('?','D'))
### BUGGY CODE ###

n,c=map(int,input().split())
xpos=[]
ypos=[]
pos=[]
for _ in range(n):
  x,y=map(int,input().split())
  xpos.append(x)
  ypos.append(y)
  pos.append([x,y])
xpos=sorted(xpos)
ypos=sorted(ypos)
ans=10**20
for i in range(n):
  for j in range(i+1,n):
    for k in range(n):
      for l in range(k+1,n):
        lx,rx=xpos[i],xpos[j]
        ly,ry=ypos[k],ypos[l]
        cnt=0
        for tx,ty in pos:
          if lx<=tx<=rx and ly<=ty<=ry:
            cnt+=1
        if cnt>=c:
          ans=min(ans,(rx-lx)*(ry-ly))
print(ans)

### FIXED CODE ###

n,c=map(int,input().split())
xpos=[]
ypos=[]
pos=[]
for _ in range(n):
  x,y=map(int,input().split())
  xpos.append(x)
  ypos.append(y)
  pos.append([x,y])
xpos=sorted(xpos)
ypos=sorted(ypos)
ans=10**20
for i in range(n):
  for j in range(i+1,n):
    for k in range(n):
      for l in range(k+1,n):
        lx,rx=xpos[i],xpos[j]
        ly,ry=ypos[k],ypos[l]
        cnt=0
        for tx,ty in pos:
          if lx<=tx<=rx and ly<=ty<=ry:
            cnt+=1
        if cnt>=c:
          ans=min(ans,(rx-lx)*(ry-ly))
print(ans)