Harryxun/stf_run huggingface dataset:
from collections import deque, defaultdict
from heapq import heappop, heappush

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = 10 ** 10
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

def BST(now, heap, dist):
    if(len(edge[now]) == 0):
        return
    for node in edge[now]:
        if(dist[node] > dist[now] + 1):
            dist[node] = dist[now] + 1
            heappush(heap, node)
    if(heap):
        next_node = heappop(heap)
        BST(next_node, heap, dist)
    else:
        return

heap = []
BST((S, 0), [], dist)

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)


### FIXED CODE ###

from collections import deque, defaultdict

N, M = map(int, input().split())
edge = defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    edge[(a, 0)].append((b, 1))
    edge[(a, 1)].append((b, 2))
    edge[(a, 2)].append((b, 0))

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

inf = float('inf')
dist = {}
for i in range(1, N+1):
    dist[(i, 0)] = inf
    dist[(i, 1)] = inf
    dist[(i, 2)] = inf
dist[(S, 0)] = 0

dq = deque()
dq.append((S, 0))

while dq:
    v = dq.popleft()
    if v == (T, 0):
        break
    for u in edge[v]:
        if dist[u] < inf: continue
        dq.append(u)
        dist[u] = dist[v] + 1

if(dist[(T, 0)] == inf):
    print(-1)
else:
    print(dist[(T, 0)]//3)
#coding:UTF-8
#
#問題：AtCoder Grand Contest019 #A Ice Tea Store
#
#手法：入力Nは整数で与えられるので、Nが2以上のときは2リットル当たりの値段が安いドリンクをN/2個買い、
#Nが奇数だったら、残りの1リットルは1リットル当たりの値段が安いドリンク買う
sum=0#合計金額
#入力(0.25リットル,0.5リットル,1リットル,2リットル)
Q,H,S,D=input().split()
Q=int(Q)
H=int(H)
S=int(S)
D=int(D)
#入力チェック
if not(1<=Q<=10**8 and 1<=H<=10**8 and 1<=S<=10**8 and 1<=D<=10**8):
	print("input error1")
#1リットル当たりのQ,Hの値段QQ,HHを求める
QQ=Q*4
HH=H*2
#2リットル当たりのQ,H,Sの値段QQQ,HHH,SSSを求める
QQQ=8*Q
HHH=4*H
SSS=2*S
N=int(input())
#Nの入力チェック]
if not(1<=N<=10**9):
	print("input error2")
#N=1のとき、QQ,HH,Sの最小値がsumになる
if N==1:
	sum=min(QQ,HH,S)
else:#Nが2以上の時
	sum+=(N//2)*min(QQQ,HHH,SSS,D)
	if N%2==1:#Nが奇数のときは、sumにQQ,HH,Sの中の最小値を加える
		sum+=min(QQ,HH,S)
print()	
print(sum)
#print("Q,H,S,D=",Q,H,S,D)


### FIXED CODE ###

sum=0
Q,H,S,D=input().split()
Q=int(Q)
H=int(H)
S=int(S)
D=int(D)

if not(1<=Q<=10**8 and 1<=H<=10**8 and 1<=S<=10**8 and 1<=D<=10**8):
	print("input error1")

QQ=Q*4
HH=H*2

QQQ=8*Q
HHH=4*H
SSS=2*S
N=int(input())

if not(1<=N<=10**9):
	print("input error2")

if N==1:
	sum=min(QQ,HH,S)
else:
	sum+=(N//2)*min(QQQ,HHH,SSS,D)
	if N%2==1:
		sum+=min(QQ,HH,S)

print(sum)
seq = map(int,raw_input().split())

print "バブルソート実行"
for i in range(len(seq)):
    for j in range(i,len(seq)-1):
        if seq[i] > seq[j+1]:
            a = seq[j+1]
            seq[j+1] = seq[i]
            seq[i] = a
        print i,j+1,seq

### FIXED CODE ###

seq = map(int,raw_input().split())

for i in range(len(seq)):
    for j in range(i,len(seq)-1):
        if seq[i] > seq[j+1]:
            a = seq[j+1]
            seq[j+1] = seq[i]
            seq[i] = a
        
print seq[0],seq[1],seq[2]
class MyClass():
    maxNumber = 0

    def roop(self, baseList, opeCount):
        listCount = len(baseList)
        roopMax = listCount if listCount < opeCount else opeCount
        for leftCount in range(1, roopMax):
            for rightCount in range(0, roopMax - leftCount -1):
                leftList = baseList[0: leftCount]
                rightList = baseList[listCount - 1 - rightCount : listCount]
                handList = leftList + rightList

                self.getMax(handList, opeCount - leftCount)

                

    def getMax(self, handList, remainOpeCount):
        if len(handList) < 1:
            return

        maxVal = 0
        removeCount = 0

        handList.sort()
        for each in handList:
            if each < 0 and remainOpeCount > 0:
                removeCount += 1
                remainOpeCount -= 1
        
        maxVal = max(handList[removeCount:])
        self.maxNumber = max([maxVal, self.maxNumber])


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

my = MyClass()
my.roop(baseList, opeCount)
print(my.maxNumber)







### FIXED CODE ###

class MyClass():
    maxNumber = 0

    def roop(self, baseList, opeCount):
        listCount = len(baseList)
        roopMax = listCount if listCount < opeCount else opeCount
        for leftCount in range(0, roopMax):
            self.getMax(baseList[0: leftCount + 1], opeCount - leftCount - 1)

            for rightCount in range(1, roopMax - leftCount + 1):
                leftList = baseList[0: leftCount]
                rightList = baseList[listCount - rightCount : listCount]
                handList = leftList + rightList

                self.getMax(handList, opeCount - leftCount - rightCount)

                

    def getMax(self, handList, remainOpeCount):
        if len(handList) < 1:
            return

        maxVal = 0
        removeCount = 0

        if remainOpeCount > 0:
            handList.sort()
            for each in handList:
                if each < 0:
                    removeCount += 1
                    remainOpeCount -= 1
                    if remainOpeCount < 1:
                        break
        
        maxVal = sum(handList[removeCount:])
        self.maxNumber = max([maxVal, self.maxNumber])


count, opeCount = map(int, input().split())
baseList = list(map(int, input().split()))

my = MyClass()
my.roop(baseList, opeCount)
print(my.maxNumber)
N = int(input())
A = list(map(int, input.split()))
B = list(map(int, input.split()))
C = list(map(int, input.split()))

sat = sum(B)
for i in range(N-1):
  if A[i] + 1 == A[i+1]:
    sat += C[i]
    
print(sat)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
B = list(map(int, input().split()))
C = list(map(int, input().split()))
 
sat = sum(B)
pre_a = A[0]
for a in A[1:]:
  if a == pre_a + 1:
    sat += C[pre_a-1]
  pre_a = a
  
print(sat)
S = int(input())
W = int(input())
if (S > W):
  print("safe")
else:
  print("unsafe")

### FIXED CODE ###

SW = list(map(int,input().split()))
if (SW[0] > SW[1]):
  print("safe")
else:
  print("unsafe")
import math
A,B,C,X,Y = list(map(int,input().split()))
max_pizza=max(X,Y)#AピザとBピザのうち、必要な枚数の多い方のピザの枚数
ans=math.inf    

for i in range(0,max_pizza*2,2):#ABピザをi枚買う(iは偶数)
    
    if (X-i/2)<=0 and (Y-i/2)>0:
        ans_kouho = B*(Y-i/2)+C*(i)
    elif (X-i/2)>0 and(Y-i/2)<=0:
        ans_kouho = A*(X-i/2)+C*(i)
    elif (X-i/2)<=0 and(Y-i/2)<=0:
         ans_kouho = C*(i)
    else:
        ans_kouho = A*(X-i/2)+B*(Y-i/2)+C*(i)

    
    if(ans_kouho<ans):
        ans = ans_kouho

print(int(ans))



### FIXED CODE ###


A,B,C,X,Y = list(map(int,input().split()))
max_pizza=max(X,Y)#AピザとBピザのうち、必要な枚数の多い方のピザの枚数
ans=10E+10  

for i in range(0,max_pizza*2+2,2):#ABピザをi枚買う(iは偶数)
    
    if (X-i/2)<=0 and (Y-i/2)>0:
        ans_kouho = B*(Y-i/2)+C*(i)
    elif (X-i/2)>0 and(Y-i/2)<=0:
        ans_kouho = A*(X-i/2)+C*(i)
    elif (X-i/2)<=0 and(Y-i/2)<=0:
         ans_kouho = C*(i)
    else:
        ans_kouho = A*(X-i/2)+B*(Y-i/2)+C*(i)

    
    if(ans_kouho<ans):
        ans = ans_kouho

print(int(ans))
import numpy as np

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

xlim = a*b/2*a
if x<xlim:
    theta = np.arctan(a*b*b/2/x)/np.pi*180
else:
    theta = np.arctan(2*(a*a*b-x)/a**3)/np.pi*180

print(theta)


### FIXED CODE ###

import numpy as np

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

xlim = a*b/2*a
if x<xlim:
    theta = np.arctan(a*b*b/2/x)/np.pi*180
else:
    theta = np.arctan(2*(a*a*b-x)/a**3)/np.pi*180

print(theta)
n = int(input())
a = list(map(int,input().split))
a.sort(reverse=True)
ans = 0
for i in range(N):
  if(i%2==0):
    ans+=a[i]
  else:
    ans+=a[i]
print(ans)

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
ans = 0
for i in range(N):
  if(i%2==0):
    ans += a[i]
  else:
    ans-=a[i]
print(ans)
s = list(input())

k1 = 0
k2 = 0
zure = 0

for i in range(len(s)-1):

    if i + zure >= len(s) - 2:
        if s[i + zure] != s[i + 1 + zure]:
            #print(s[i+zure])
            k1 += 1
        k1 += 1
        break

    if s[i + zure] == s[i+1+zure]:
        #print(s[i+zure])
        #print(s[i+1+zure]+s[i+2+zure])
        k1 += 1
        zure += 2
    else:
        #print(s[i+zure])

    k1 += 1
    if i + zure >= len(s)-1:
        if i + zure == len(s)-1:
            k1 += 1
        break

print(k1)


### FIXED CODE ###

s = list(input())

g = []

g.append(0)
g.append(1)
if len(s) > 1:
    if s[0] == s[1]:
        g.append(1)
    else:
        g.append(2)

    for i in range(3,len(s)+1):
        if s[i-1] != s[i-2]:
            g.append(g[i-1]+1)
        else:
            g.append(g[i-3]+2)

print(g[len(s)])
import sys

n = int(raw_input())


#class of node
class Node:
    def __init__(self):
        self.p = -1
        self.l = -1
        self.r = -1

T = [ Node() for _ in xrange(n)] #info of u
D = [0] * n #depth of u

def printInfo(u):
    #print 'node', u, ':',
    #print 'parent = ', T[u].p, ',',
    #print 'depth = ', D[u], ',',
    print "node {}: parent = {}, depth = {},".format(u, T[u].p, D[u]) ,
    if T[u].p == -1: 
        print 'root, ',
    elif T[u].l == -1:
        print 'leaf, ',
    else:
        print 'internal node, ',

    #print '[',
    sys.stdout.write("[")

    c = T[u].l
    i = 0
    while c != -1:
        if i > 0:
            print ', ',
        sys.stdout.write(str(c))
        #print "{}".format(c),
        c = T[c].r
        i += 1
    #print ']'
    sys.stdout.write("]\n")

    return 0

def rec(u, p):
    D[u] = p
    if T[u].r != -1:
        rec(T[u].r, p)
    if T[u].l != -1:
        rec(T[u].l, p+1)
    return

def main():
    for i in xrange(n):
        a = map(int, raw_input().split())
        v = a[0]
        d = a[1]
        for j in xrange(d):
            if j == 0:
                T[v].l = a[j+2]
            else:
                T[l].r = a[j+2]
            l = a[j+2]
            T[a[j+2]].p = v
    for i in xrange(n):
        if T[i].p == -1:
            r = i

    rec(r, 0)

    for i in xrange(n):
        printInfo(i)

    return 0

main()

### FIXED CODE ###

#!/usr/bin/env python
from __future__ import division, print_function
from sys import stdin
 
FORMAT = ('node {0.id}: parent = {0.parent}, depth = {0.depth},'
          ' {0.kind}, {0.childs}').format
 
 
class Node(object):
    def __init__(self, node):
        self.depth = 0
        self.parent = -1
        self.id = node[0]
        self.degree = node[1]
        self.kind = 'internal node' if node[1] else 'leaf'
        self.childs = node[2:]
 
    def __str__(self):
        return FORMAT(self)
 
 
def calc_depth(tree, i):
    for j in tree[i].childs:
        tree[j].depth += 1
        calc_depth(tree, j)
 
 
n = int(stdin.readline())
tree = [-1] * n
#assert 1 <= n <= 100000
for _ in xrange(n):
    node = Node([int(s) for s in stdin.readline().split()])
    i = node.id
    node.parent = tree[i]
    for j in node.childs:
        if isinstance(tree[j], int):
            tree[j] = i
        else:
            tree[j].parent = i
    tree[i] = node
 
for i in xrange(n):
    calc_depth(tree, i)
 
for i, node in enumerate(tree):
    if node.parent == -1:
        node.kind = 'root'
    print(node)
import numpy as np
N = int(input())

word_list = []
for i in range(N):
    S = list(input())
    words, count = np.unique(S, return_counts=True)
    word_list.append(''.join(words)+str(count))

S, ans_count = np.unique(word_list, return_counts=True)
temp = ans_count[ans_count>1]
ans = int(sum([t*(t-1)/2 for t in temp]))
print(ans)

### FIXED CODE ###

import collections

N = int(input())

word_list = []
for i in range(N):
    S = list(input())
    c = collections.Counter(sorted(S))
    count = c.values()
    words = c.keys()
    word_list.append(''.join(words)+str(count))

ans_dict = collections.Counter(word_list)
ans_count = list(ans_dict.values())
temp = [i for i in ans_count if i>1]
ans = int(sum([t*(t-1)/2 for t in temp]))
print(ans)
#!/usr/bin
# -*- coding="utf-8" -*-

c1 = []
c2 = []
q = input().split()
for i in range(int(q[1])):
  n = input()
for j in range(n):
  m = j.split()
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])

if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("INPOSSIBLE")

### FIXED CODE ###

#!/usr/bin
# -*- coding="utf-8" -*-
c1 = []
c2 = []
q = input().split()
n = [input().split() for i in range(int(q[1]))]
 
for m in n:
  if m[0] == "1":
    c1.append(m[1])
  if m[1] == q[0]:
    c2.append(m[0])
if set(c1) & set(c2):
  print("POSSIBLE")
else:
  print("IMPOSSIBLE")
def solve():
  K = int(input())
  N = int(input())
  vals = [None] * N
  ans = 99999999
  for i in range(N):
    vals[i] = int(input())
  for i in range(N):
    cc = -1
    if i == 0:
      cc = vals[N-1] - vals[0]
    else:
      cc = vals[i-1] + K - vals[i]
    ans = min(ans, cc)
  print(ans)
solve()
  


### FIXED CODE ###

def solve():
  raw = input().split()
  K = int(raw[0])
  N = int(raw[1])
  vals = [None] * N
  ans = 99999999
  raw = input().split()
  for i in range(N):
    vals[i] = int(raw[i])
  for i in range(N):
    cc = -1
    if i == 0:
      cc = vals[N-1] - vals[0]
    else:
      cc = vals[i-1] + K - vals[i]
    ans = min(ans, cc)
  print(ans)
solve()
N = int(input())
A = list(map(int, input(), split()))
ans = 0
while all(a % 2 == 0 for a in A):
    A = [a / 2 for ain A]
    ans += 1
print(ans)


### FIXED CODE ###

input()
A=list(map(int,input().split()))
ans=0
while all(a%2==0 for a in A):
    A=[a/2 for a in A]
    ans+=1
print(ans)
x,y,a,b,c = map(int, input().split())

s_a = [int(i) for i in list(input().split())]
s_b = [int(i) for i in list(input().split())]
s_c = [int(i) for i in list(input().split())]

s_a.sort(reverse = True)
s_b.sort(reverse = True)
s_c.sort(reverse = True)

ans = 0
x_a = s_a[0:x]
x_b = s_b[0:y]

x_a.reverse()
x_b.reverse()

s = 0
v = 0
t = 0
while s <= x and v <= y and t <= c:
    if x_a[s] <= x_b[v]:
        #print('B')
        if x_a[s] < s_c[t]:
            x_a[s] = s_c[t]
            s += 1
            t += 1
        else:
            break
    else:
        #print('A')
        if x_b[v] < s_c[t]:
            x_b[v] = s_c[t]
            v += 1
            t += 1
        else:
            break

ans = sum(x_a) + sum(x_b)
print(ans)

### FIXED CODE ###

x,y,a,b,c = map(int, input().split())

s_a = [int(i) for i in list(input().split())]
s_b = [int(i) for i in list(input().split())]
s_c = [int(i) for i in list(input().split())]

s_a.sort(reverse = True)
s_b.sort(reverse = True)
s_c.sort(reverse = True)

x_a = s_a[0:x]
x_b = s_b[0:y]


sum_a = x_a + x_b + s_c
sum_a.sort(reverse = True)
sum_a = sum_a[0:x+y]
print(sum(sum_a))
def koch(n, a_x, a_y, b_x, b_y):
  if n == 0:
    return

  th = math.pi*60.0/180.0

  s_x = (2.0*a_x + 1.0*b_x)/3.0
  s_y = (2.0*a_x + 1.0*b_x)/3.0
  t_x = (1.0*a_x + 2.0*b_x)/3.0
  t_y = (1.0*a_x + 2.0*b_x)/3.0
  u_x = (t_x - s_x)*math.cos(th) + (t_y - s_y)*math.sin(th) + s_x
  u_y = (t_x - s_x)*math.sin(th) + (t_y - s_y)*math.cos(th) + s_y

  koch(n-1, a_x, a_y, s_x, s_y)
  print '%.8f %8.f' % (s_x, s_y)
  koch(n-1, s_x, s_y, u_x, u_y)
  print '%.8f %8.f' % (u_x, u_y)
  koch(n-1, u_x, u_y, t_x, t_y)
  print '%.8f %8.f' % (t_x, t_y)
  koch(n-1, t_x, t_y, b_x, b_y)


import math
n = input()
a_x = 0.0
a_y = 0.0
b_x = 100.0
b_y = 0.0

print '%.8f %8.f' % (a_x, a_y)
koch(n-1, a_x, a_y, b_x, b_y)
print '%.8f %8.f' % (b_x, b_y)

### FIXED CODE ###

def koch(n, a_x, a_y, b_x, b_y):
  if n == 0:
    return
 
  th = math.pi*60.0/180.0
 
  s_x = (2.0*a_x + 1.0*b_x)/3.0
  s_y = (2.0*a_y + 1.0*b_y)/3.0
  t_x = (1.0*a_x + 2.0*b_x)/3.0
  t_y = (1.0*a_y + 2.0*b_y)/3.0
  u_x = (t_x - s_x)*math.cos(th) - (t_y - s_y)*math.sin(th) + s_x
  u_y = (t_x - s_x)*math.sin(th) + (t_y - s_y)*math.cos(th) + s_y
 
  koch(n-1, a_x, a_y, s_x, s_y)
  print '%.8f %.8f' % (s_x, s_y)
  koch(n-1, s_x, s_y, u_x, u_y)
  print '%.8f %.8f' % (u_x, u_y)
  koch(n-1, u_x, u_y, t_x, t_y)
  print '%.8f %.8f' % (t_x, t_y)
  koch(n-1, t_x, t_y, b_x, b_y)
 
 

import math
n = input()
a_x = 0.0
a_y = 0.0
b_x = 100.0
b_y = 0.0
 
print '%.8f %.8f' % (a_x, a_y)
koch(n, a_x, a_y, b_x, b_y)
print '%.8f %.8f' % (b_x, b_y)
def main():
  N = int(input())
  monsters = list(map(int, input().split()))

  monsters = sorted(monsters)
  # print(monsters)

  last = 10000
  while True:
    # print('==============================')
    # print(monsters)
    for i in range(1, len(monsters)):
      monsters[i] = monsters[i] % monsters[0]

    # print(monsters)
    if 0 in monsters:
      monsters.remove(0)
      monsters = sorted(monsters)

    # print(monsters)
    if len(monsters) == 2:
      last = int(abs(monsters[1] - monsters[0]))
      monsters.remove(monsters[1])

    if len(monsters) == 1:
      break
  print(last)

  

main()


### FIXED CODE ###

from fractions import gcd
import numpy as np

N = int(input())
A = np.array([int(i) for i in input().split()])

a = A[0]
for b in A[1:]:
  # print(a)
  a = gcd(a, b)

print(a)
n=int(input())
if n==1:
    print("Hello World")
elif n==2:
    a,b=map(int,input().split())
    print(a+b)

### FIXED CODE ###

if(int(input())==1):
    print("Hello World")
else:
    a=int(input())
    b=int(input())
    print(a+b)
x, y = [int(s) for s in input().split()]

a, a_mod = divmod(2 * y - x, 3)
b, b_mod = divmod(2 * x - y, 3)
if a_mod != 0 or b_mod != 0:
    print(0)
    exit()

mod = 10 ** 9 + 7

n = a + b
temp_list = [1] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = i * temp_list[i - 1] % mod

stop = a if a < b else b
i_temp_list = [1] * (n + 1)
i_temp_list[-1] = pow(temp_list[-1], mod - 2, mod)
for i in range(n, stop, -1):
    i_temp_list[i - 1] = i_temp_list[i] * i % mod

ans = temp_list[n] * i_temp_list[a] * i_temp_list[b] % mod
print(ans)

### FIXED CODE ###

x, y = [int(s) for s in input().split()]

a, a_mod = divmod(2 * y - x, 3)
b, b_mod = divmod(2 * x - y, 3)
if a < 0 or a_mod != 0 or b < 0 or b_mod != 0:
    print(0)
    exit()

mod = 10 ** 9 + 7

n = a + b
temp_list = [1] * (n + 1)
for i in range(1, n + 1):
    temp_list[i] = i * temp_list[i - 1] % mod

stop = a if a < b else b
i_temp_list = [1] * (n + 1)
i_temp_list[-1] = pow(temp_list[-1], mod - 2, mod)
for i in range(n, stop, -1):
    i_temp_list[i - 1] = i_temp_list[i] * i % mod

ans = temp_list[n] * i_temp_list[a] * i_temp_list[b] % mod
print(ans)
import sys
sys.setrecursionlimit(10e9)
N, M, K = map(int, input().split())
A = list(map(int, input().split()))
B = list(map(int, input().split()))

AA = list(reversed(A))
BB = list(reversed(B))

rest = K
ans = 0

def dfs(cost, aindex, bindex, score):

    if K == cost:
        # print("1:", score, cost)
        return score
    elif K < cost:
        # print("2:", score, cost)
        return score - 1
        # return -1
    
    if aindex == N and bindex == M:
        # print("3:", score, cost)
        return score

    if aindex >= N:
        return dfs(cost + B[bindex], aindex, bindex+1, score + 1)
    
    elif bindex >= M:
        return dfs(cost + A[aindex], aindex+1, bindex, score + 1)

    else:
        return max(dfs(cost + A[aindex], aindex+1, bindex, score + 1), dfs(cost + B[bindex], aindex, bindex + 1, score + 1))

print(max(dfs(A[0], 1, 0, 1), dfs(B[0], 0, 1, 1)))

### FIXED CODE ###

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

a, b = [0], [0]
for ai in A:
    a.append(a[-1] + ai)

for bi in B:
    b.append(b[-1] + bi)

# print(a, b)
ans = 0
bs = M
for i in range(N+1):
    if a[i] > K:
        break
    for j in reversed(range(bs+1)):
        if a[i] + b[j] <= K:
            ans = max(ans, i + j)
            bs = j
            break

print(ans)
N=int(input())
a=list(map(int,input().split()))
b=[0]*N
sum=0
for i in range(N):
  b[a[i]]+=1

for i in range(N):
  sum+=b[i]*(b[i]-1)//2
for i in range(N):
  print(sum-b[a[i]]-1)

### FIXED CODE ###

N=int(input())
a=list(map(int,input().split()))
b=[0]*N
sum=0
for i in range(N):
  b[a[i]-1]+=1

for i in range(N):
  sum+=b[i]*(b[i]-1)//2
for i in range(N):
  print(sum-b[a[i]-1]+1)
a = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split())) 
ans = 0

for i in range(a):
    if v(i) >= c(i):
        ans += (v(i)-c(i))
        
print(ans)

### FIXED CODE ###

a = int(input())
v = list(map(int,input().split()))
c = list(map(int,input().split())) 
ans = 0
for i in range(a):
    if v[i] >= c[i]:
        ans += (v[i]-c[i])
print(ans)
S = list(input())
K = int(input())

if len(S) == 1:
    print(K // 2)
else :
    pre = S[0]
    flg = 0
    cnt = 0
    cnt_list =[]
    
    for i in range(1, len(S)):
        cnt += 1
        if flg == 1:
            flg = 0
            pre = S[i]
            continue
        if S[i] == pre:
            cnt_list.append(cnt)
            flg = 1
        pre = S[i]
    
    S = S[::-1]
    pre = S[0]
    flg = 0
    cnt = 0
    cnt_list2 =[]
    
    for i in range(1, len(S)):
        cnt += 1
        if flg == 1:
            flg = 0
            pre = S[i]
            continue
        if S[i] == pre:
            cnt_list2.append(cnt)
            flg = 1
        pre = S[i]

    print(cnt_list, S*K)
    
    if S[0] == S[-1] and (S[-1] == S[-2] and len(S)-1 in cnt_list):
        print(len(cnt_list)*K)
    elif S[0] == S[-1] and (S[0] == S[1] and 0 in cnt_list2):
        print(len(cnt_list2)*K)
    elif S[0] == S[-1]:
        print(len(cnt_list)*K+K-1)
    else :
        print(len(cnt_list)*K)

### FIXED CODE ###

S = input()
K = int(input())
 
if len(S) == 1:
    print(K // 2)
    exit()

chkd, flg = 0, 1
cnt = 0
cnt_list =[]
 
for i in range(1, len(S)):
    cnt += 1
    if S[i] != S[i-1]:
        flg = 0
    if chkd == 1:
        chkd = 0
        continue
    if S[i] == S[i-1]:
        cnt_list.append(cnt)
        chkd = 1
 
# 2個連続の場合
S2 = S*2
chkd = 0
cnt = 0
cnt_list2 =[]
 
for i in range(1, len(S2)):
    cnt += 1
    if chkd == 1:
        chkd = 0
        continue
    if S2[i] == S2[i-1]:
        cnt_list2.append(cnt)
        chkd = 1

if flg: # 全部同じ場合
    print(len(S)*K // 2)
elif S[0] == S[-1]:
    print(len(cnt_list) + (len(cnt_list2)-len(cnt_list)) * (K - 1))
else :
    print(len(cnt_list)*K)
d = input()
a = int(input())
p = []
k = len(d)
for i in range(k):
  for j in range(k-i):
    p.append(d[i:i+j])
    
x = list(set(p))
x.sort()
del x[0]

print(x[a-1])

### FIXED CODE ###

d = input()
a = int(input())
p = []
k = len(d)
for i in range(k):
  for j in range(min({6,k-i+1})):
    p.append(d[i:i+j])
    
x = list(set(p))
x.sort()
del x[0]
 
print(x[a-1])
N = int(input())
W = map(int, input().split())
ans = 0

for T in range(N-1):
    tmp = abs(sum(W[1:T]) - sum(W[T:N]))
    if ans > tmp:
        ans = tmp
 
print(ans)

### FIXED CODE ###

N = int(input())
M = list(map(int, input().split()))
ans = sum(M)

for T in range(1, N):
    ans = min(abs(sum(M[0:T]) - sum(M[T:N])), ans)

print(ans)
N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for i in range(N-1):
  ans = ans + B[A[i]]
  if i > 0 and A[i] == A[i-1] + 1:
    ans = ans + C[A[i-1]]
print(str(ans))

### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
B=list(map(int,input().split()))
C=list(map(int,input().split()))
ans=0
for i in range(N):
  ans = ans + B[A[i] - 1]
  if i > 0 and A[i] == A[i-1] + 1:
    ans = ans + C[A[i-1] - 1]
print(str(ans))
T = list(str(input()))

for i in range(len(T)-1):
    if T[i] == '?' and T[i - 1] == 'P':
        T[i] = 'D'
    elif T[i] == '?' and T[i + 1] == 'D':
        T[i] = 'P'
    elif T[i] == '?' and T[i + 1] == '?':
        T[i] = 'P'
        T[i + 1] = 'D'
        i += 1
    elif T[i] == '?':
        T[i] = 'D'

if i == len(T):
    if T[i] == '?' and T[i - 1] == 'P':
        T[i] = 'D'
    elif T[i] == '?':
        T[i] = 'D'

print(''.join(T))


### FIXED CODE ###

T = list(str(input()))

for i in range(len(T)):
    if T[i] == '?':
        T[i] = 'D'
    print(T[i],end='')