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

import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)

### FIXED CODE ###

import itertools
n,m,r=map(int,input().split());R=min(r,8)
d = [[10**12for i in range(n)]for j in range(n)]
l=list(map(int,input().split()))
for i in range(r):
  l[i]-=1
for i in range(m):
  a,b,c=map(int,input().split())
  d[a-1][b-1]=d[b-1][a-1] = c
for k in range(n):
  for i in range(n):
    for j in range(n):
      d[i][j]=min(d[i][j], d[i][k]+d[k][j])
#print(d)
ans=10**12
for v in itertools.permutations(l, R):
  cnt=0
  for i in range(1,R):
    cnt+=d[v[i-1]][v[i]]
  ans=min(ans,cnt)
print(ans)
### BUGGY CODE ###

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
cango=dict()
res=[0]
data=[0 for _ in range(1+n)]

def calc(k):
    return 1/2*k*(k-1)

def search(data,x):
    bef=x
    while data[x]>0:
        data[bef]=data[x]
        bef=x
        x=data[x]
    return x,data[x]

for i in range(m):
    a,b=branch.pop()
    aset={a,}
    bset={b,}
    aroot,aidx=search(data,a)
    broot,bidx=search(data,b)
    if aidx!=0:aset=cango[aidx]
    if bidx!=0:bset=cango[bidx]
    lena=len(aset)
    lenb=len(bset)
    if aidx==0 and bidx==0:
        data[a]=-1*a
        data[b]=a
        cango[-1*a]={a,b}
    elif aidx==bidx and aidx!=0:
        res.append(res[-1])
        continue
    elif aidx==0 and bidx!=0:
        cango[bidx]|={a,}
        data[a]=broot
    elif aidx!=0 and bidx==0:
        cango[aidx]|={b,}
        data[b]=aroot
    elif aidx!=0 and bidx!=0 and aidx!=bidx:
        cango.pop(bidx)
        cango[aidx]|=bset
        data[broot]=aroot
    res.append(res[-1]-calc(lena)-calc(lenb)+calc(lena+lenb))

for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))

### FIXED CODE ###

n,m=map(int,input().split())
branch=[tuple(map(int,input().split())) for _ in range(m)]
res=[0]
data=[-1 for _ in range(1+n)]
def calc(k):
    k=abs(k)
    return 1/2*k*(k-1)

def search(data,x):
    if data[x]<=0:
        return x
    else:
        data[x]=search(data,data[x])
    return data[x]

for i in range(m):
    a,b=branch.pop()
    aroot=search(data,a)
    broot=search(data,b)
    if aroot==broot:
        res.append(res[-1])
        continue
    res.append(res[-1]-calc(data[aroot])-calc(data[broot])+calc(data[aroot]+data[broot]))
    if data[aroot]<=data[broot]:
        data[aroot]+=data[broot]
        data[broot]=aroot
    elif data[aroot]>data[broot]:
        data[broot]+=data[aroot]
        data[aroot]=broot
for j in range(m-1,-1,-1):
    print(int(res[m]-res[j]))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
x+=d*k
m=abs(x)
for i in range(k):
  x-=d*2
  if abs(x)<m:
    m=abs(x)
  else:
    break
print(m)

### FIXED CODE ###

# -*- coding: utf-8 -*-
x,k,d=map(int,input().split())
m=abs(x)
n=m//d
j=k-n
if j>0:
  if x<0:
    if j%2==0:
      x+=d*n
    else:
      x+=d*(n+1)
  else:
    if j%2==0:
      x-=d*n
    else:
      x-=d*(n+1)
else:
  if x<0:
    x+=d*k
  else:
    x-=d*k
print(abs(x))
### BUGGY CODE ###

a=int(input())
b=[int(input()) for i in range(a)]
b.sort()
c=sum(b)
if c%10!=0:
  print(c)
else:
  while c%10==0:
    for k in range(a):
      c=c-b[k]
  print(c)

### FIXED CODE ###

a=int(input())
b=[int(input()) for i in range(a)]
b.sort()
c=sum(b)
d=0
if c%10!=0:
  print(c)
else:
  for i in range(a):
    if b[i]%10!=0:
      c=c-b[i]
      print(c)
      break
  if sum(b)==c:
    print(0)
### BUGGY CODE ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    for _ in range(n):
        q = input()
        d = d[::-1] if q[0] == ('1') else q[-1]+d if q[:3] == ("2 1") else d+q[-1]
    print(d)

### FIXED CODE ###

if __name__ == '__main__':
    d = input()
    n = int(input())
    qs = [input() for e in range(n)]
    s = []
    e = []
    r = False
    for q in qs:
        if q == '1':
            r = not(r)
        elif q.startswith("2 1"):
            e.append(q[-1]) if r else s.append(q[-1])
        else:
            s.append(q[-1]) if r else e.append(q[-1])
    print("".join(e[::-1]) + d[::-1] + "".join(s) if r else "".join(s[::-1]) + d + "".join(e))
### BUGGY CODE ###

N = int(input())
a = []
for i in range(N):
    A = int(input())
    a. append(A)
b = sorted(a)
for i in range(N):
    if max(a) == a[i]:
        print(b[N - 2])
    else:
        print(max(a))

### FIXED CODE ###

N = int(input())
a = []
ans = []
for i in range(N):
    A = int(input())
    a.append(A)

b = sorted(a)

m = max(a)
for i in a:
    if i == m:
        ans.append(b[-2])
    else:
        ans.append(m)

for i in ans:
    print(i)
### BUGGY CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)

for i in range(1,N+1):
  print(A.count(i))

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)

for i in range(1,N+1):
  print(count[i])
### BUGGY CODE ###

#!/usr/bin/env python3
def main():
    N, K = map(int, input().split())
    S = set()
    for _ in range(K):
        l, r = map(int, input().split())
        for n in range(l, r + 1):
            S.add(n)
    MOD = 998244353

    dp = [0] * N
    dp[0] = 1
    for i in range(N):
        for d in S:
            if i >= d:
                dp[i] += dp[i - d] % MOD
    print(dp[-1] % MOD)


if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
def main():
    import numpy as np

    N, K = map(int, input().split())
    section = [list(map(int, input().split())) for _ in range(K)]
    MOD = 998244353

    dp = np.zeros(N + 1, dtype=np.int64)
    dp[1] = 1
    cumsum = np.zeros(N + 1, dtype=np.int64)
    cumsum[1] = 1
    for i in range(2, N + 1):
        for left_section, right_section in section:
            left = max(i - right_section - 1, 0)
            right = i - left_section
            if right < 0:
                continue
            dp[i] += cumsum[right] - cumsum[left]
        cumsum[i] = cumsum[i - 1] + dp[i]
        dp[i] %= MOD
        cumsum[i] %= MOD
    print(dp[N] % MOD)
    # print(dp)
    # print(cumsum)


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

import math
 
k=int(input())
cnt=0
for a in range(k):
  a=a+1
  for b in range(k):
    b=b+1
    for c in range(k):
      c=c+1
      cnt=cnt+math.gcd(math.gcd(a,b),c)
print(cnt)
      

### FIXED CODE ###

import math
 
k=int(input())
cnt=0
tmp=[]
for a in range(k):
  a=a+1
  for b in range(k):
    b=b+1
    tmp.append(math.gcd(a,b))
for i in tmp:
  if i==1:
    cnt=cnt+k
  else:
    for j in range(k):
      j=j+1
      cnt=cnt+math.gcd(i,j)
print(cnt)
### BUGGY CODE ###

from math import sqrt

primes = [x for x in range(2, 1000000) if x % 2 == 1 or x == 2]
for i in range(2, int(sqrt(1000000))):
    primes = [x for x in primes if x % i != 0 or x == i]

while True:
    a, d, n = map(int, input().split())
    if a == 0: break

    nums = [x for x in primes if (x-a) % d == 0]
    print(nums[n-1])

### FIXED CODE ###

from math import sqrt
from array import array

size = 10000000
s = array('i', range(size+1))
s[1] = 0
sqrtn = int(round(size**0.5))
for i in range(2, sqrtn + 1):
    if s[i]:
        s[i*i: size+1 : i] = array('i', [0] * len(range(i*i, size+1, i)))
primes = list(filter(None, s))

while True:
    a, d, n = map(int, input().split())
    if a == 0: break

    ans = 0
    for p in primes:
        if p-a < 0 : continue
        if (p-a) % d == 0:
            ans = p
            n -= 1
        if n == 0:
            break
    print(ans)
### BUGGY CODE ###

import sys
import numpy as np
# input処理を高速化する
input = sys.stdin.readline

L=int(input())
div =0.001
V=0
for x in np.arange(div,L+1,div):
    z=L-2*x
    V=max(V,x*x*z)

print(V)


# for x in np.arange(1,10+1,0.1):
#     for y in np.arange(1,10+1-x,0.1):
#         print(x,y)

### FIXED CODE ###

import sys
import numpy as np
# input処理を高速化する
input = sys.stdin.readline

L=int(input())

#forループではない
# div =0.001
# ranges =np.arange(0.001,L+1,0.01)
# V=0
# for x in ranges:
#     z=L-2*x
#     V=max(V,x*x*z)

# print(V)
#相加相乗平均を用いる
print((L/3)**3)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(210000)

N = int(input())
A = [int(input()) for i in range(N)]
Ad = [0] *N

for i in range(N):
    tmp = A[i]
    A[i] = 0
    print(max(A))
    A[i] = tmp

### FIXED CODE ###

N = int(input())
A = [int(input()) for i in range(N)]
A_reverse = sorted(A)

for i in range(N):
    if A[i] == A_reverse[-1]:
        print(A_reverse[-2])
    else:
        print(A_reverse[-1])
### BUGGY CODE ###

import math
import collections

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

equal = 0
elements = collections.Counter(A)
for v in elements.values():
    equal += v * (v - 1) // 2

for i in range(n):
    A_tmp = A[: i] + A[i + 1: ]
    equal_i = A_tmp.count(A[i])
    print(equal - equal_i)


### FIXED CODE ###

import math
import collections

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

equal = 0
elements = collections.Counter(A)
equal = sum([v * (v - 1) // 2 for v in elements.values()])

for i in range(n):
    equal_i = elements[A[i]] - 1
    print(equal - equal_i)
### BUGGY CODE ###

from itertools import permutations
import heapq

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))

cost = {}
for i in range(m):
    a, b, c = list(map(int, input().split()))
    if not a in cost.keys():
        cost[a] = [(b, c)]
    else:
        cost[a].append((b, c))
    if not b in cost.keys():
        cost[b] = [(a, c)]
    else:
        cost[b].append((a, c))
        
dist = [[INF]*(n+1) for _ in range(n+1)]
for st in range(1, n+1):
    d = [INF]*(n+1)
    d[st] = 0
    path = [(0, st)]
    heapq.heapify(path)
    while len(path) > 0:
        c, node = heapq.heappop(path)
        if d[node] < c:
            continue
        d[node] = c
        for node_next, c_next in cost[node]:
            if d[node]+c_next < d[node_next]:
                heapq.heappush(path, (d[node]+c_next, node_next))
    dist[st] = d
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(ans)


### FIXED CODE ###

from itertools import permutations

INF = float('inf')
n, m, R = list(map(int, input().split()))
r = list(map(int, input().split()))
dist = [[INF]*(n+1) for _ in range(n+1)]
for i in range(1, n+1):
    dist[i][i] = 0
for i in range(m):
    a, b, c = map(int, input().split())
    dist[a][b] = c
    dist[b][a] = c

from scipy.sparse import csgraph
dist = csgraph.floyd_warshall(dist)
# for k in range(n):
#     for i in range(n):
#         for j in range(n):
#             dist[i][j] = min(dist[i][j], dist[i][k]+dist[k][j])
# for d in dist: print(d)

ans = INF
for p in permutations(r):
    ans_ = 0
    for i in range(R-1):
        ans_ += dist[p[i]][p[i+1]]
    ans = min(ans, ans_)
print(int(ans))
### BUGGY CODE ###

S = input()
counter = 0
while True:
    tmp = S.replace("BW", "WB", 1)
    if S == tmp:
        break
    S = tmp
    counter += 1

print(counter)

### FIXED CODE ###

S = input()

count = 0
for i in range(len(S)):
    if S[i] == 'W':
        continue
    else:
        break
S = S[i:]

count = 0
score = 0
for i in range(len(S)):
    if S[i] == 'W':
        score += (i - count)
        count += 1
print(score)
### BUGGY CODE ###

n = int(input())
s = list(map(int, input().split(" ")))

c = [0] * (n+1)
j = 0
if 1 not in s:
    print(-1)
elif len(s) == 1:
    print(0)
else:
    for i in range(1,n+1):
        if i in s:
            c[i] = s.index(i)
            del s[j:c[i]]
            j += 1
            #print(s)
        elif i not in s:
            break
    print(n - j)

### FIXED CODE ###

n = int(input())
s = list(map(int, input().split(" ")))

c = []
j = 0
if 1 not in s:
    print(-1)
elif len(s) == 1:
    print(0)
else:
    for i in s:
        if i - j == 1:
            j = i
            c.append(i)
    print(n - len(c))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys
import collections

def solve(N: int, s: "List[str]"):
    answer = 0
    for i in range(N):
        for j in range(i+1,N):
            # print(collections.Counter(s[i]))
            if collections.Counter(s[i]) == collections.Counter(s[j]):
                answer += 1
    print(answer)
    return


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
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import collections
from itertools import groupby

def solve(N: int, s: "List[str]"):
    s = [sorted(s[i]) for i in range(N)]
    s.sort()
    group = groupby(s)
    answer = 0
    for key, group in group:
        a = len(list(group))
        answer += int(a*(a-1)/2) if a > 1 else 0
    print(answer)
   


    # for i in range(N):
    #     a = 1
    #     pop_index = []
    #     for j in range(i+1,len(ss)):
    #         if ss[i] == ss[j]:
    #             a += 1
    #             pop_index.append(j)
        
    #     ss = [ss[i] for i in range(len(ss)) if i not in pop_index]
    #     answer += int(a*(a-1)/2) if a > 1 else 0
    return


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
    s = [next(tokens) for _ in range(N)]  # type: "List[str]"
    solve(N, s)

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

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

MOD = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD

print(dp[N][S])


### FIXED CODE ###

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

MOD = 998244353

dp = [[0] * (S + 1) for _ in range(N + 1)]
dp[0][0] = 1

for i in range(N):
    for j in range(S + 1):
        dp[i + 1][j] += 2 * dp[i][j]
        dp[i + 1][j] %= MOD
        if j + A[i] <= S:
            dp[i + 1][j + A[i]] += dp[i][j]
            dp[i + 1][j + A[i]] %= MOD

print(dp[N][S])
### BUGGY CODE ###

n = int(input())
s = []

# for i in range(n):
#     s.append(input())

buf = []
cnt = []

for i in range(n):
    buf2 = input()
    if buf2 not in buf:
        buf.append(buf2)
        cnt.append(0)
    cnt[buf.index(buf2)] += 1

# for i in s:
#     if i not in buf:
#         buf.append(i)
#         cnt.append(0)
#     cnt[buf.index(i)] += 1

ans = [i for i, x in enumerate(cnt) if x == max(cnt)]

ans2 = [buf[i] for i in range(len(buf)) if i in ans]

ans3 = sorted(ans2)

for i in ans3:
    print(i)

### FIXED CODE ###

n = int(input())
s = []

for i in range(n):
    s.append(input())

word_buf = {}

for i in s:
    if i in word_buf.keys():
        word_buf[i] += 1
    else:
        word_buf[i] = 1

max_cnt = max(word_buf.values())
max_word = [i[0] for i in word_buf.items() if i[1] == max_cnt]
max_word.sort()

for i in max_word:
    print(i)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
ac = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    ac.append((a, c))

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, ci) in enumerate(ac, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])


### FIXED CODE ###

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
abc = []
for i in range(m):
    a, b = map(int, input().split())
    tmpc = map(int, input().split())
    c = sum(1 << (ci - 1) for ci in tmpc)
    abc.append([a,b,c])

# 解説AC
dp = [[0] + [pow(10, 9)] * (pow(2, n) - 1)]
for i, (ai, _, ci) in enumerate(abc, 1):
    dp.append(dp[-1][:])
    for j in range(pow(2, n)):
        tmp = min(dp[i - 1][j | ci], dp[i - 1][j] + ai)
        dp[i][j | ci] = min(tmp, dp[i][j | ci])
print(-1 if dp[-1][-1] == pow(10, 9) else dp[-1][-1])
### BUGGY CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range( (N - r * R)//G + 1):
        if r * R + g * G < N and (N - r * R - g * G) % B == 0:
            ans += 1
        if r * R + g * G == N:
            ans += 1

print(ans)

### FIXED CODE ###

R, G, B, N = map(int, input().split())

ans = 0
for r in range(N//R + 1):
    for g in range( (N - r * R)//G + 1):
        if (N - r * R - g * G) % B == 0:
            ans += 1

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

def main():
    n, m, q = map(int, input().split())
    trains = [list(map(int, input().split())) for _ in range(m)]
    for _ in range(q):
        p, q = map(int, input().split())
        print(len(list(filter(lambda x: p <= x[0] and x[1] <= q, trains))))


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m, q = map(int, input().split())
    trains = [[0 for _ in range(n + 1)] for _ in range(n + 1)]
    for _ in range(m):
        l, r = map(int, input().split())
        trains[l][r] += 1
    for i in range(n + 1):
        for j in range(1, n + 1):
            trains[i][j] += trains[i][j - 1]
    for _ in range(q):
        p, q = map(int, input().split())
        ans = 0
        for i in range(p, q + 1):
            ans += trains[i][q] - trains[i][p - 1]
        print(ans)


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

n,q=map(int,input().split())
s=input()

for i in range(q):
    l,r=map(int,input().split())
    ss=s[l-1:r]
    m=0
    for j in range(r-l+1):
        if j==r-l:
            continue
        else:
            if ss[j]=="A" and ss[j+1]=="C":
                m+=1
    print(m)


### FIXED CODE ###

n,q=map(int,input().split())
s=input()
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=map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
for i in range(N):
  R[i+1]=R[i]+A[i]
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[:10],)
#print(R.count(4))

ans=0
for a in list(set(R[1:])):
  b=R.count(a)
  if b>=2:
    ans+=cmbn2(b)
print(ans)
  

### FIXED CODE ###

def cmbn2(n):
  #n>=2
  return int(n*(n-1)/2)

N=int(input())
A=list(map(int, input().split()))
R=[0]*(N+1)
D={0:1}
for i in range(N):
  R[i+1]=R[i]+A[i]
  if R[i+1] not in D.keys():
    D[R[i+1]]=1
  else:
    D[R[i+1]]+=1
  
#m=len(set(R[1:]))
#print((N-m)*m)
#print(R[1:10],)
#print(R.count(4))

ans=0
for b in D.values():
  
  if b>=2:
    ans+=cmbn2(b)
print(ans)
#print(D.values())
### BUGGY CODE ###

import numpy as np
n=int(input())
s=list(input())
r=0
for ii in np.arange(1,n+1):
  for jj in np.arange(ii+1,n+1):
    for kk in np.arange(jj+1,n+1):
      #print(ii,jj,kk)
      if jj-ii!=kk-jj:
        if s[ii-1]!=s[jj-1] and s[jj-1]!=s[kk-1] and s[ii-1]!=s[kk-1]:
          r+=1
print(r)
    

### FIXED CODE ###

import numpy as np
n=int(input())
s=list(input())
sr=set()
sg=set()
sb=set()
for ii in range(n):
    if s[ii]=="R":
        sr.add(ii)
    if s[ii]=="G":
        sg.add(ii)
    if s[ii]=="B":
        sb.add(ii)
l=[len(sr),len(sg),len(sb)]
l.sort()

if l[0]==len(sr):
  s1=sr
  if l[1]==len(sg):
    s2=sg
    s3=sb
  else:
    s2=sb
    s3=sg
elif l[0]==len(sg):
  s1=sg
  if l[1]==len(sr):
    s2=sr
    s3=sb
  else:
    s2=sb
    s3=sr
else:
  s1=sb
  if l[1]==len(sr):
    s2=sr
    s3=sg
  else:
    s2=sg
    s3=sr
  
r=0
for ii in s1:
  for jj in s2:
    r+=len(s3)
    dt=abs(ii-jj)
    if ii+dt in s3:
      r-=1
    if ii-dt in s3:
      r-=1
    if jj+dt in s3:
      r-=1
    if jj-dt in s3:
      r-=1
    if (ii+jj)%2==0:
      if (ii+jj)//2 in s3:
        r-=1
      
print(r)
### BUGGY CODE ###

H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[False if i != C[0] or j != C[1] else True for j in range(W)] for i in range(H)]
queue = [C]
ans = 0
 
while True:
    tmp = queue.pop()
    dfs = [tmp]
 
    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue
 
            if not toGo[hh][ww] and S[hh][ww] == '.':
                toGo[hh][ww] = True
                dfs.append([hh, ww])
 
    if toGo[D[0]][D[1]]:
        break
 
    flag = True
    if not len(queue):
        ttogo = [[toGo[i][j] for j in range(W)] for i in range(H)]
        ans += 1
        for i in range(H):
            for j in range(W):
                if not toGo[i][j] and S[i][j] == ".":
                    t = False
                    for ii in range(-2, 3):
                        for jj in range(-2, 3):
                            hh, ww = i + ii, j + jj
                            if hh >= H or hh < 0 or ww >= W or ww < 0:
                                continue
 
                            if toGo[hh][ww]:
                                ttogo[i][j] = True
                                flag, t = False, True
                                queue.append([i, j])
                                break
                        if t:
                            break
        toGo = ttogo
        if flag:
            print(-1)
            exit()
 
print(ans)

### FIXED CODE ###

H, W = map(int, input().split())
C = list(map(lambda x: int(x) - 1, input().split()))
D = list(map(lambda x: int(x) - 1, input().split()))
S = [input() for _ in range(H)]
toGo = [[False if i != C[0] or j != C[1] else True for j in range(W)] for i in range(H)]
queue, mahou = [C], [C]
ans = 0

while True:
    tmp = queue.pop()
    mahou.append(tmp)
    dfs = [tmp]

    while len(dfs):
        a = dfs.pop()
        for move in [[0, 1], [0, -1], [1, 0], [-1, 0]]:
            hh, ww = a[0] + move[0], a[1] + move[1]
            if hh >= H or hh < 0 or ww >= W or ww < 0:
                continue

            if not toGo[hh][ww] and S[hh][ww] == '.':
                toGo[hh][ww] = True
                dfs.append([hh, ww])
                mahou.append([hh, ww])

    if toGo[D[0]][D[1]]:
        break

    flag = True
    if not len(queue):
        ans += 1
        for k in mahou:
            for i in range(-2, 3):
                for j in range(-2, 3):
                    h, w = i + k[0], j + k[1]
                    if h >= H or h < 0 or w >= W or w < 0:
                        continue

                    if not toGo[h][w] and S[h][w] == '.':
                        flag = False
                        toGo[h][w] = True
                        queue.append([h, w])
        mahou = []

        if flag:
            print(-1)
            exit()

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

import sys

def replace(Str):
    Len = len(Str)
    for Num in range(Len):
        if(Str[Num]== "?"):
            Str = Str[:Num] + 'D' + Str[Num+1:]
    return Str

if(__name__ == "__main__"):
    Str = input()

    Stred = replace(Str)
    print(Stred)


### FIXED CODE ###

import sys



if(__name__ == "__main__"):
    Str = input()

    Stred = Str.replace('?', 'D')
    print(Stred)