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

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    naf = lambda: list(map(float, sys.stdin.readline().split()))

    n = ni()
    p = naf()

    dp = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
    dp[0][0] = 1

    # dp[i][j] : pのうちi個めまでを投げて、表がj個出る確率
    for i in range(n):
        for j in range(n):
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    print(sum(dp[n][(n + 1) // 2:]))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
# import re
import math
import collections
# import decimal
import bisect
import itertools
import fractions
# import functools
import copy
# import heapq
import decimal
# import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    naf = lambda: list(map(float, sys.stdin.readline().split()))

    n = ni()
    p = naf()

    dp = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
    dp[0][0] = 1

    # dp[i][j] : pのうちi個めまでを投げて、表がj個出る確率
    for i in range(n):
        for j in range(n):
            dp[i + 1][j + 1] += dp[i][j] * p[i]
            dp[i + 1][j] += dp[i][j] * (1 - p[i])

    print(sum(dp[n][(n + 1) // 2:]))


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

N = int(input())
S = []
for _ in range(N):
    S.append(int(input()))


for i in range(len(S)):
        maax=-100
        for j in range(len(S)):
                if i==j:
                        continue
                if S[j] > maax:
                        maax = S[j]
        print(maax)

### FIXED CODE ###

N = int(input())
S = []
for _ in range(N):
    S.append(int(input()))


max1=-1
max2=-10

max1_ind=-100
max2_ind=-100

for i in range(len(S)):
        if S[i] > max1:
                max2=max1
                max2_ind = max1_ind

                max1=S[i]
                max1_ind=i
        elif S[i] > max2:
                max2=S[i]
                max2_ind=i

for i in range(len(S)):
        if i != max1_ind:
                print(max1)
        else:
                print(max2)
### BUGGY CODE ###

def main():
    X = input()
    count = 0
    for i in range(10**4):
        count += X.count("ST")
        X = X.replace("ST","")
    print(len(X))


if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import deque
def main():
    X = input()
    stack = deque([])
    for i in range(len(X)):
        if X[i] == "S":
            stack.append(X[i])
        else:
            if len(stack) != 0:
                tmp = stack.pop()
                if tmp == "T":
                    stack.append(tmp)
                    stack.append(X[i])
            else:
                stack.append(X[i])
    print(len(stack))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

n = int(input())
l = list(map(int, input().split()))
l = sorted(l)
ans = 0

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):
            if l[k] < l[i] + l[j]:
                ans += 1
print(ans)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
A = sorted(A)
ans = 0


def q(k):
    if A[k] < A[i] + A[j]:
        return True
    else:
        return False


for i in range(n):
    for j in range(i + 1, n):
        l = j
        r = n
        while r - l > 1:
            mid = (l + r) // 2
            if q(mid):
                l = mid
            else:
                r = mid
        ans += (l - j)


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

N = int(input())
S = input()
while True:
    T = S.replace('#.','')
    if T == S:
        break
    else:
        S = T
print((N-len(S))//2)

### FIXED CODE ###

N = int(input())
S = input()
black = 0
ans = 0

for s in S:
    if s == "#":
        black += 1
    else:
        if black > 0:
            ans += 1
            black -= 1

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

H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = []
            if i == j == 0:
                b.append(0)
            if i > 0:
                b.append(dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b.append(dp[i][j-1] + shift[i][j-1])
            dp[i][j] = min(b)
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans


### FIXED CODE ###

H, W = map(int, raw_input().split())
a = [raw_input().strip() for _ in xrange(H)]
a = map(''.join, zip(*a))
ans = 0
def solve(a, c):
    shift = [[0] * (H+1) for _ in xrange(H+1)]
    for i in reversed(xrange(H)):
        for j in reversed(xrange(H)):
            shift[i][j] = shift[i+1][j+1] + int(a[H-1-i] == c[H-1-j])
    dp = [[float('inf')] * (H+1) for _ in xrange(H+1)]
    for i in xrange(H+1):
        for j in xrange(H+1):
            b = 2147483647
            if i == j == 0:
                b = 0
            if i > 0:
                b = min(b, dp[i-1][j] + shift[i-1][j])
            if j > 0:
                b = min(b, dp[i][j-1] + shift[i][j-1])
            dp[i][j] = b
    #print a, c, shift
    return dp[H][H]
for i in xrange(W-1):
    i1 = i
    i2 = i+1
    ans += solve(a[i1], a[i2])
print ans
### BUGGY CODE ###

s = int(input())
x1=0
y1=0
x2=0
y2=0
x3=0
y3=0
# x2y3-y2x3=s
cnt=0
i=0
while(1):
    cnt=i*i
    if cnt>s: break
    i+=1
x2=i-1
y3=i-1
y2=-1
x3=s-(i-1)**2
print(x1+1,y1+1,x2+1,y2+1,x3+1,y3+1)


### FIXED CODE ###

import math
s = int(input())
x1=0
y1=0
x2=0
y2=0
x3=0
y3=0
i=math.ceil(s**(1/2))
x2=i
y3=i
y2=1
x3=(i)**2-s
print(x1,y1,x2,y2,x3,y3)
### BUGGY CODE ###

n = int(input())
lst = list(map(int, input().split()))

cnt = 0
for i in range(len(lst)):
    num = lst[i]
    bl = True
    for j in lst[:i]:
        if num > j:
            bl = False
            break

    if bl:
        cnt += 1

print(cnt)


### FIXED CODE ###

n = int(input())
lst = list(map(int, input().split()))

cnt = 0
tmp_min = max(lst)
for i in range(len(lst)):
    num = lst[i]
    if num <= tmp_min:
        cnt += 1
        tmp_min = num

print(cnt)
### BUGGY CODE ###

N = int(input())
A = input().split()

result = 1
length = len(A)

for num in range(length):
    result = result * int(A[num])

max = 1000000000000000000;

if result <= max:
    print(result)
else:
    print("-1")

### FIXED CODE ###

n=int(input())
arr=list(map(int,input().split()))
arr=sorted(arr) #配列を昇順ソートしておく(配列に0がある場合0が先頭に来るので、場合分けの必要がなくなる)
ans=1
for val in arr:
 ans*=val #Pythonは多倍長整数をサポートしているので単に積を求めれば十分
 if ans>10**18:
   print(-1)
   break
else:
 print(ans)
### BUGGY CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    mid = int(left + (right-left)//2)
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)

### FIXED CODE ###

n,k = map(int, input().split())
A = list(map(int, input().split()))
F = list(map(int, input().split()))
A.sort()
F.sort(reverse=True)

def isOk(x):
    cost = 0
    for a, f in zip(A,F):
        eatable = x//f
        if eatable >= a:
            continue
        cost += a - eatable
    if cost <= k:
        return True
    return False

left = -1
right = A[-1] * F[0]
while left+1 < right:
    # mid = int(left + (right-left)//2)
    mid = (left+right)//2
    if isOk(mid):
        right = mid
    else:
        left = mid
print(right)
### BUGGY CODE ###

def solve():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    min_dist = 10 ** 9
    for i in range(n - k + 1):
        part = xs[i:i + k]
        length = abs(part[0] - part[-1])
        dist = min(abs(part[0]) + length, abs(part[-1]) + length)
        if dist < min_dist:
            min_dist = dist
    return min_dist


if __name__ == "__main__":
    print(solve())


### FIXED CODE ###

def solve():
    n, k = map(int, input().split())
    xs = list(map(int, input().split()))
    min_dist = 10 ** 9
    for i in range(n - k + 1):
        length = abs(xs[i] - xs[i + k - 1])
        dist = min(abs(xs[i]) + length, abs(xs[i + k - 1]) + length)
        if dist < min_dist:
            min_dist = dist
    return min_dist


if __name__ == "__main__":
    print(solve())
### BUGGY CODE ###

import numpy as np

# 入力部分
n, limit = map(int, input().split())
w, v = [], []
for i in range(n):
    a, b = map(int, input().split())
    w.append(a)
    v.append(b)

# dpテーブルの要素数
V = sum(v)

INF = 1 << 60

dp = [[INF] * (V + 1) for _ in range(n + 1)]
dp[0][0] = 0

for i in range(n):
    for j in range(V + 1):
        dp[i + 1][j] = min(dp[i + 1][j], dp[i][j])
        if j - v[i] >= 0:
            dp[i + 1][j] = min(dp[i + 1][j], dp[i][j - v[i]] + w[i])

dp = np.array(dp)

ans = 0
for arr in dp:
    ans = max(ans, np.where(arr <= limit)[0].max())

print(ans)

### FIXED CODE ###

import numpy as np

N, W = map(int, input().split())
MAX_V = (10**3) * N + 1
INF = 1 << 60

dp = np.full(MAX_V, INF)
dp[0] = 0

for i in range(N):
    w, v = map(int, input().split())
    np.minimum(dp[v:], dp[:-v] + w, out=dp[v:])

print(np.where(dp <= W)[0].max())
### BUGGY CODE ###

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

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

iter_num = n - k + 1

ans = []
for i in range(iter_num):
	ans.append((sum(p[i:k+i])+k)/2)

print(max(ans))


### FIXED CODE ###

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

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

iter_num = n - k + 1

num = sum(p[0:k])
ans = [(num+k)/2]
for i in range(iter_num-1):
	num = num - p[i] + p[k+i]
	ans.append((num+k)/2)

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

n = int(input())
ls = [int(input()) for _ in range(n)]

def judge(n):
    if n == 2 or n == 3:
        return 1
    div = 3
    while div <= n/2+1:
        if n%2 == 0 or n%div == 0:
            return 0
        else:  
            div += 2
    return 1

print(sum(map(judge, ls)))


### FIXED CODE ###

n = int(input())
ls = [int(input()) for _ in range(n)]


def judge(n):
    if n == 2 or n == 3:
        return 1
    if n % 2 == 0:
        return 0
    i = 3
    while i <= n/i:
        if n%i == 0:
            return 0
        else:  
            i += 2
    return 1

print(sum(map(judge, ls)))
### BUGGY CODE ###

def pow_o(x, y):
    if n == 0:
        return 1
    if n % 2 == 0:
        return pow_o(x ** 2, y // 2)
    else:
        return x * pow_o(x ** 2, y // 2)

n, m, d = map(int, input().split())
sum = 0
patt = (n-d)
if d != 0:
    patt = 2 * patt
totyu = n ** (m-2)
beau = totyu * (m-1)
print(patt * beau / (totyu * n * n))

### FIXED CODE ###

n, m, d = map(int, input().split())
sum = 0
patt = n-d
if d != 0:
    patt = 2 * patt
print(patt * (m-1) / (n * n))
### BUGGY CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d] is not None:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return None

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


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

dic = [[] for _ in range(N)]
memo = [[None]*11 for _ in range(N)]

for m in range(M):
    a, b = tuple(map(int, input().split(' ')))
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())

vdc = [None]*Q

for q in range(Q):
    vdc[q] = tuple(map(int, input().split(' ')))

res = ['0']*N

for q in range(Q-1, -1, -1):
    v, d, c = vdc[q]
    dp(v, d, c)


print('\n'.join(res))


### FIXED CODE ###

import numpy as np

def dp(v, d, c):
    if memo[v-1][d]:
        return

    memo[v-1][d] = True
    if d == 0:
        res[v-1] = str(c)
        return

    dp(v, d-1, c)
    for e in dic[v-1]:
        dp(e, d-1, c)


N, M = [int(e) for e in input().split(' ')]

dic = [[] for _ in range(N)]
memo = [[False]*11 for _ in range(N)]

for m in range(M):
    a, b = [int(e) for e in input().split(' ')]
    dic[a-1].append(b)
    dic[b-1].append(a)

Q = int(input())


vdc = [[int(e) for e in input().split(' ')] for _ in range(Q)]

res = ['0']*N

[dp(v, d, c) for v, d, c in vdc[::-1]]


print('\n'.join(res))
### BUGGY CODE ###

from functools import reduce
from fractions import gcd
import numpy as np

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers, 1)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)

As = np.array(As)

print(np.sum(lcm//As) % mod)

### FIXED CODE ###

from functools import reduce
from fractions import gcd

def lcm_base(x, y):
    return (x * y) // gcd(x, y)

def lcm_list(numbers):
    return reduce(lcm_base, numbers)
mod = 10**9 + 7
n = int(input())
As = list(map(int, input().split()))

lcm = lcm_list(As)
b = [lcm//As[i] for i in range(n)]

print(sum(b) % mod)
### BUGGY CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())

N = ni()
g1, s1, b1 = nm()
g2, s2, b2 = nm()

INF = 10 ** 15


def solve():
    x1 = [g1, s1, b1]
    x2 = [g2, s2, b2]

    # dp[i] := max future donguri when we use i donguri
    dp = [-INF] * (N + 1)
    dp[0] = N
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 >= t2:
            continue
        for j in range(t1, N + 1):
            if dp[j - t1] >= N:
                dp[j] = max(dp[j], dp[j - t1] - t1 + t2)

    don = max(dp)
    dp = [0] * (don + 1)
    dp[0] = don
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 <= t2:
            continue
        for j in range(t2, don + 1):
            if dp[j - t2] >= N:
                dp[j] = max(dp[j], dp[j - t2] - t2 + t1)
    return max(dp)


print(solve())


### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 8)
ni = lambda: int(sys.stdin.readline())
nm = lambda: map(int, sys.stdin.readline().split())

N = ni()
g1, s1, b1 = nm()
g2, s2, b2 = nm()

INF = 10 ** 15


def solve():
    x1 = [g1, s1, b1]
    x2 = [g2, s2, b2]

    # dp[i] := max future donguri when we use i donguri
    dp = [-INF] * (N + 1)
    dp[0] = N
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 >= t2:
            continue
        for j in range(t1, N + 1):
            r = dp[j - t1] - t1
            if r >= 0 and dp[j] < r + t2:
                dp[j] = r + t2

    don = max(dp)
    dp = [0] * (don + 1)
    dp[0] = don
    for i in range(3):
        t1 = x1[i]
        t2 = x2[i]
        if t1 <= t2:
            continue
        for j in range(t2, don + 1):
            r = dp[j - t2] - t2
            if r >= 0 and dp[j] < r + t1:
                dp[j] = r + t1
    return max(dp)


print(solve())
### BUGGY CODE ###

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

arr = []
for i in range(n):
  a = list(map(int, input().split()))
  for j in range(a[1]):
    arr.append(a[0])
  
arr.sort()
print(arr[k - 1])

### FIXED CODE ###

n, k = map(int, input().split())
ab = [list(map(int, input().split())) for i in range(n)]

ab.sort(key=lambda x: x[0])
index = 0
for i in range(n):
  index += ab[i][1]
  if index >= k:
    ans = ab[i][0]
    break

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

def main():
    n = int(input())
    a=1
    l=[int(x) for x in input().split()]
    for i in range(len(l)):
        a=a*l[i]
        
    if a>10**18:
        a=-1
    print(a)
main()

### FIXED CODE ###

def main():
    n = int(input())
    a=1
    l=[int(x) for x in input().split()]
    if not(0 in l):
        for i in range(len(l)):
            a=a*l[i]
            if a>10**18:
                a=-1
                break
    else:
        a=0
    print(a)
main()
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode().rstrip()

ans = 0
for i in range(1000):
    i_ = '{:>03}'.format(i)
    idx = 0

    for s in S:
        if s == i_[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(500000)

N = int(readline())
S = readline().decode().rstrip()

ans = 0
for i in range(1000):
    i_ = '{:>03}'.format(i)
    idx = 0

    for s in S:
        if s == i_[idx]:
            idx += 1
        if idx == 3:
            ans += 1
            break

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

strs = input()
N = int(input())

Len = len(strs)

allstr = [] 

for i in range(Len):
    for j in range(i+1):
        allstr.append(strs[i-j:i+1])
        allstr2 = list(set(allstr))
        if len(allstr) > 5:
            allstr2.sort()
            allstr = allstr2[0:6]

allstr2 = list(set(allstr))        
allstr2.sort()

print(allstr2[N-1])

### FIXED CODE ###

strs = input()
N = int(input())

Len = len(strs)

allstr = [] 
flag = 0

for i in range(Len):
    tmp = list(range(i+1))
    tmp.reverse()
    for j in tmp:
#        print(strs[Len-i-1:Len-j])
        allstr.append(strs[Len-i-1:Len-j])
        allstr2 = list(set(allstr))
        if len(allstr2) > 5:
            if allstr[5:6] > allstr[4:5] and flag == 1:
#                print(allstr[5:6], allstr[4:5])
                allstr = allstr[0:5]
                break
            allstr2.sort()
            allstr = allstr2[0:5]
            flag = 1
#            print(allstr2)
        

allstr2 = list(set(allstr))        
allstr2.sort()

print(allstr2[N-1])
### BUGGY CODE ###

N = int(input())
L = []
cnt = 0
for _ in range(N):
    s = input()
    if not s in L:
        L.append(s)
        cnt += 1
print(cnt)

### FIXED CODE ###

from collections import deque
N = int(input())
D = deque()
for _ in range(N):
    D.append(input())
print(len(set(D)))
### BUGGY CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n,m = MAP()
a = MAP()
heapify(a)
for i in range(m):
    b,c = MAP()
    for j in range(b):
        tmp = heappop(a)
        if tmp<c:
            heappush(a,c)
        else:
            heappush(a,tmp)
            break
print(sum(a))

### FIXED CODE ###

import math
import collections
import itertools
import sys
import bisect
from heapq import heappop,heappush,heapify
sys.setrecursionlimit(10**6)
def MAP(): return list(map(int,input().split()))
def INT(): return int(input())
def FLOAT(): return float(input())
MOD = 10**9+7


n, m = MAP()
a = MAP()
p = [(a[i], 1) for i in range(n)]
for j in range(m):
    b, c = MAP()
    p.append((c, b))
p.sort(reverse=True)
ans, cnt = 0, n
for (v, c) in p:
    use = min(c, cnt)
    ans += use * v
    cnt -= use
print(ans)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(10000000)
def input():
    return sys.stdin.readline()[:-1]
from collections import *
import math
from bisect import *
import functools
INF = float('inf')
mod = 10**9+7

N = int(input())
A = [list(map(lambda x: int(x)-1, input().split())) for i in range(N)]
P = [0] * N
cnt, day = 0, 0
while 1:
    day += 1
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == N*(N-1)//2:
        print(day)
        break
    if flag == 0:
        print(-1)
        exit()


### FIXED CODE ###

import sys
def input():
    return sys.stdin.readline()[:-1]
import time

N = int(input())
A = [[int(x)-1 for x in input().split()] for i in range(N)]
P = [0] * N
cnt = 0
ALL = N*(N-1)//2
s = time.time()
for day in range(ALL):
    if time.time()-s > 1.6:
        print(N*(N-1)//2)
        break
    used = [0] * N
    flag = 0
    for i, p in enumerate(P):
        if p != N-1 and used[i] == 0:
            x = A[i][p]
            if x < N and used[x] == 0 and A[x][P[x]] == i:
                P[i] += 1
                P[x] += 1
                used[i] = 1
                used[x] = 1
                flag = 1
                cnt += 1
    if cnt == ALL:
        print(day+1)
        break
    if flag == 0:
        print(-1)
        break
### BUGGY CODE ###

n=int(input())
a=list(map(int, input().split()))
ans=1
for i in a:
    ans*=i
    #print(ans)
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n=int(input())
a=sorted(list(map(int, input().split())))
ans=1
f=True
for i in a:
    ans*=i
    if ans>10**18:
        f=False
        break
if f:
    print(ans)
else:
    print(-1)
### BUGGY CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0 for i in range(h)], [0 for i in range(w)]
bord = [[0 for _j in range(w)] for _i in range(h)]

for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    bord[s][t] = 1

x_max, y_max = max(bord_x), max(bord_y)
a = [x for x, p in enumerate(bord_x) if x_max==p]
b = [y for y, p in enumerate(bord_y) if y_max==p]

checker = 0
for i in a:
    for j in b:
        if bord[i][j]==0:
            import sys
            print(x_max+y_max)
            sys.exit()
        else:
            checker += 1
            if checker >= m:
                break

print(x_max+y_max-1)

### FIXED CODE ###

h, w, m = map(int, input().split())
bord_x, bord_y = [0]*h, [0]*w
 
hw = []
for _i in range(m):
    s, t = map(int, input().split())
    s -= 1
    t -= 1
    bord_x[s] += 1
    bord_y[t] += 1
    hw.append([s, t])
 
x_max, y_max = max(bord_x), max(bord_y)
 
cnt = 0
for i, j in hw:
    if bord_x[i] == x_max and bord_y[j] == y_max:
        cnt += 1
 
if cnt == bord_x.count(x_max)*bord_y.count(y_max):
    x_max -= 1
 
print(x_max+y_max)
### BUGGY CODE ###

t = input()
ques_num = t.count('?')
t = list(t)

# PDの2通りを計算する
ans = ""
score = 0
for bit in range(2**ques_num):
    tmp_t = list(t)
    tmp_ques_num = 0
    for i in range(len(t)):
        if tmp_t[i] != '?':
            continue
        if bit >> tmp_ques_num & 1:
            tmp_t[i] = 'P'
        else:
            tmp_t[i] = 'D'
        tmp_ques_num += 1
    if score < "".join(tmp_t).count('D') + "".join(tmp_t).count('PD'):
        score = "".join(tmp_t).count('D') + "".join(tmp_t).count('PD')
        ans = "".join(tmp_t)

print(ans)

### FIXED CODE ###

t = list(input())

for i in range(len(t)):
    if t[i] == '?':
        t[i] = 'D'
print("".join(t))