Harryxun/stf_run huggingface dataset:
class Combination:
    """
    O(n)の前計算を1回行うことで，O(1)でnCr mod mを求められる
    n_max = 10**6のとき前処理は約950ms (PyPyなら約340ms, 10**7で約1800ms)
    使用例：
    comb = Combination(1000000)
    print(comb(5, 3))  # 10
    """
    def __init__(self, n_max, mod=10**9+7):
        self.mod = mod
        self.modinv = self.make_modinv_list(n_max)
        self.fac, self.facinv = self.make_factorial_list(n_max)

    def __call__(self, n, r):
        return self.fac[n] * self.facinv[r] % self.mod * self.facinv[n-r] % self.mod

    def make_factorial_list(self, n):
        # 階乗のリストと階乗のmod逆元のリストを返す O(n)
        # self.make_modinv_list()が先に実行されている必要がある
        fac = [1]
        facinv = [1]
        for i in range(1, n+1):
            fac.append(fac[i-1] * i % self.mod)
            facinv.append(facinv[i-1] * self.modinv[i] % self.mod)
        return fac, facinv

    def make_modinv_list(self, n):
        # 0からnまでのmod逆元のリストを返す O(n)
        modinv = [0] * (n+1)
        modinv[1] = 1
        for i in range(2, n+1):
            modinv[i] = self.mod - self.mod//i * modinv[self.mod%i] % self.mod
        return modinv

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

p = 998244353

comb = Combination(N-1,p)

# 何個を同じ色の組にするか0~K
cnt = 0
for k in range(K+1):
    buf = 0
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    buf = comb(N-1,k)

    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    buf *= M%p
    buf %= p
    buf *= pow((M-1),(N-k-1),p)
    cnt += buf%p
    cnt %= p

print(cnt)


### FIXED CODE ###

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

p = 998244353
# 何個を同じ色の組にするか0~K
cnt = 0
com = 1
for k in range(K+1):
    l = N-k
    # N-1個の組のうちどれを同じ色にするかN-1Ck
    # それぞれで、N-k個を別の色の順列にする
    # M*(M-1)**(N-k-1)
    x = pow((M-1),(l-1),p)
    cnt += M * x * com
    cnt %= p

    # 次のkのnCk
    com *= N-(k+1)
    com *= pow(k+1,p-2,p)
    com %= p


print(cnt)
git merge upstream/master

### FIXED CODE ###

import sys
import socket

if socket.gethostname() == 'N551J':
    sys.stdin = open('a1.in')


def read_int_list():
    return list(map(int, input().split()))


def read_int():
    return int(input())


def read_str_list():
    return input().split()


def read_str():
    return input()


def solve():
    if read_str().startswith('YAKI'):
        return 'Yes'
    return 'No'

def main():
    res = solve()
    print(res)


if __name__ == '__main__':
    main()
N = int(input())
l = []
alpha = "abcdefghijklmnopqrstuvwxyz"
d = {i+1: a for i, a in enumerate(alpha)}
while N != 0:
    l.append(N % 26)
    N = N // 26
ans = []
for i in l[::-1]:
    ans.append(d[i])
print("".join(ans))

### FIXED CODE ###

N = int(input())

def num2alpha(num):
    if num<=26:
        return chr(64+num)
    elif num%26==0:
        return num2alpha(num//26-1)+chr(90)
    else:
        return num2alpha(num//26)+chr(64+num%26)

print(num2alpha(N).lower())
n=input()
x=list(map(int, input().split()))
maxn=0
for i in range(n):
    if x[i]>maxn:
        maxn=x[i]
    else:
        maxn=maxn
minp=0
for j in range(n):
    minp=minp+(x[j]-1)**2
for i in range(maxn+1)
    for j in range(n):
        power=power+(x[j]-i)**2
    if power<minp:
        minp=power
    else:
        minp=minp
print(minp)

### FIXED CODE ###

n=int(input())
x=list(map(int, input().split()))
maxn=0
for i in range(n):
    if x[i]>maxn:
        maxn=x[i]
    else:
        maxn=maxn
minp=0
for j in range(n):
    minp=minp+(x[j]-1)**2
for i in range(maxn+1):
    power=0
    for j in range(n):
        power=power+(x[j]-i)**2
    if power<minp:
        minp=power
    else:
        minp=minp
print(minp)
def s(n):
  x = 0
  for i in range(len(n)):
    x += int(n[i])
  return x
n = input()
print("Yes") if n % s(n) == 0 else print("No")


### FIXED CODE ###

def s(n):
  x = 0
  for i in range(len(n)):
    x += int(n[i])
  return x
n = input()
print("Yes") if int(n) % s(n) == 0 else print("No")
S = input()
T = input()
k = len(T)
m = 0
for i in range(k):
  if S[k] == T[k]:
    m = m
  else:
    m += 1
print(m)

### FIXED CODE ###

S = input()
T = input()
k = len(T)
m = 0
for i in range(k):
  if S[i] != T[i]:
    m += 1
print(m)
A = int(input())
op = input()
B = input()

if op == '+':
  print(A + B)
else:
  print(A - B)

### FIXED CODE ###

a = input().split()
if a[1] == '+':
    print(int(a[0])+int(a[2]))
else:
    print(int(a[0])-int(a[-1]))
from collections import defaultdict as de
s=de(int)
u=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    u.append(a[i])
    for j in range(n):
        if i!=j:
            s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
p,q=max([(v,k) for k,v in s.items()])[1]
i=0
p=n-1
g=0
while i!=n:
    if u[a[n-1]]>0:
        u[a[n-1]]-=1
    s,t=a[n-1][0]-p,a[n-1][1]-q
    i+=1
    while u[s,t]>0:
        u[s,t]-=1
        s-=p
        t-=q
        i+=1
    else:
        g+=1
print(g)

### FIXED CODE ###

from collections import defaultdict as de
s=de(int)
n=int(input())
a=sorted([list(map(int,input().split()))for i in range(n)])
for i in range(n):
    for j in range(i):
        s[(a[i][0]-a[j][0],a[i][1]-a[j][1])]+=1
print(n-max(s.values(),default=0))
S = input()
T = input()
a = []
ans = 0
for i in range(len(S)-2):
    if S[i]==T[0]:
        ans+=1
        if S[i+1]==T[1]:
            ans+=1
            if S[i+2]==T[2]:
                ans+=1
    a.append(ans)
    ans=0
print(len(T)-max(a))

### FIXED CODE ###

S = input()
T = input()
a = []
ans = 0
for i in range(len(S)-len(T)+1):
    C = S[i:i+len(T)]
    for j in range(len(T)):
        if C[j] == T[j]:
            ans+=1
    a.append(ans)
    ans=0
print(len(T)-max(a))
import math

height, width = [int(i) for i in input().split(' ')]

if height > 1 and width > 2:
    print(math.ceil(width/2) * math.ceil(height/2) + math.floor(width/2) * math.floor(height/2))
else print(1)

### FIXED CODE ###

import math

height, width = [int(i) for i in input().split(' ')]

if height > 1 and width > 2:
    print(math.ceil(width/2) * math.ceil(height/2) + math.floor(width/2) * math.floor(height/2))
else:
    print(1)
import sys
input=sys.stdin.readline
from heapq import *
from collections import defaultdict
x, y, z, k = map(int,input().split())
a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))

a = sorted(a, reverse = True)
b = sorted(b, reverse = True)
c = sorted(c, reverse = True)

ans = [[-(a[0] + b[0] + c[0]), 1, 1, 1]]
heapify(ans)
log = defaultdict(lambda :0)

d = [(1, 0, 0), (0, 1, 0), (0, 0, 1)]
for i in range(k):
    temp, s, t, u = heappop(ans)
    temp = temp * (-1)
    print(temp)
    for ds, dt, du in d:
        ns = s + ds
        nt = t + dt
        nu = u + du
        if not(0 <= ns < x and 0 <= nt < y and 0 <= nu < z):continue
        if log[(ns, nt, nu)]:continue
        heappush(ans, [-(a[ns - 1] + b[nt - 1] + c[nu - 1]), ns, nt, nu])
        log[(ns, nt, nu)] = 1


### FIXED CODE ###

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

c = sorted(c, reverse=True)
ab = []
for i in range(x):
    for j in range(y):
        temp = a[i] + b[j]
        ab.append(temp)

ab = sorted(ab, reverse=True)
ans = []
for i in range(z):
    for j in range(min(x * y, k)):
        temp = c[i] + ab[j]
        ans += [temp]
ans = sorted(ans, reverse=True)

for i in range(k):
    print(ans[i])
x = int()
print(str(x)+"????????????"+str(x*x*x))

 print(eval(input())**3)

### FIXED CODE ###

x = int(input())
print(x*x*x)
s = input()
k = int(input())
onesum = 0
while s[0] == "1" and len(s) > 0:
    s = s[1:]
    onesum += 1
if k <= onesum:
    print(1)
else:
    print(s[0])


### FIXED CODE ###

s = input()
k = int(input())
onesum = 0
while s[0] == "1":
    onesum += 1
    if len(s) == 1:
        break
    s = s[1:]
if k <= onesum:
    print(1)
else:
    print(s[0])
N, M = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(M)]
for i in range(0, 10**N):
    if len(str(i))==N and all(str(i)[s-1] == c for s,c in sc)
    print(i)
else:
    print(-1)

### FIXED CODE ###

N, M = map(int, input().split())
sc = [list(map(int, input().split())) for i in range(M)]
for i in range(10**N): #rangeで書けば小さい順に実行するのを利用
    if len(str(i))==N and all(str(i)[s-1]==str(c) for s,c in sc):
                    #iの桁数指定では、入力のsと一つずれることに注意  
                    #このif文では最小値である可能性のある数字がリスト中にあるかどうか確認
        print(i)
        break
else:
    print(-1)
N=int(input())
H=list(map(int,input().split()))

HH=[H[1]-H[0]]
M=0
K=[]
if N==1:
    print(0)
elif N==2:
    if H[0]>=H[1]:
        print(1)
    else:
        print(0)
else:
    for i in range(1,N-1):
        HH.append(H[i+1]-H[i])
    for i in range(len(HH)):
        if HH[i]<=0:
            M+=1
        else:
            K.append(M)
            M=0
    K.append(M)
    print(max(K))

### FIXED CODE ###

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


M=0
K=[]
if N==1:
    print(0)
elif N==2:
    if H[0]>=H[1]:
        print(1)
    else:
        print(0)
else:
    HH=[H[1]-H[0]]
    for i in range(1,N-1):
        HH.append(H[i+1]-H[i])
    for i in range(len(HH)):
        if HH[i]<=0:
            M+=1
        else:
            K.append(M)
            M=0
    K.append(M)
    print(max(K))
tate =int(input())
yoko=int(input())
arr = [i+1 for i in range(tate)]
for j in range(yoko):
    rep1,rep2=input().split()
    rep1=int(rep1)-1
    rep2=int(rep2)-1
    arr[rep1],arr[rep2] = arr[rep2],arr[rep1]

for k in range(tate):
    print(arr[k])


### FIXED CODE ###

tate =int(input())
yoko=int(input())
arr = [i+1 for i in range(tate)]
for j in range(yoko):
    rep1,rep2=input().split(",")
    rep1=int(rep1)-1
    rep2=int(rep2)-1
    arr[rep1],arr[rep2] = arr[rep2],arr[rep1]

for k in range(tate):
    print(arr[k])
from collections import Counter 
from collections import defaultdict
from collections import deque
from functools import reduce
import math
import itertools
import heapq
import numpy as np
import sys
sys.setrecursionlimit(10**6)

#n=int(input())
#n,m=list(map(int,input().split()))
#a=list(map(int,input().split()))
ceil=lambda x,y: (x+y-1)//y
input_list = lambda : list(map(int,input().split()))



#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    check=[False for _ in range(n)]
    check[s]=True
    queue=[n for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:

        
        if now>=n or queue[now]==n:
            return []

        for i in node[queue[now]]:
            edge=i[0]
            
            ind=i[1]
            if check[edge]:
                continue

            queue[last_ind]=edge
            last_ind+=1
            #check[edge]=True
            
            ans[edge]=queue[now]
            check[edge]=True
        now+=1
        print(queue)
        print(last_ind)
        print()
    return ans



n,m=input_list()
node=[[] for _ in range(n)]
for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append([v,i])
    node[v].append([u,i])

#print(np.array(node))

ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

print("Yes")
for each in ans[1:]:
    print(each+1)








### FIXED CODE ###

input_list = lambda : list(map(int,input().split()))


#bfs内で処理すると使い回しが効かないのでsearch_color とか幅探索後の具体的な処理は別個にしたほうがいい
def bfs(s,n,node):
    c=[-1 for _ in range(n)]
    c[0]=0
    
    side_num_arr=list(map(lambda x :len(x),node))
    #print(l)
    queue=[-1 for _ in range(n)]
    now=0
    queue[now]=s
    ans=[-1 for _ in range(n)]
    ans[0]=[0]
    last_ind=1
    while last_ind<n:
        
        if now>=n:
            return []
        c[queue[now]]=True
        if side_num_arr[queue[now]]<=0:
            now+=1
            continue
        for edge in node[queue[now]]:
            #edge=i[0]
            if side_num_arr[edge]<=0 or c[edge]==True:
                continue
            side_num_arr[edge]-=1
            
            queue[last_ind]=edge
            last_ind+=1
            c[edge]=True
            ans[edge]=queue[now]

        side_num_arr[queue[now]]=0
        now+=1
    return ans



n,m=input_list()
node=[[] for _ in range(n)]

for i in range(m):
    u,v=input_list()
    u-=1
    v-=1
    node[u].append(v)
    node[v].append(u)

#print(np.array(node))

ans=bfs(0,n,node)
if len(ans)==0:
    print("No")
    exit()

print("Yes")
for each in ans[1:]:
    print(each+1)
N = int(input())
S = list(input())

tb = [False]*10**2
for i in range(N):
    for j in range(i+1,N):
        for k in range(j+1,N):
            l = int(''.join(S[i]+S[j]+S[k]))
            tb[l] = True
print(tb.count(True))

### FIXED CODE ###

from collections import defaultdict
n = int(input())
S = input()

d1 = defaultdict(int)
d2 = defaultdict(int)
d3 = defaultdict(int)

for s in S:
    for x in d2:
        d3[x+s]+=1
    for y in d1:
        d2[y+s]+=1
    d1[s]+=1

print(len(d3))
def main():
    a, b = map(int, open(0).read().split())

    ans = max(0, a - b * 2)
    print(ans)
    return()

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, = map(int, open(0).read().split())

    ans = ((n+1) // 2) / n
    print(ans)
    return()

if __name__ == '__main__':
    main()
n,c=map(int,input().split())
x=[0]
v=[]
for i in range(n):
    a,b=map(int,input().split())
    x.append(a)
    v.append(b)

x1=[x[i+1]-x[i] for i in range(len(x)-1)]
x2=[c-x[-1]]+x1[:0:-1]
h=[0]
for i,j in zip(x2,reversed(v)):
    h.append(h[-1]+j+-i)
t=[0]
for i,j in zip(x1,v):
    t.append(t[-1]+j-i)
hi=h.index(max(h[0:-1]))
ti=t.index(max(t[0:-1]))
tm=max(t[0:-1])
hm=max(h[0:-ti])
h2=[h[i]-c+x[-i] for i in range(1,len(h))]
t2=[t[i]-x[i] for i in range(1,len(t))]


#print(ti,hi)
print(max(max(t), max(h), hm+max(t2[0:-ti]),tm+max(h2[:-hi])))

### FIXED CODE ###

n,c=map(int, input().split())
a=[[0,0]]+[list(map(int, input().split())) for i in range(n)]+[[c,0]]
m=[0]
h=[0]
mb=[0]
hb=[0]
for i in range(n+1):
    m.append(m[-1]-a[i+1][0]+a[i][0]+a[i+1][1])
    mb.append(m[-2]-a[i+1][0]+a[i][0]+a[i+1][1]-a[i+1][0])
    h.append(h[-1]-a[-i-1][0]+a[-i-2][0]+a[-i-2][1])
    hb.append(h[-2]-a[-i-1][0]+a[-i-2][0]+a[-i-2][1]-c+a[-i-2][0])

mm=[0]
for i in range(n):
    mm.append(max(mm[-1],m[i+1]))
hm=[0]
for i in range(n):
    hm.append(max(hm[-1],h[i+1]))
    
ans=max(hm[-1],mm[-1])
for i in range(1,n):
    ans=max(hb[i]+mm[-i-1], mb[i]+hm[-i-1],ans)
print(ans)
N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

dp = [1,1]
last_idx = [-1]*(N+10)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])

### FIXED CODE ###

N = int(input())
C = [int(input()) for _ in range(N)]
MOD = 10**9 + 7

if N <= 2:
    print(1)
    exit()

dp = [1,1]
last_idx = [-1]*(N+10)
last_idx[C[0]] = 0
last_idx[C[1]] = 1

for i in range(2, N):
    if C[i-1] == C[i] or last_idx[C[i]] == -1:
        dp.append(dp[-1] % MOD)
    else:
        dp.append((dp[-1] + dp[last_idx[C[i]]]) % MOD)
    last_idx[C[i]] = i

print(dp[-1])
string = input().split()
print(string[1]+string[0]

### FIXED CODE ###

s = input().split()
print(s[1]+s[0])
N = int(input())
res = 0
for i in range(N):
    x,u = map(str, input().split())
    if u == "JPY":
        res += int(x)
    else:
        res += int(x)*380000
print(res)

### FIXED CODE ###

N = int(input())
res = 0
for i in range(N):
    x,u = map(str, input().split())
    if u == "JPY":
        res += int(x)
    else:
        res += float(x)*380000
print(res)
from math import gcd
from functools import reduce

def lcm(a, b):
    return a*b // gcd(a, b)

N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))
print(reduce(lcm, T))

### FIXED CODE ###

from fractions import gcd
from functools import reduce

def lcm(a, b):
    return a*b // gcd(a, b)

N = int(input())
T = []
for _ in range(N):
    T.append(int(input()))
print(reduce(lcm, T))
n = int(input())
    s = input()

    m = 0
    for i in range(1, n - 1):
        a = s[:i]
        b = s[i:]
        c = len(set(a) & set(b))
        if c >= m:
            m = c

    print(m)

### FIXED CODE ###

n = int(input())
s = input()

m = 0
for i in range(1, n - 1):
  a = s[:i]
  b = s[i:]
  c = len(set(a) & set(b))
  if c >= m:
    m = c

print(m)
import sys
     
    def get_minimun_val(n, rule_dict):
      max_val = 10**n
      min_val = 10**(n-1)
      for i in range(min_val, max_val):
        str_i = str(i)
        flg = True
        for s, c in rule_dict.items():
          if str_i[s-1] == str(c):
            continue
          else:
            flg = False
            break
        if flg:
          return i
      return -1
     
     
    rule_dict = {}
     
    n, m = map(int, input().split())
    res = -1
    for i in range(m):
      s, c = map(int, input().split())
      if c == 0 and s == 1:
        print(-1)
        sys.exit()
      if s not in rule_dict:
        rule_dict[s] = c
        continue
      current_c = rule_dict[s]
      if c != current_c:
        print(-1)
        sys.exit()
     
    print(get_minimun_val(n, rule_dict))

### FIXED CODE ###

import sys

def get_minimun_val(n, rule_dict):
  max_val = 10**n
  min_val = 10**(n-1)
  if min_val == 1:
    min_val=0
  for i in range(min_val, max_val):
    str_i = str(i)
    flg = True
    for s, c in rule_dict.items():
      if str_i[s-1] == str(c):
        continue
      else:
        flg = False
        break
    if flg:
      return i
  return -1


rule_dict = {}

n, m = map(int, input().split())
res = -1
for i in range(m):
  s, c = map(int, input().split())
  if c == 0 and s == 1 and n > 1:
    print(-1)
    sys.exit()
  if s not in rule_dict:
    rule_dict[s] = c
    continue
  current_c = rule_dict[s]
  if c != current_c:
    print(-1)
    sys.exit()

print(get_minimun_val(n, rule_dict))
n, k = map(int, input().split())
a = list(map(int, input().split()))
ind = 0
l = []
for i in range(k):
    if ind in l:
        break
    l.append(ind)
    ind = a[ind]-1
l = l[l.index(ind):]
for i in range((k-i)%len(l)):
    ind = a[ind]-1
print(ind+1)

### FIXED CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
d = {}
for i in range(1, n+1):
    d[i] = 0
l = [1]
x = 1
if n >= k:
    for i in range(k):
        x = a[x-1]
    print(x)
    exit()
for i in range(n):
    x = a[x-1]
    if d[x] == 1:
        k -= l.index(x)
        print(l[l.index(x):][k%(l.index(x)-len(l))])
        exit()
    l.append(x)
    d[x] += 1
print(x)
# n = int(sys.stdin.readline())
# a, b = map(int, sys.stdin.readline().split())
# c = list(map(int, sys.stdin.readline().split()))
# s = [list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a = 100
# b = 0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋め, 小数点出力桁指定時のときの出力
# 000100-0.987654

import math
import sys
import itertools
import queue

mod = 1000000007

def lcm(x, y):
    return (x * y) // math.gcd(x, y)

if __name__ == "__main__":
    A, B, C, D = map(int, sys.stdin.readline().split())
    A = A - 1
    c_div = math.floor(B / C)
    #nc_div = (B - c_div)
    d_div = math.floor(B / D)
    #nd_div = (B - d_div)
    cd_div = math.floor(B / lcm(C, D))
    #ncd_div = (B - cd_div)
    #print(nc_div)
    #print(nd_div)
    #print(ncd_div)


    not_div1 = B - (c_div + d_div -cd_div)

    c_div = math.floor(A / C)
    nc_div = (A - c_div)
    d_div = math.floor(A / D)
    nd_div = (A - d_div)
    cd_div = math.floor(A / lcm(C, D))
    ncd_div = (A - cd_div)

    not_div2 = A - (c_div + d_div -cd_div)
    #not_div2 = nc_div + nd_div - ncd_div

    #print(not_div1)
    #print(not_div2)

    #print(not_div2)

    print(not_div1 - not_div2)



### FIXED CODE ###

# n = int(sys.stdin.readline())
# a, b = map(int, sys.stdin.readline().split())
# c = list(map(int, sys.stdin.readline().split()))
# s = [list(map(int,list(sys.stdin.readline()))) for i in range(h)]  # 二次元配列入力　二次元マップみたいな入力のとき

# a = 100
# b = 0.987654321
# print('{0:06d}-{1:6f}'.format(a,b))  # 0埋め, 小数点出力桁指定時のときの出力
# 000100-0.987654

import math
import sys
import itertools
import queue
from functools import reduce
from fractions import gcd

def lcm(a, b):
    return a * b // gcd(a, b)

mod = 1000000007

if __name__ == "__main__":
    A, B, C, D = map(int, sys.stdin.readline().split())
    A = A - 1
    c_div = int(B // C)
    d_div = int(B // D)
    cd_div = int(B // lcm(C, D))

    not_div1 = B - (c_div + d_div -cd_div)

    c_div = int(A // C)
    d_div = int(A // D)
    cd_div = int(A // lcm(C, D))

    not_div2 = A - (c_div + d_div -cd_div)

    print(not_div1 - not_div2)
import numpy as np

N = int(input())
A = np.zeros(1000000000,dtype=bool)

for _ in range(N):
    i = int(input())
    A[i] = not A[i]
    
print(np.count_nonzero(A))

### FIXED CODE ###

n=int(input())
d={}
for _ in [0]*n:
    v=int(input())
    d[v]=(d.get(v,0)+1)%2
    
print(sum(d.values()))
s=input()
n=len(s)
def dfs(i,x):
    if i==n-1:
        return sum(list(int,x.split('+')))
    return dfs(i+1,x+s[i+1])+dfs(i+1,x+'+'+s[i+1])
print(dfs(0,s[0]))

### FIXED CODE ###

s=input()
n=len(s)

def f(i,t):
    if i == n-1:
        return sum(list(map(int, t.split('+'))))
    
    return f(i+1,t+s[i+1]) + f(i+1,t+'+'+s[i+1]) #sumの値を足してる

print(f(0,s[0]))
N,K = map(int,input().split())
S = input()
if S[0] == '0':
  divide = []
else:
  divide = [0]
tmp = 1
for i in range(1,N):
  if S[i] == S[i-1]:
    tmp += 1
  else:
    divide += [tmp]
    tmp = 1
divide += [tmp]
le = len(divide)
zero = [0]*2*le + divide + [0]*2*le
su = [0]
for i in range(0,5*le):
  su += [su[-1]+zero[i]]
del su[0]
lle = len(su)
mxm = 0
for k in range(K,lle):
  if 2*k+1 > lle:
    break
  cd = su[2*k+1] - su[2*k-2*K]
  if cd > mxm:
    mxm = cd
print(mxm)

### FIXED CODE ###

N,K = map(int,input().split())
S = input()
if S[0] == '0':
  divide = []
else:
  divide = [0]
tmp = 1
for i in range(1,N):
  if S[i] == S[i-1]:
    tmp += 1
  else:
    divide += [tmp]
    tmp = 1
divide += [tmp]
le = len(divide)
zero = [0]*2*le + divide + [0]*2*le
su = [0]
for i in range(0,5*le):
  su += [su[-1]+zero[i]]
del su[0]
lle = len(su)
mxm = 0
for k in range(K,lle):
  if 2*k+1 >= lle:
    break
  cd = su[2*k+1] - su[2*k-2*K]
  if cd > mxm:
    mxm = cd
xmx = max(divide)
print(max(mxm,xmx))
a,b=map(int,input().split())

d = [0]*(2*(10**5))
for i in range(a):
    ts,tf,c =map(int,input().split())
    d[(ts-1)*2]+=1
    d[(tf-1)*2+2]-=1
M = 0
for i in range(len(d)):
    if i > 0:
        d[i] = d[i-1]+d[i]
    M = max(M,d[i])
print(M)


### FIXED CODE ###

##########################
from collections import defaultdict as ddict
N, C = map(int, input().split())
imos = [0] * (10**5 + 2)
last_s_by_c = ddict(lambda: 1)
last_t_by_c = ddict(int)
stc = [list(map(int, input().split())) for i in range(N)]
for s, t, c in sorted(stc, key=lambda x: x[1]):
	if last_t_by_c[c] != s:
		imos[last_s_by_c[c] - 1] += 1
		imos[last_t_by_c[c]] -= 1
		last_s_by_c[c] = s
	last_t_by_c[c] = t
for c in last_s_by_c:
	imos[last_s_by_c[c] - 1] += 1
	imos[last_t_by_c[c]] -= 1
for i in range(10**5 + 1):
	imos[i + 1] += imos[i]
print(max(imos))
import sys
from datetime import datetime

def main():
    line = sys.stdin.readline()
    today = datetime.strptime(line, "%Y/%m/%d")
    TBD = datetime(2019, 5, 1)
    if today < TBD:
        print("HEISEI")
    else:
        print("TBD")

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
from datetime import datetime

def main():
    line = sys.stdin.readline().strip()
    today = datetime.strptime(line, "%Y/%m/%d")
    TBD = datetime(2019, 5, 1)
    if today < TBD:
        print("Heisei")
    else:
        print("TBD")

if __name__ == "__main__":
    main()