Harryxun/stf_run huggingface dataset:
N=int(input())
A=[26,702,18278,475254,12356630,321272406,8353082582,217180147158,5646683826134,146813779479510,3817158266467286]
B=["a","b","c","d","e","f","g","h","i","j","k","l","m","n","o","p","q","r","s","t","u","v","w","x","y","z"]
a=0
for x in range(11):
  if N<=A[x]:
    a=x
    break
for y in range(a):
  b=N//(26**(a-y))
  print(B[b-1],end="")
  N=N-b*(26**(a-y))
print(B[N-1])
  
  

### FIXED CODE ###

'''
Created on 2020/08/31

@author: harurun
'''
def main():
  import sys
  pin=sys.stdin.readline
  pout=sys.stdout.write
  perr=sys.stderr.write

  N=int(pin())
  ans=""
  while N:
    N-=1
    ans+=chr(97+N%26)
    N=N//26
  print(ans[::-1])
  return
main()
#解説AC
import sys
import math


stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

AB_array = [na() for _ in range(N)]

# print(AB_array)

plus_dic = {}
minus_dic = {}
ans = 1
fish_count = 0
mod = 10 ** 9 + 7
for ab in AB_array:
    a, b = ab
    if a == 0 and b == 0:
        continue
    fish_count += 1
    if a == 0:
        vec = (0, 1)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
    elif b == 0:
        vec = (1, 0)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1
    c = math.gcd(a, b)
    a = a // c
    b = b // c
    if a < 0:
        a *= -1
        b *= -1
    if b > 0:
        vec = (a, b)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
    else:
        vec = (a, b)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1


# print(plus_dic, minus_dic, fish_count)

for k, vp in plus_dic.items():
    x, y = k
    if (y, -x) in minus_dic:
        vm = minus_dic[(y, -x)]
        ans = ans * (pow(2, vp, mod) + pow(2, vm, mod) - 1) % mod
        fish_count -= (vp + vm)

ans = ans * pow(2, fish_count, mod) % mod

print((ans - 1) % mod)


### FIXED CODE ###

import sys
import math


stdin = sys.stdin


def ni(): return int(ns())


def na(): return list(map(int, stdin.readline().split()))


def ns(): return stdin.readline().rstrip()  # ignore trailing spaces


N = ni()

AB_array = [na() for _ in range(N)]

# print(AB_array)

plus_dic = {}
minus_dic = {}
ans = 1
fish_count = 0
mod = 10 ** 9 + 7
zero_count = 0
for ab in AB_array:
    a, b = ab
    if a == 0 and b == 0:
        zero_count += 1
        continue
    fish_count += 1
    if a == 0:
        vec = (0, 1)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
        continue
    elif b == 0:
        vec = (1, 0)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1
        continue
    c = math.gcd(a, b)
    a = a // c
    b = b // c
    if a < 0:
        a *= -1
        b *= -1
    if b > 0:
        vec = (a, b)
        if vec in plus_dic:
            plus_dic[vec] += 1
        else:
            plus_dic[vec] = 1
    else:
        vec = (a, b)
        if vec in minus_dic:
            minus_dic[vec] += 1
        else:
            minus_dic[vec] = 1


# print(plus_dic, minus_dic, fish_count)

for k, vp in plus_dic.items():
    x, y = k
    if (y, -x) in minus_dic:
        vm = minus_dic[(y, -x)]
        ans = ans * (pow(2, vp, mod) + pow(2, vm, mod) - 1) % mod
        fish_count -= (vp + vm)

ans = ans * pow(2, fish_count, mod) % mod

print((ans - 1 + zero_count) % mod)
n=int(input())
s=int(input())

No=0
if n==s:
    print(n+1)
    No =1
else:
    for b in range(2,int(n**0.5)+2):
        m=0
        N=n
        while N!=0:
            m+=N%b
            N=N//b
            if m>s:
                break    
        if m==s:
            print(b)
            No=1
            exit()
    for p in range(int(n**0.5-1),0,-1):
        b = float(n-s)/float(p)+1.0
        if abs(b-int(b))<10**(-10):
            b=int(b)
            m=0
            N=n
            while N!=0:
                m+=N%b
                N=N//b
                if m>s:
                    break    
            if m==s:
                print(b)
                No=1
                exit()
if No==0:
    print(-1)

### FIXED CODE ###

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

No=0
if n==s:
    print(n+1)
    No =1
else:
    for b in range(2,int(n**0.5)+2):
        m=0
        N=n
        while N!=0:
            m+=N%b
            N=N//b
            if m>s:
                break    
        if m==s:
            print(b)
            No=1
            exit()
    for p in range(int(n**0.5-1),0,-1):
        b = float(n-s)/float(p)+1.0
        if abs(b-int(b))<10**(-10)and b>0:
            b=int(b)
            m=0
            N=n
            while N!=0:
                m+=N%b
                N=N//b
                if m>s:
                    break    
            if m==s:
                print(b)
                No=1
                exit()
if No==0:
    print(-1)
input = input().split()

a, b, c = input_
a, b, c = int(a), int(b), int(c)

if a == b + c, b == c + a, c == a + b:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

input_ = input().split()

a, b, c = input_
a, b, c = int(a), int(b), int(c)

if a == b + c or b == c + a or c == a + b:
    print("Yes")
else:
    print("No")
while True:
    H, W = [int(i) for i in input().split()]

        if H + W % == 0:
            print('#')

        else:
            print('.')

    print

        

### FIXED CODE ###

while True:
    H, W = [int(i) for i in input().split()]
    if H == W == 0:
       break

    for h in range(H):
        for w in range(W):
            if (h + w) % 2 == 0:
                print('#', end='')
            else:
                print('.', end='')

        print()
    print()
import sys
n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i : [] for i in range(n)}
for i in range(n-1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j : i for i, j in enumerate(path)}
already = set()

def dfs(ind, cur_dis):
    res = 0
    already.add(ind)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis:
                continue
            else:
                res = max(res, dfs(_next, cur_dis + 1) - 1)
        else:
            res = max(res, dfs(_next, cur_dis + 1) + 1)
    return res

res = dfs(u, 0)
if res == 0:
    print(distance - 1)
else:
    print(distance + res - distance % 2)

### FIXED CODE ###

import sys

sys.setrecursionlimit(10 ** 7)

n, u, v = [int(i) for i in sys.stdin.readline().split()]
u -= 1
v -= 1
graph = {i: [] for i in range(n)}
for i in range(n - 1):
    a, b = [int(i) for i in sys.stdin.readline().split()]
    a -= 1
    b -= 1
    graph[a].append(b)
    graph[b].append(a)

distance = 0
stack = [(u, 0)]
already = set()
parent = [i for i in range(n)]
while len(stack) > 0:
    cur, dis = stack.pop(-1)
    already.add(cur)
    for _next in graph[cur]:
        if _next in already:
            continue
        parent[_next] = cur
        if _next == v:
            distance = dis + 1
            break
        stack.append((_next, dis + 1))
cur = v
path = []
while cur != u:
    path.append(cur)
    cur = parent[cur]

path_dict = {j: i for i, j in enumerate(path)}
already = set()
ls = []
stack = [(u, 0, 0)]
while len(stack) > 0:
    ind, cur_dis, minus = stack.pop(-1)
    already.add(ind)
    ls.append(cur_dis - minus)
    for _next in graph[ind]:
        parent[_next] = ind
        if _next in already:
            continue
        if _next in path:
            if path_dict[_next] <= cur_dis + 1:
                continue
            else:
                stack.append((_next, cur_dis + 1, minus + 2))
        else:
            stack.append((_next, cur_dis + 1, minus))

res = max(ls)

if res == 0:
    print(distance - 1)
else:
    print(distance + res - 1)
K = int(input())

i = 7%K
se = set(i)
cnt = 1
while True:
  if i == 0:
    print(cnt)
    break
  cnt += 1
  i = (i*10 + 7)%K
  if i in se:
    print(-1)
    break
  else:
    se.add(i)
  

### FIXED CODE ###

K = int(input())

i = 7%K
se = set([i])
cnt = 1
while True:
  if i == 0:
    print(cnt)
    break
  cnt += 1
  i = (i*10 + 7)%K
  if i in se:
    print(-1)
    break
  else:
    se.add(i)
N, Y = map(int, input().split())
ans = [-1,-1,-1]
for x in range(N+1):
  for y in range(N+1):
    z = N-x-y
    if z < 0: continue

    if (10000*x + 5000*y + 1000*z) == Y: 
      ans[0]= x
      ans[1]= y
      ans[2]= z
      break
    else: continue

if ans[0]==-1:print("-1 -1 -1")
else:
  print(f"{ans[0]} {ans[1]} {ans[2]}")




### FIXED CODE ###

N, Y = map(int, input().split())
ans = [-1,-1,-1]
for x in range(N+1):
  for y in range(N+1):
    z = N-x-y
    if z < 0: continue

    if (10000*x + 5000*y + 1000*z) == Y: 
      ans[0]= x
      ans[1]= y
      ans[2]= z
      break
    else: continue

if ans[0]==-1:print("-1 -1 -1")
else:
  print("{} {} {}".format(ans[0],ans[1],ans[2]))
n,t = map(int,input().split())

m = 1001

for i in range(N):
    
    c,t = map(int,input().split())
    
    if t <= T:
        m=min(m,c)
        
print("TLE" if m==1001 else m)



### FIXED CODE ###

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

m = 1001

for i in range(N):
    
    c,t = map(int,input().split())
    
    if t <= T:
        m=min(m,c)
        
print("TLE" if m==1001 else m)
n, a =map(int, input().split())
x=list(map(int, input().split()))
x=[i-a for i in x]
memo=[[-1]*110 for i in range(60)]
def dp(k, value):
    if k==n:
        if value==0:
            return 1
        else:
            return 0
    if memo[k][value]>0:
        return memo[k][value]
    memo[k][value]=dp(k+1, value+x[k])+dp(k+1, value)
    print(memo[k][value], k, value)
    return memo[k][value]
print(dp(0, 0)-1)

### FIXED CODE ###

n, a = map(int, input().split())
x=list(map(lambda x: int(x)-a, input().split()))
k=[[0]*3000 for i in range(60)]
for i in range(3000):
    k[0][i]=0
k[0][x[0]+1500]+=1
k[0][1500]+=1
for i in range(1, n):
    for j in range(3000):
        if 3000>j-x[i]>=0:
            k[i][j]=k[i-1][j-x[i]]+k[i-1][j]
        else:
            k[i][j]=k[i-1][j]
print(k[n-1][1500]-1)
import numpy as np
N = int(input())
a = np.array(list(map(int, input().split())))
l = 0
n = 1
b = 0
g = np.zeros(N+1)
g[0] = 1-a[0]
for i in range(N+1):
    if a[i] < 0:
        l = -1
for i in range(1, N+1):
    g[i] = (g[i-1]-a[i-1])*2
    if g[i] <= 0:
        l = -1
g[N] = a[N]
for i in range(1, N+1):
    if l<0:
        break
    b = N-i
    if g[b] > g[b+1]+a[b]:
        g[b] = g[b+1]+a[b]
    if g[b] <= 0:
        l = -1
        break
if a[0] != 0 or l == -1:
    print(-1)
else:
    print(int(sum(g)))

### FIXED CODE ###

import numpy as np
h1, m1, h2, m2, k = np.array(list(map(int, input().split())))
h = h2 - h1
m = m2-m1
t = h*60 + m
print(t-k)
import math
N = int(input())
for i in range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = math.ceil(x/a)
    yb = math.ceil(y/b)
    c = max(xa,yb)
    x,y = a*c,b*c
print(x+b)

### FIXED CODE ###

N = int(input())
for i in range(N):
  a,t = map(int,input().split())
  if i == 0:
    x,y = a,t
  else:
    xa = x//a if x%a==0 else x//a+1
    yt = y//t if y%t==0 else y//t+1
    c = max(xa,yt)
    x,y = a*c,t*c
print(x+y)
H,W=map(int,input().split())
S=["."+input()+"." for i in range(H)]
S=["."*(W+2)]+S+["."*(W+2)]

flag=0

for k in range(1,H+1):
    for j in range(1,W+1):
        if field[k][j]=='#' and field[k-1][j]!='#' and field[k+1][j]!='#' and field[k][j-1]!='#' and field[k][j+1]!='#':
            flag=1

if flag==1:
    print('No')
else:     
    print('Yes')

### FIXED CODE ###

H,W=map(int,input().split())
S=["."+input()+"." for i in range(H)]
field=["."*(W+2)]+S+["."*(W+2)]

flag=0

for k in range(1,H+1):
    for j in range(1,W+1):
        if field[k][j]=='#' and field[k-1][j]!='#' and field[k+1][j]!='#' and field[k][j-1]!='#' and field[k][j+1]!='#':
            flag=1

if flag==1:
    print('No')
else:     
    print('Yes')
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define FOR(i,a,b) for(ll i=a;i<b;i++)
#define rep(i,n) FOR(i,0,n)
const ll INF = 9223372036854775807;

int main() {
  string s;cin >> s;
  vector<char> t(0);
  rep(i,s.size()) t.push_back(s.at(i));
  vector<char> u(0);
  rep(i,s.size()) u.push_back(s.at(i));
  int nD = 0;
  rep(i,t.size()) if(t.at(i) != 'P') nD++;
  rep(i,t.size()) {
    if(t.at(i) == '?') {
      if(i<(t.size()-1)) {
        if(t.at(i+i) == 'D') t.at(i) = 'P';
        else t.at(i) = 'D';
      }else t.at(i) = 'D';
    }
  }
  int nDPD = 0;
  string Ans = "";
  rep(i,t.size()) if(t.at(i) != 'P') nDPD++;
  rep(i,t.size()-1) if(t.at(i) == 'P') if(t.at(i+1) == 'D') nDPD++;
  if(nD > nDPD) {
    rep(i,u.size()) if(u.at(i) == '?') u.at(i) = 'D';
    rep(i,u.size()) Ans += u.at(i);
    cout << Ans << endl;
  }else{
    rep(i,t.size()) Ans += t.at(i);
    cout << Ans << endl;
  }
}

### FIXED CODE ###

import sys
import math
import itertools
import collections
import heapq
import numpy as np

rl = sys.stdin.readline

t = rl()
li = []
for i in range(len(t)):
    if t[i] == '?':
        li.append('D')
    else:
        li.append(t[i])
print(''.join(li))
N = map(int,input().split())
fizz = list()
for i in range(N):
    if i // 3 = 0 and i // 5 = 0:
        i = FizzBuzz
    elif i // 3 = 0 
        i = Fizz
    elif i // 5 = 0
        i = Buzz
    else:
        fizz.append(i)
print(sum(fizz))

### FIXED CODE ###

N = int(input())
a = 0
for i in range(N+1):
    if i % 3 != 0 and i % 5 != 0:
        a += i
print(a)
C11,C12,C13 = map(int, input().split())
C21,C22,C23 = map(int, input().split())
C31,C32,C33 = map(int, input().split())

print(C11+C22+C33)


### FIXED CODE ###

a = input()
b = input()
c = input()

print(a[0]+b[1]+c[2])
a = p.strip()
l = a.split()
m = l.pop(0)
print(len(set(l))


### FIXED CODE ###


a = int(input())
l = [input() for i in range(a)]
print(len(set(l)))
a,b,c=map(int,input().split())
if c-a-b<0:
    print('No')
else:
    if ab<(c-b-a)*(c-b-a)
        print('Yes')
    else:
        print('No')

### FIXED CODE ###

a,b,c=map(int,input().split())
if c-a-b<0:
    print('No')
else:
    if 4*a*b<(c-b-a)*(c-b-a):
        print('Yes')
    else:
        print('No')
from mypulp import *

model = Model('aaa')
a=[int(i) for i in input().split()]
b=[input().split() for i in range(a[1])]
x={}
for j in range(1,a[1]+1):
    x[j]=model.addVar(vtype='I',name=f'x({j})')
model.update()
model.addConstr(quicksum(int(b[j-1][0])*x[j] for j in range(1,a[1]+1))>=a[0])
a=quicksum(int(b[j-1][1])*x[j] for j in range(1,a[1]+1))
model.setObjective(a, GRB.MINIMIZE )
model.optimize()
print(int(model.ObjVal)) 


### FIXED CODE ###

H, N = map(int, input().split())
da, cost = [0] * N, [0] * N
for i in range(N):
    da[i],cost[i]=map(int, input().split())

max_da=max(da) 
dp = [float("inf") for i in range(H+max_da)]
dp[0]=0

for i in range(H+max_da):
    for j in range(N):
        if i-da[j]>=0:
            dp[i]=min(dp[i],dp[i-da[j]]+cost[j])

print(min(dp[H:]))
n,a,b=map(int,input().split())
if (b-a)%2==0:
    print((b-a)//2)
else:
    print(min(a-1,n-B)+1+(b-a-1)//2)


### FIXED CODE ###

n,a,b=map(int,input().split())
if (b-a)%2==0:
    print((b-a)//2)
else:
    print(min(a-1,n-b)+1+(b-a-1)//2)
N = input()
dp = [0] * (87)
dp[0] = 2
dp[1] = 1
for i in range(2, N+1):
  dp[i] = dp[i-1] + dp[i-2]
print(dp[N])

### FIXED CODE ###

N = int(input())
dp = [0] * (87)
dp[0] = 2
dp[1] = 1
for i in range(2, N+1):
  dp[i] = dp[i-1] + dp[i-2]
print(dp[N])
X = int(input())
num = []
for i in range(1,X):
  temp = i**2
  if temp<=X:
    num.append(temp)
    
print(num[-1])

### FIXED CODE ###

X = int(input())
num = [1]
for i in range(2,X):
  temp = i
  while temp*i<=X:
    temp=temp*i
    num.append(temp)
    
print(sorted(num)[-1])
a, b = map(int(int, input().split()))
print(max([a+b,a-b,a*b]))

### FIXED CODE ###

a, b = map(int, input().split());print(max(a+b,a-b,a*b))
x,y=map(int,input().split())
if x=0:print(abs(y)+(y<0))
elif y=0:print(abs(x)+(x>0))
elif 0<x<y or x<y<0:print(abs(y-x))
elif 0<y<x or y<x<0:print(2+abs(x-y))
else:print(abs(abs(x)-abs(y))+1)

### FIXED CODE ###

x,y=map(int,input().split())
if x==0:print(abs(y)+(y<0))
elif y==0:print(abs(x)+(x>0))
elif 0<x<y or x<y<0:print(abs(y-x))
elif 0<y<x or y<x<0:print(2+abs(x-y))
else:print(abs(abs(x)-abs(y))+1)
X, Y = map(int, input())
print(X + Y/2)

### FIXED CODE ###

X, Y = map(int, input().split())
print(int(X + Y/2))
n=int(input())
edge=[[]for _ in range(n)]
for i in range(n-1):edge[int(input())-1].append(i+1)
def dfs(v):
  d=[-1]+sorted([dfs(i)for i in edge[v]])
  l=len(d)
  return max(l-i+j for i,j in enumerate(d))
print(dfs(0))

### FIXED CODE ###

import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**6)
n=int(input())
a=[int(input())for _ in range(n-1)]
def dfs(v):
  d=[dfs(i)for i in t[v]]
  d.sort()
  l=len(d)
  ans=0
  for i,j in enumerate(d):
    ans=max(ans,l-i+j)
  return ans
t=[[]for _ in range(n+1)]
for i in range(n-1):
  t[a[i]-1].append(i+1)
print(dfs(0))
N=int(input())

if (N%4)==0:
    print("Yes")
    break
elif(N%7)==0:
    print("Yes")
    break
elif(N%11)==0:
    print("Yes")
    break
while N>0:
    i=1
    N=N-11*i
    if(N%4)==0 or (N%7)==0:
        print("Yes")
        break
    i=i+1
else:
    print("No")

### FIXED CODE ###

N=int(input())

if (N%4)==0:
    print("Yes")
elif(N%7)==0:
    print("Yes")
elif(N%11)==0:
    print("Yes")
elif(1):
    while N>0:
        i=1
        N=N-11*i
        if(N<0):
            print("No")
            break
        if(N%4)==0 or (N%7)==0:
            print("Yes")
            break
        i=i+1
N, K = map(int, input().split())

if N <= K:
    print(-1)
else:
    M = N * (N - 1) // 2 - K
    cnt = 0
    ans = []
    for i in range(N - 1):
        for j in range(i + 1, N):
            ans.append((i + 1, j + 1))
            cnt += 1
            if M == cnt:
                break
        else:
            continue
        break

print(M)
for edge in ans:
    print(*edge)


### FIXED CODE ###

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

if K > (N - 1) * (N - 2) // 2:
    print(-1)
else:
    M = N * (N - 1) // 2 - K
    cnt = 0
    ans = []
    for i in range(N - 1):
        for j in range(i + 1, N):
            ans.append((i + 1, j + 1))
            cnt += 1
            if M == cnt:
                break
        else:
            continue
        break
    print(M)
    for edge in ans:
        print(*edge)
n,k=map(int,input().split())
lists=[]
for _ in range(k):
  d=input()
  list=list(map(int,input().split()))
  lists.append(list)
ans=[0]*n
for list in lists:
  for i in range(1,len(list)+1):
    ans[i-1]+=1
count=0
for h in ans:
  if h==0:
    count+=1
print(count)

### FIXED CODE ###

n,k=map(int,input().split())
lists=[]
for _ in range(k):
  d=int(input())
  lis=list(map(int,input().split()))
  lists.append(lis)
ans=[0]*n
for list in lists:
  for i in range(len(list)):
    ans[list[i]-1]+=1
count=0
for h in ans:
  if h==0:
    count+=1
print(count)
R, G=map(int,input().split())
print(2*G-R)

### FIXED CODE ###

r=int(input())
g=int(input())
print(2*g-r)
import math
import sys

n, m = map(int, input().split())
a = list(map(int, input().split()))

def f(x):
    res = 0
    while x % 2 == 0:
        x/= 2
        res += 1
    return res

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

for i in range(n):
    a[i] //= 2

t = f(a[0])

ans = 0
for i in range(n):
    if f(a[i] != t):
        print(0)
        sys.exit(0)
    a[i] >>= t

m >>= t

l = 1
for i in range(n):
    l = lcm(l, a[i])
    if l > m:
        print(0)
        sys.exit(0)

m //= l
ans = (m + 1)//2
print(ans)


### FIXED CODE ###

n, m = map(int, input().split())
a = list(map(int, input().split()))

def f(x):
    res = 0
    while x % 2 == 0:
        x//= 2
        res += 1
    return res

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

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

for i in range(n):
    a[i] //= 2

t = f(a[0])

ans = 0
for i in range(n):
    if f(a[i]) != t:
        print(0)
        exit()
    a[i] >>= t

m >>= t

l = 1
for i in range(n):
    l = lcm(l, a[i])
    if l > m:
        print(0)
        exit()

m //= l
ans = (m + 1)//2
print(ans)
def fib_memo(n):
    """メモ化フィボナッチ"""
    memo = [0]*(n+1)

    def _fib(n):
        if n <= 1:
            return n
        if memo[n] != 0:
            return memo[n]
        memo[n] = _fib(n-1) + _fib(n-2)
        return memo[n]

    return _fib(n)
  
N, M = map(int, input().split())
A = list(map(int, input().split()))
B = [0]*(M-1)
for i in range(M):
  diff = 0
  if i == 0:
    diff = A[i] - 1
    B[0] = fib_memo(diff + 1)
  else if i == (M - 1):
    diff = N - A[M-1] -1
    B[M-1] = fib_memo(diff + 1)
  else:
    diff = A[i] - A[i-1]
    B[i] = fib_memo(diff + 1)
Ans = reduce(lambda a, b: a*b, array)
print(Ans % 1000000007)
    
    

### FIXED CODE ###

N, M = map(int, input().split())
A = [True] * (N+1)
for _ in range(M):
  idx = int(input())
  A[idx] = False

step = [0] * (N+1)
step[0] = 1
for i in range(1, N+1):
  if A[i]:
    step[i] = step[i-1] + step[i-2]
  else:
    step[i] = 0
print(step[N]%(10**9+7))
n,k=input().split(" ")
n=int(n)
k=int(k)
arr=[0]+[int(i) for i in input().split(" ")]
dp=[0]*(n+1)
for i in range(n-1,0,-1):
    min1=1000000007;
    for j in range(i+1,min(n+1,i+k+1)):
        x=dp[j]+abs(arr[i]-arr[j])
        if(x<min1):
            min1=x
    dp[i]=min1
print(dp[1])


### FIXED CODE ###

n=int(input())
arr=[]
arr=[0]+[int(i) for i in input().split(" ")]
dp=[0]*(n+1)
dp[n]=0
dp[n-1]=abs(arr[n-1]-arr[n])
for i in range(n-2,0,-1):
    dp[i]=min( dp[i+1]+abs(arr[i]-arr[i+1]) , dp[i+2]+abs(arr[i]-arr[i+2]) )
print(dp[1])
a=input()
b=int(input())
c=0
if a[0]!="1":
  print(a[0])
if a[0]=="1":
  for i in range(len(a)-1):
    if a[i]==1 and a[i+1]==1:
      c=c+1
    else:
      break
  if c>=b:
    print(1)
  else:
    print(a[1])

### FIXED CODE ###

a=input()
b=int(input())
c=1
if a[0]!="1":
  print(a[0])
if a[0]=="1":
  for i in range(len(a)-1):
    if a[i]=="1" and a[i+1]=="1":
      c=c+1
    else:
      break
  if c>=b:
    print(1)
  else:
    print(a[c])
from collections import deque

n, m = map(int, input().split())
G = [list() for _ in range(n)]
for _ in range(m):
  a, b = map(int, input().split())
  a -= 1; b -= 1
  G[a].append(b)
  G[b].append(a)
Q = int(input())
queries = [tuple(map(int, input().split())) for _ in range(Q)][::-1]
dp = [[Q]*n for _ in range(n)]
for i, (v, d, _) in enumerate(queries):
  dp[v-1][d] = i
for d in range(10, 0, -1):
  for v in range(n):
    if dp[v][d] < Q:
      dp[v][d-1] = min(dp[v][d-1], dp[v][d])
      for x in G[v]:
        dp[x][d-1] = min(dp[x][d-1], dp[v][d])
queries.append((-1, -1, 0))
color = [queries[dp[v][0]][2] for v in range(n)]
print(*color, sep='\n')

### FIXED CODE ###

import sys

readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: map(int, readline().split())
nl = lambda: list(map(int, readline().split()))

def solve():
  n, m = nm()
  G = [list() for _ in range(n)]
  for _ in range(m):
    a, b = nm()
    a -= 1; b -= 1
    G[a].append(b)
    G[b].append(a)
  Q = int(input())
  queries = [tuple(nm()) for _ in range(Q)][::-1]
  dp = [[Q]*11 for _ in range(n)]
  for i in range(Q-1, -1, -1):
    v, d, _ = queries[i]
    dp[v-1][d] = i
    
  for d in range(10, 0, -1):
    for v in range(n):
      for x in G[v] + [v]:
        if dp[x][d-1] > dp[v][d]:
          dp[x][d-1] = dp[v][d]
          
  queries.append((-1, -1, 0))
  color = [queries[dp[v][0]][2] for v in range(n)]
  print(*color, sep='\n')
  return

solve()