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

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

for i in range(a,b+1):
    if i>=a+x and i<=b-x:
        continue
    else:
        print(i)


### FIXED CODE ###

a,b,k=map(int,input().split())

if b-a+1<=2*k:
    for i in range(a,b+1):
        print(i)
    exit()

else:
    for i in range(a,a+k):
        print(i)
    for j in range(b-k+1,b+1):
        print(j)
### BUGGY CODE ###

def check_block(comb, H):
    block = 0
    pre = (comb & 1) > 0
    mapping = {0: 0}
    cut_num = 0
    for i in range(1, H):
        cur = ((1 << i) & comb) > 0
        if pre != cur:
            block += 1
            pre = cur
            cut_num += 1
        mapping[i] = block
    return mapping, cut_num

H, W, K = map(int, input().split())
graph = [input() for ele in range(H)]
#
ans = 1319203291031903
for comb in range(1<<(H-1)):
    mapping, cut_num = check_block(comb, H)
    pre = [0] * (cut_num + 1)
    gg = False
    # preprocess 
    for j in range(H):
        pre[mapping[j]] += (graph[j][0] == '1')
    for ele in pre:
        if ele > K:
            gg = True
            break
    if gg: continue

    for i in range(1, W):
        cum = pre[:]
        for j in range(H):
            cum[mapping[j]] += (graph[j][i] == '1')
        for ii in range(len(cum)):
            if cum[ii] - pre[ii] > K:
                gg = True
                break
            if cum[ii] > K:
                cut_num += 1
                for idx in range(len(cum)):
                    cum[idx] -= pre[idx]
                break
        pre = cum
        if gg: break

    if not gg:
        ans = min(ans, cut_num)
print(ans)


### FIXED CODE ###

def check_block(comb, H):
    block = 0
    pre = (comb & 1) > 0
    mapping = {0: 0}
    cut_num = 0
    for i in range(1, H):
        cur = ((1 << i) & comb) > 0
        if pre != cur:
            block += 1
            pre = cur
            cut_num += 1
        mapping[i] = block
    return mapping, cut_num

H, W, K = map(int, input().split())
graph = [input() for ele in range(H)]
#
ans = 1319203291031903
for comb in range(1<<(H-1)):
    mapping, cut_num = check_block(comb, H)
    pre = [0] * (cut_num + 1)
    gg = False
    # preprocess 
    for j in range(H):
        pre[mapping[j]] += (graph[j][0] == '1')
    for ele in pre:
        if ele > K:
            gg = True
            break
    if gg: continue

    for i in range(1, W):
        cum = pre[:]
        for j in range(H):
            cum[mapping[j]] += (graph[j][i] == '1')
        for ii in range(len(cum)):
            if cum[ii] - pre[ii] > K or cut_num > ans:
                gg = True
                break
            if cum[ii] > K:
                cut_num += 1
                for idx in range(len(cum)):
                    cum[idx] -= pre[idx]
                break
        pre = cum
        if gg: break

    if not gg:
        ans = min(ans, cut_num)
print(ans)
### BUGGY CODE ###

K, S = map(int, input().split())
n = 0
for x in range(K+1):
  for y in range(K+1):
    if x+y > S:
      break
    for z in range(K+1):
      if x+y+z == S:
        n += 1
print(n)

### FIXED CODE ###

K, S = map(int, input().split())
n = 0
for x in range(K+1):
  for y in range(K+1):
    z = S-x-y
    if z>=0 and z<=K:
      n +=1
print(n)
### BUGGY CODE ###

from collections import deque
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    for j in range(i+1,n-1):
        for k in range(j+1,n):
            if tris[i] < tris[j] + tris[k] and tris[j] < tris[k] + tris[i] and tris[k] < tris[i] + tris[j]:
                cnt += 1
            else:
                break
print(cnt)


### FIXED CODE ###

import bisect
n = int(input())
tris = list(map(int,input().split()))
tris.sort()
cnt = 0
for i in range(n-2):
    a = tris[i]
    for j in range(i+1,n-1):
        b = tris[j]
        r = bisect.bisect_left(tris, a+b)
        cnt += r - j - 1
print(cnt)
### BUGGY CODE ###

import bisect


x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans_p = sorted(p, reverse=True)[:x][::-1]
ans_q = sorted(q, reverse=True)[:y][::-1]
r.sort(reverse=True)

for max_r in r:
    if ans_p[0] < ans_q[0]:
        if ans_p[0] < max_r:
            del ans_p[0]
            bisect.insort(ans_p, max_r)
        else:
            break
    else:
        if ans_q[0] < max_r:
            del ans_q[0]
            bisect.insort(ans_q, max_r)
        else:
            break
print(sum(ans_p)+sum(ans_q))

### FIXED CODE ###

x, y, a, b, c = map(int, input().split())
p = list(map(int, input().split()))
q = list(map(int, input().split()))
r = list(map(int, input().split()))

ans_p = sorted(p, reverse=True)[:x][::-1]
ans_q = sorted(q, reverse=True)[:y][::-1]
r.sort(reverse=True)

p_index = 0
q_index = 0
used_r_sum = 0

for max_r in r:
    ans_p_p_index = ans_p[p_index] if p_index < x else float('inf')
    ans_q_q_index = ans_q[q_index] if q_index < y else float('inf')
    if ans_p_p_index < ans_q_q_index:
        if ans_p_p_index < max_r:
            p_index += 1
            used_r_sum += max_r
        else:
            break
    else:
        if ans_q_q_index < max_r:
            q_index += 1
            used_r_sum += max_r
        else:
            break


print(sum(ans_p[p_index:])+sum(ans_q[q_index:])+used_r_sum)
### BUGGY CODE ###

def main():
    N = int(input())
    A = []
    d = []
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(i+1, N):
            if Ai[j] > 0:
                d.append((Ai[j], i, j))
    d.sort(key=lambda x: x[0])


    def wf(dist):
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])
        return dist


    ok = len(d)+1
    ng = 0
    mid = len(d)
    while ok - ng > 1:
        dist = [[10 ** 10 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            dist[i][i] = 0
        for x, i, j in d[:mid]:
            dist[i][j] = x
            dist[j][i] = x
        if wf(dist) == A:
            ok = mid
        else:
            ng = mid
            if ng == len(d):
                print(-1)
                exit()
        mid = (ok+ng)//2

    ans = 0
    for i in range(ok):
        ans += d[i][0]
    print(ans)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    N = int(input())
    A = []
    dist = [[0 for _ in range(N)] for _ in range(N)]
    for i in range(N):
        Ai = list(map(int, input().split()))
        A.append(Ai)
        for j in range(N):
            dist[i][j] = Ai[j]

    def wf(dist):
        need = [[1 for _ in range(N)] for _ in range(N)]
        for i in range(N):
            for j in range(N):
                for k in range(N):
                    if dist[i][j] > dist[i][k] + dist[k][j]:
                        print(-1)
                        exit()
                    elif dist[i][j] == dist[i][k] + dist[k][j]:
                        if i != k and j != k:
                            need[i][j] = 0
                            need[j][i] = 0
        return need

    need = wf(dist)
    ans = 0
    for i in range(N):
        for j in range(i+1, N):
            ans += need[i][j] * dist[i][j]
    print(ans)


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

import copy
n = int(input())
a = [int(input()) for _ in range(n)]
m = max(a)

for i in range(n):
    if a[i] != max(a):
        print(max(a))
    else:
        b = copy.copy(a)
        b.pop(i)
        print(max(b))

### FIXED CODE ###

import copy
n = int(input())
a = []
for _ in range(n):
    a.append(int(input()))
b = copy.copy(a)
a.sort(reverse=True)
for i in range(n):
    if b[i] == a[0]:
        print(a[1])
    else:
        print(a[0])
### BUGGY CODE ###

import sys

stdin = sys.stdin

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

def C(n,r):
    if n < 0 or r < 0 or n < r: 
        return 0
    elif n == 0 or r == 0: 
        return 1
    return C(n-1,r-1)+C(n-1,r)

def main():
    n = ni()
    l = sorted(na())

    j = n - 2
    k = n - 1
    cnt = 0
    dame = []
    for i in range(n - 3, -1, -1):
        try:
            if i in dame or j in dame or k in dame:
                continue
            a = l[i]
            b = l[j]
            c = l[k]
            if a < b + c and b < a + c and c < a + b:
                cnt += C(n - i - len(dame) - 1, 2)
                j -= 1
                k -= 1
            else:
                tmp = j
                while True:
                    a = l[i]
                    b = l[j]
                    c = l[k]
                    if a < b + c and b < a + c and c < a + b:
                        break
                    j += 1
                    k += 1
                    tmp = j
                cnt += C(n - tmp - 1 - len(dame), 2)
                dame.append(i)
        except:
            break
    print(cnt)

main()

### FIXED CODE ###

import sys

stdin = sys.stdin

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

from bisect import bisect_left

def main():
    n = ni()
    l = sorted(na())
    
    ans = 0
    for i in range(n):
        for j in range(i+1, n):
            t = l[i] + l[j]
            ind = bisect_left(l, t)
            ans += max(0, ind - j - 1)
    print(ans)

main()
### BUGGY CODE ###

N,M = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
import numpy as np
l = []
for i in [[a]*b for a,b in AB]:
  l.extend(i)

print(sum(sorted(l)[:M]))

### FIXED CODE ###

N,M = map(int, input().split())
import numpy as np
AB = np.array([list(map(int, input().split())) for _ in range(N)])
idx = np.argsort(AB[:,0],axis=0)
AB = AB[idx]
l = []
for a,b in AB:
  l.extend([a]*b)
  if len(l) > M:
    break
print(sum(l[:M]))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n, m = [int(x) for x in input().split()]
g = [[] for _ in range(n)]

for _ in range(m):
    l, r, d = [int(x) for x in input().split()]
    l -= 1
    r -= 1
    g[l].append((r, d))
    g[r].append((l, -d))

visited = [0] * n
d = [0] * n

for i in range(n):
    if visited[i] != 0:
        continue
    stack = [i]
    while stack:
        u = stack.pop()
        visited[u] = 1
        for v, d_ in g[u]:
            if d[v] == 0 and v != i:
                d[v] = d[u] + d_
                stack.append(v)
            else:
                if d[v] != d[u] + d_:
                    print("No")
                    sys.exit()
print("Yes")


### FIXED CODE ###

n, m = map(int, input().split())
ed = [[] for _ in range(n)]  # グラフ
v = [None] * n
for _ in range(m):
  l, r, d = map(int, input().split())
  ed[l-1].append((r-1, d))  # l -> r
  ed[r-1].append((l-1, -d))  # r -> l

visited = [False] * n  # 訪問フラグ（非連結の可能性の為）

def dfs(start):
  s = [start]
  v[start] = 0
  while s:
    label = s.pop()
    if visited[label] == False:
      visited[label] = True
      for to, dist in ed[label]:
        if v[to] is None:
          v[to] = v[label] + dist
          s.append(to)
        else:
          if v[to] != v[label] + dist:
            return False
  return True

is_exist = True
for i in range(n):
  if v[i] is None:
    if not dfs(i):
      print('No')
      is_exist = False
      break
if is_exist:
  print("Yes")
### BUGGY CODE ###

n = int(input())
p = [float(i) for i in input().split()]
dp = [[0 for i in range(len(p)+1)] for j in range(n)]
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]
for i in range(1,n):
	for j in range(len(p)+1):
		dp[i][j] += (1-p[i])*dp[i-1][j]
		dp[i][j] += p[i]*dp[i-1][j-1]
sum1 = 0
for i in dp[n-1][n//2+1:]:
	sum1+=i
print(sum1)

### FIXED CODE ###

n = int(input())
p = [float(i) for i in input().split()]
dp = [[0 for i in range(len(p)+1)] for j in range(n)]
dp[0][0] = 1 - p[0]
dp[0][1] = p[0]
for i in range(1,n):
	for j in range(len(p)+1):
		dp[i][j] += (1-p[i])*dp[i-1][j]
		dp[i][j] += p[i]*dp[i-1][j-1]
sum1 = 0
for i in dp[n-1][n//2+1:]:
	sum1+=i
print(sum1)
### BUGGY CODE ###

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

M=[N]*N

for i in range(K):
    L=[0]*(N+1)
    for j in range(N):
        L[max(0,j-A[j])]+=1
        L[min(N,j+A[j]+1)]-=1
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    #if A==M:
    #    break

for i in range(N):
    print(A[i],end=" ")
print()


### FIXED CODE ###

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

M=[N]*N

for i in range(K):
    L=[0]*(N+1)
    for j in range(N):
        L[max(0,j-A[j])]+=1
        L[min(N,j+A[j]+1)]-=1
        
    S=0
    for j in range(N):
        S+=L[j]
        A[j]=S

    if A==M:
        break

for i in range(N):
    print(A[i],end=" ")
print()
### BUGGY CODE ###

a,b,n = map(int,input().split())

ans =0

for x in range(1,n+1):
    ans = max( ans , (a * x) // b - a* (x // b))

print(ans)

### FIXED CODE ###

a,b,n = map(int,input().split())

ans =0

# for x in range(1,n+1):
x = min(b-1,n)
ans = max( ans , (a * x) // b - a* (x // b))
print(ans)
### BUGGY CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E.get(u1,[]):
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = dict()
p2 = dict()
for i in range(m):
  p[u[i]-1]=p.get(u[i]-1,[])+[(v[i]-1,a[i])]
  p[v[i]-1]=p.get(v[i]-1,[])+[(u[i]-1,a[i])]
  p2[u[i]-1]=p2.get(u[i]-1,[])+[(v[i]-1,b[i])]
  p2[v[i]-1]=p2.get(v[i]-1,[])+[(u[i]-1,b[i])]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [d[n-1]+d2[n-1]]
for i in range(1,n):
  ans.append(min(ans[i-1],d[n-1-i]+d2[n-1-i]))

for i in range(n):
  print(10**15-ans[n-1-i])

### FIXED CODE ###

#### import ####
import sys
import math
from collections import defaultdict

#### 設定 ####
sys.setrecursionlimit(10**7)
def input():
  return sys.stdin.readline()[:-1]

#### 定数 ####
mod = 10**9 + 7

#### 読み込み ####
def I(): return int(input())
def II(): return map(int, input().split())
def III(): return list(map(int, input().split()))
def Line(N):
  read_all = [tuple(map(int, input().split())) for _ in range(N)]
  return map(list,zip(*read_all))

#################

n,m,s,t = II()
u,v,a,b = Line(m)

from heapq import heappop, heappush
def dijkstra(E,s,n):
  inf=float('inf')
  d=[inf for _ in range(n)]
  d[s]=0
  q=[]
  heappush(q,(0,s))
  while q:
    du, u1 = heappop(q)
    if d[u1]<du: continue
    for v1,weight in E[u1].items():
      alt=du+weight
      if d[v1]>alt:
        d[v1]=alt
        heappush(q, (alt,v1))
  return d

p = [dict() for _ in range(n)]
p2 = [dict() for _ in range(n)]
for i in range(m):
  p[u[i]-1][v[i]-1] = a[i]
  p[v[i]-1][u[i]-1] = a[i]
  p2[u[i]-1][v[i]-1] = b[i]
  p2[v[i]-1][u[i]-1] = b[i]

d = dijkstra(p,s-1,n)
d2 = dijkstra(p2,t-1,n)

ans = [0]*n
ans[0] = d[n-1]+d2[n-1]
for i in range(1,n):
  ans[i] = min(ans[i-1],d[n-1-i]+d2[n-1-i])

for i in ans[::-1]:
  print(10**15-i)
### BUGGY CODE ###

import os
num = input().split(' ')
num_data = [int(num[i]) for i in range(3)]
#N X Y
data = [[i - 1,i + 1] if 0 < i and i < num_data[0] - 1 else [i + 1] for i in range(num_data[0])]
data[num_data[1] - 1].append(num_data[2] - 1)
data[num_data[2] - 1].append(num_data[1] - 1)
data[num_data[0] - 1][0] = num_data[0] - 2
cost = [0 for i in range(num_data[0] - 1)] #start position has the lowest number

key = 0
for i in range(num_data[0]):
    curent = i
    count = 1
    seen = [False for i in range(num_data[0])]
    seen[i] = True
    todo = [i]
    key = 0
    while(all(seen) == False):
        if(key == 0):
            key = len(todo) - 1
        else:
            key -= 1
        for per in data[curent]:
            if(seen[per]):
                pass
            else:
                seen[per] = True
                todo.append(per)
                cost[count - 1] += 1
        todo.pop(0)
        curent = todo[0]
        if(key == 0):
            count += 1

for per in cost:
    print(int(per/2))


### FIXED CODE ###

def main():
    n,x,y = map(int,input().split(' '))
    cost = [0 for i in range(n - 1)]
    for i in range(n - 1):
        for l in range(i + 1, n):
            result = min(abs(i - l),abs(i - x + 1) + 1 + abs(l - y + 1),abs(i - y + 1) + 1 + abs(l - x + 1))
            cost[result - 1] += 1
    for per in cost:
        print(per)

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


def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n)] for j in range(n)]
    
    for i in range(n):
        for j in range(i,n):
            if s[i]!=s[j]:
                continue
            else:
                cnt = 0
                for k in range(min(n-j,j-i)):
                    if s[i+k] ==s[j+k]:
                        cnt += 1
                    else:
                        break
                dp[i][j] = cnt 
    mx = 0
    for i in range(n):
        mx = max(mx,max(dp[i]))
    print(mx)

if __name__ =='__main__':main()
            
            
            


### FIXED CODE ###

def main():
    n = int(input())
    s = input()
    dp = [[0 for i in range(n+1)] for j in range(n+1)]
    
    from itertools import product
    for i,j in product(reversed(range(n)),repeat=2):###for を置き換え
        if j>i:
            continue
        if s[i]!=s[j]:
            dp[i][j] = 0 #continueではない	    
        else:
           	dp[i][j] = dp[i+1][j+1] +1
           	"""
            これでは結局ループしている
            cnt = 0
            for k in range(min(n-j,j-i)):
                if s[i+k] ==s[j+k]:
                    cnt += 1
                else:
                    break
            dp[i][j] = cnt
            """
    mx = 0
    #print(dp)
    for i in range(n):
      	for j in range(i):###
        	mx = max(mx,min(i-j,dp[i][j]))###i-jで抑える
    print(mx)

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

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs[: m], cs[m] // 2)
  r = bl(cs[m: ], cs[m] + (cs[-1] - cs[m]) // 2) + m
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)

### FIXED CODE ###

import sys
from bisect import bisect_left as bl
input = sys.stdin.readline
N = int(input())
a = list(map(int,input().split()))
cs = [0] * N
cs[0] = a[0]
for i in range(N - 1): cs[i + 1] = cs[i] + a[i + 1]
res = float("inf")
for m in range(1, N - 1):
  l = bl(cs, cs[m] // 2, hi = m)
  r = bl(cs, cs[m] + (cs[-1] - cs[m]) // 2, lo = m)
  l -= l == m
  r += r == m
  nl = l + 0
  nr = r + 0
  for i in range(3):
    if i == 1: continue
    if 0 <= l + i - 1 < m:
      if abs(cs[m] - 2 * cs[l + i - 1]) < abs(cs[m] - 2 * cs[l]):
        nl = l + i - 1
    if m < r + i - 1 < N:
      if abs(cs[-1] - 2 * cs[r + i - 1] + cs[m]) < abs(cs[-1] - 2 * cs[r] + cs[m]):
        nr = r + i - 1
  l = nl
  r = nr
  res = min(res, max(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]) - min(cs[l], cs[m] - cs[l], cs[r] - cs[m], cs[-1] - cs[r]))
print(res)
### BUGGY CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

mod = 10**9+7
N = 10**6                   # 出力の制限
g1 = [1]*(N+1)              # 元テーブル
g2 = [1]*(N+1)              # 逆元テーブル
for i in range( 2, N + 1 ): # 準備
    g1[i] = ( g1[i-1] * i ) % mod
    g2[i] = ( g2[i-1] * pow(i,mod-2,mod) ) % mod

def nCr(n, r, mod):
    if ( r<0 or r>n ):
        return 0
    r = min(r, n-r)
    return g1[n] * g2[r] * g2[n-r] % mod

def main():
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    for i in range(K+1):
        ret += nCr(i+Nk-1, Nk-1, mod) * pow(25,i,mod) * pow(26,K-i,mod)
        ret %= mod
    print(ret)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin python3
# -*- coding: utf-8 -*-

def main():
    mod = 10**9+7
    K = int(input())
    S = input()
    Nk = len(S)
    ret = 0
    nCk = 1
    pw25 = 1
    pw26 = pow(26,K,mod)
    inv26 = pow(26,mod-2,mod)
    for i in range(K+1):
        ret += nCk * pw25 * pw26
        ret %= mod
        nCk *= (i+Nk) * pow(i+1,mod-2,mod)
        nCk %= mod
        pw25 = (pw25*25)%mod
        pw26 = (pw26*inv26)%mod

    print(ret)

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

T = list(input())

s = T.count('?')

for i in range(s):
    a = T.index('?')
    T[a] = 'D'
print(''.join(T))

### FIXED CODE ###

T = input()

T = T.replace('?', 'D')
	
print(''.join(T))
### BUGGY CODE ###

from sys import stdin
import math

a,b = [int(x) for x in stdin.readline().rstrip().split()]

def is_prime(n):
    if n == 1: return False
    for k in range(2, int(math.sqrt(n)) + 1):
        if n % k == 0:
            return False
    return True

if a == 1:
    print(1)
    exit()

def cf(x1,x2):
    cf=[]
    cf.append(1)
    for i in range(2,min(x1,x2)+1):
        if x1 % i == 0 and x2 % i == 0 and is_prime(i) == True:
            cf.append(i)
    return len(cf)

print(cf(a,b))

### FIXED CODE ###

from sys import stdin
import fractions
import bisect

a,b = [int(x) for x in stdin.readline().rstrip().split()]

def prime_factorize(n):
    a = []
    while n % 2 == 0:
        a.append(2)
        n //= 2
    f = 3
    while f * f <= n:
        if n % f == 0:
            a.append(f)
            n //= f
        else:
            f += 2
    if n != 1:
        a.append(n)
    return a

ali = set(prime_factorize(a))
bli = set(prime_factorize(b))

ali = list(ali)
bli = list(bli)

point = 0
for i in range(len(ali)):
    if ali[i] in bli:
        point += 1
print(point+1)
### BUGGY CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*T for _ in range(N+1)]
for i,ab in enumerate(AB,1):
  for t in range(1,T):
    a = ab[0]
    if a>t:
      dp1[i][t]=dp1[i-1][t]
      
    else:
      dp1[i][t] = max(dp1[i-1][t],dp1[i-1][t-a]+ab[1])

rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,ab in enumerate(rev_AB,1):
  for t in range(1,T):
    a = ab[0]
    if a>t:
      dp2[i][t]=dp2[i-1][t]
      
    else:
      dp2[i][t] = max(dp2[i-1][t],dp2[i-1][t-a]+ab[1])
      
lis = [0]*N
for i in range(1,N+1):
  for t in range(T):
    lis[i-1] = max(dp1[i-1][t]+dp2[N-i][T-1-t]+AB[i-1][1],lis[i-1])

    
print(max(lis))

### FIXED CODE ###

N,T = map(int,input().split())
AB = [list(map(int,input().split())) for _ in range(N)]

dp1 = [[0]*T for _ in range(N+1)]
rev_AB = AB[::-1]
dp2 = [[0]*T for _ in range(N+1)]
for i,(ab,rev_ab) in enumerate(zip(AB,rev_AB),1):
  a = ab[0]
  rev_a = rev_ab[0]
  b = ab[1]
  rev_b = rev_ab[1]
  l_1 = dp1[i-1]
  l_2 = dp2[i-1]
  for t in range(1,T):
    if a>t:
      dp1[i][t]=l_1[t]
      
    else:
      dp1[i][t] = max(l_1[t],l_1[t-a]+b)
      
    if rev_a>t:
      dp2[i][t]=l_2[t]
    
    else:
      dp2[i][t] = max(l_2[t],l_2[t-rev_a]+rev_b)
      
      
    

      
lis = [0]*N
for i in range(1,N+1):
  l_1 = dp1[i-1]
  l_2 = dp2[N-i]
  b = AB[i-1][1]
  for t in range(T):
    lis[i-1] = max(l_1[t]+l_2[T-1-t]+b,lis[i-1])

    
print(max(lis))