Harryxun/stf_run huggingface dataset:
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline

MAXN = 1005
MAXV = MAXN*(MAXN-1)//2

to = [[] for _ in range(MAXV)]
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)]

def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXN
dp = [1] * MAXV

def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1

    for u in to [v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]

def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n-2):
            to[a[i][j+1]].append(a[i][j])
    ans = 0
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1')
            return
        ans = max(ans, res)
    print(ans)
    return
if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
MAXN = 1005
MAXV = MAXN*(MAXN-1)//2
 
to = [[] for _ in range(MAXV)]
id = [[[] for _ in range(MAXN)] for _ in range(MAXN)]
 
def toId(i, j):
    if i > j:
        i, j = j, i
    return id[i][j]
visited = [False] * MAXV
calculated = [False] * MAXV
dp = [1] * MAXV
 
def dfs(v):
    if visited[v]:
        if not calculated[v]:
            return -1
        return dp[v]
    visited[v] = True
    dp[v] = 1
 
    for u in to[v]:
        res = dfs(u)
        if res == -1: return -1
        dp[v] = max(dp[v], res+1)
    calculated[v] = True
    return dp[v]
 
def main():
    n = int(input())
    a = [[int(i) for i in readline().split()] for _ in range(n)]
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] -= 1
    V = 0
    for i in range(n):
        for j in range(n):
            if i < j:
                id[i][j] = V
                V += 1
    
    for i in range(n):
        for j in range(n-1):
            a[i][j] = toId(i, a[i][j])
        for j in range(n-2):
            to[a[i][j+1]].append(a[i][j])
    
    ans = 0
    
    for i in range(V):
        res = dfs(i)
        if res == -1:
            print('-1')
            return
        ans = max(ans, res)
    print(ans)
    return
  
if __name__ == '__main__':
    main()
H, W = map(int,input().split())

s = []
for i in range(H):
    ss = input()
    s.append(ss)

shift = [[1,0],[-1,0],[0,1],[0,-1]]

for j in range(H):
    for i in range(W):
        if s[j][i] == "#":
            flag = False
            for dx, dy in shift:
                nx = i + dx
                ny = j + dy
                if nx >= 0 and nx < W and ny >= 0 and ny < H:
                    if s[ny][nx] == "#":
                        flag = True
            if not flag:
                exit(0)

if flag:
    print("Yes")
else:
    print("No")


### FIXED CODE ###

H,W = map(int,input().split())
s = []
for _ in range(H):
    s.append(input())

shift = [[1,0],[-1,0],[0,-1],[0,1]]

flag = True
for j in range(H):
    for i in range(W):
        if s[j][i] == ".":
            continue
        else:
            flag = False
            for dx,dy in shift:
                nx = i + dx
                ny = j + dy
                
                if nx >= 0 and nx < W and ny >= 0 and ny < H:
                    if s[ny][nx] == "#":
                        flag = True
            if not flag:
                print("No")
                exit(0)

print("Yes")
from itertools import *
from collections import *
from bisect import *


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

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=31
for i in range(len(nlst)):
    a=bin(nlst[i])[2:]
    nlst[i]=[0 for i in range(lenbin-len(a))]+list(map(int,list(a)))
    #print(nlst[i])
lenbinst=0
print(unko)
#print(nlst)
use=set([i for i in range(len(nlst))])
while lenbinst<lenbin:
    idx=-1
    count=0
    dellst=set()
    for m in use:
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        if len(nlst)!=count:
            for m in use:
                if nlst[m][lenbinst]!=1:
                    dellst.add(m)
    use=use-dellst
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]
nlst=[nlst[i] for i in use]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)


### FIXED CODE ###

from itertools import *
from collections import *
from bisect import *
N,K=map(int,input().split())
A=list(map(int,input().split()))

ruiA=[0 for i in range(N+1)]
for i in range(0,N):
    ruiA[i+1]=ruiA[i]+A[i]


nlst=[]

for i in range(len(ruiA)-1):
    for m in range(i+1,len(ruiA)):
        nlst.append(ruiA[m]-ruiA[i])
nlst.sort(reverse=True)

lenbin=60
for i in range(len(nlst)):
    lst=[]
    for m in range(lenbin):
        lst.append((nlst[i]>>m)&1)
    nlst[i]=list(reversed(lst))
lenbinst=0

use=set([i for i in range(len(nlst))])
while lenbinst<lenbin:
    idx=-1
    count=0
    dellst=set()
    for m in use:
        if nlst[m][lenbinst]==1:
            count+=1
    if count>=K:
        if len(nlst)!=count:
            for m in use:
                if nlst[m][lenbinst]!=1:
                    dellst.add(m)
    use=use-dellst
    lenbinst+=1
valuelst=[0 for i in range(lenbin)]
nlst=[nlst[i] for i in use]

for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1

for i in range(lenbin):
    if valuelst[i]>=K:
        newlst=[i for i in nlst if i[idx]==1]
        if len(newlst)>=K:
            nlst=newlst

valuelst=[0 for i in range(lenbin)]
for n in nlst:
    for i,a in enumerate(list(reversed(n))):
        if a:
            valuelst[i]+=1
value=0
for i in range(lenbin):
    if valuelst[i]>=K:
        value+=2**i
print(value)
import sys
input = sys.stdin.readline

N, C = map(int, input().split())
STC = [tuple(map(int, input().split())) for _ in range(N)]
STC.sort(reverse=True, key=lambda x: x[1])  # tを基準に降順ソート

record = []
while STC:
    s_now, t_now, c_now = STC.pop()

    for i in range(len(record)):
        t, s, c = record[i]
        if c == c_now:
            record[i] = (t_now, s_now, c_now)
            break
        elif s_now > t:
            record[i] = (t_now, s_now, c_now)
            break
    else:
        record.append((t_now, s_now, c_now))

    ans = max(ans, len(record))

print(len(ans))


### FIXED CODE ###

N, C = map(int, input().split())
tmp = []

for _ in range(N):
    s, t, c = map(int, input().split())
    tmp.append((s, t, c))
tmp.sort()

# そもそもCが小さいから力技で行けるはず
video = [(0, 0)]  # t,c
for s, t, c in tmp:
    for i, v in enumerate(video):
        ti, ci = v
        if c == ci:
            video[i] = (t, c)
            break
        if s > ti:
            video[i] = (t, c)
            break
    else:
        video.append((t, c))
    video.sort(reverse=True)

ans = len(video)
print(ans)
# AOJ ITP1_4_D: Min, Max and Sum
# 2018.6.7 bal4u
#

n = input()
data = list(map(int, input().split()))   # 1行にある複数の値を整数にして、リストにしまう
#
vmin = min(data)  # 最小値
vmax = max(data)  # 最大値
vsum = sum(data)  # 合計
#
print(vmin, vmax, vsum)  # 結果表示


### FIXED CODE ###

# AOJ ITP1_4_D: Min, Max and Sum
# Python3 2018.6.7 bal4u

n = int(input())
data = list(map(int, input().split()))   # 1行にある複数の値を整数にして、リストにしまう
#
vmin = min(data)  # 最小値
vmax = max(data)  # 最大値
vsum = sum(data)  # 合計
#
print(vmin, vmax, vsum)  # 結果表示
import math
n = int(input())
ans = int(input())
for i in range(n-1):
    a = int(input())
    ans = ans // math.gcd(ans,a) * a
print(ans)

### FIXED CODE ###

import fractions
n = int(input())
ans = 1
for i in range(n):
    a = int(input())
    ans = ans // fractions.gcd(ans,a) * a
print(ans)
n, q = map(int, input().split())
connect = {a:[] for a in range(1,n+1)}
ans = [0]*n

for _ in range(n-1):
    a, b = map(int, input().split())
    connect[a].append(b)

def d(p, x):
    ans[p-1] += x
    for b in connect[p]:
        d(b, x)
        
for _ in range(q):
    p, x = map(int, input().split())
    d(p, x)
    
print(*ans)

### FIXED CODE ###

from queue import deque


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

graph = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    graph[a].append(b)
    graph[b].append(a)

C = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    C[p - 1] += x

P = [-1] * N

root = 0
q = deque([root])
while q:
    x = q.popleft()
    for y in graph[x]:
        if y == P[x]:
            continue
        C[y] += C[x]
        q.append(y)
        P[y] = x

print(*C)
n,k=input().split()
N=int(n)
K=int(k)
print(k*(k-1)**(n-1))

### FIXED CODE ###

n,k=input().split()
N=int(n)
K=int(k)
print(K*((K-1)**(N-1)))
a,b = map(int,input().split())
import fraction
g = fraction.gcd(a,b)

print(round(a*b/g))

### FIXED CODE ###

a,b = map(int,input().split())
import fractions
g = fractions.gcd(a,b)

print(round(a*b/g))
import numpy as np

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

ans = np.lcm(a,b)

print(int(ans))


### FIXED CODE ###

from fractions import gcd
a, b = map(int, input().split())

print(a*b//gcd(a,b))
N,A,B = map(int,input().split())
D  = A*N

if D>B:
    print(D)
else: 
    print(G)

### FIXED CODE ###

N,A,B = map(int,input().split())
D  = A*N
if D>B:
    print(B)
else: 
    print(D)
a,b=int(input().split())
print("error" if a+b > 10 else a+b)

### FIXED CODE ###

a,b=map(int,input().split())
print("error" if a+b >= 10 else a+b)
N,K,Q = map(int, input().split()))
 
A = []
 
for _ in range(Q):
    A.append(int(input()))
	
P = [K] * N
 
r = 0
 
for i in range(0,len(A)):
	r = A[i] - 1
	P[r] += 1
	P = list(map(lambda x: x-1,P))
	
for i in range(0,len(P)):
	if P[i] > 0:
		print("Yes")
	else:print("No")

### FIXED CODE ###

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

P = [0] * N


for i in range(Q):
	A = int(input())
	P[A-1] += 1


for j in range(0,len(P)):
	if K - Q + P[j] > 0:
		print('Yes')
	else:
		print('No')
H,W=map(int,input().split())
a=[]
for i in range(H):
    a.append(map(int,input().split()))

for i in range(0,W+2):
    print("#",end="")
print()

for i in a:
    print("#",end="")
    for j in i:
        print(j,end="")
    print("#")

for i in range(0, W+2):
      print("#",end="")
print()

### FIXED CODE ###

H,W=map(int,input().split())
a=[]
for i in range(H):
    a.append(map(str,input().split()))

for i in range(0,W+2):
    print("#",end="")
print()

for i in a:
    print("#",end="")
    for j in i:
        print(j,end="")
    print("#")

for i in range(0, W+2):
      print("#",end="")
print()
#input
S = input()

#output
N = len(S)
k = N//2
l = (N-3)//4
m = (3*N-1)//4
if N == 3:
    if S[0] == S[3]:
        print("Yes"):
    else:
        print("No"):
else:
    if (S[0:k] == S[-1:k:-1] )and (S[0:l] == S[(N-3)//2:l:-1]) and (S[(N+1)//2:m] == S[N-1:m:-1]):
        print("Yes")
    else:
        print("No")

### FIXED CODE ###

#input
S = input()

#output
N = len(S)

if (S == S[::-1]) and (S[:(N-1)//2] == S[:(N-1)//2][::-1]) and (S[(N+3)//2-1:] == S[(N+3)//2-1:][::-1]):
    print("Yes")
else:
    print("No")
antena = [int(input()) for _ in range(5)]
k = int(input())

flg = True
for i in range(len(antena)):
  for j in range(len(antena)):
    if a[i] - a[j] > k:
      flg = False
      break
    
if flg:
  print('Yay!')
else:
  print(':(')



### FIXED CODE ###

antena = [int(input()) for _ in range(5)]
k = int(input())

flg = True
for i in range(len(antena)):
  for j in range(len(antena)):
    if antena[i] - antena[j] > k:
      flg = False
      break
    
if flg:
  print('Yay!')
else:
  print(':(')
n,m=map(int,input().split())
a=[]

for i in range(m):
  b=int(input())
  a.append(b)
    
def count(x):
    if x==-1:
        return 0
    elif x==0:
        return 1
    elif x in a:
        return 0
    else:
        return (count(x-2)+count(x-1))%1000000007
    
print(count(n))

### FIXED CODE ###

n,m=map(int,input().split())
mod=10**9+7
a = [int(input()) for i in range(m)]
block=[0,1]
x=[True for i in range(n)]
for j in a:
  x[j-1]=False

for i in range(1,n+1):
  if x[i-1]==False:
    block=block[1:]+[0]
  else:
    block=block[1:]+[sum(block)%mod]
print(block[-1])
number, base = map(int, input().split())
result_list = []
while number / base > 0:
  mod = number % base
  result_list.append(str(mod))
  number = number // base

result_list.reverse()
result = "".join(result_list)
print(len(result))


### FIXED CODE ###

count, outrate = map(int, input().split())

if count >= 10:
  result = outrate
  print(result)
else:
  result = outrate + 100 * (10 - count)
  print(result)
def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    ans = []
    for i, a in enumerate(A[::-1]):
        i = n - i
        b = sum(B[i - 1::i])
        if b % 2 != a:
            ans.append(str(i))
            B[i] = 1
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n = int(input())
    A = list(map(int, input().split()))
    B = [0] * n
    ans = []
    for i, a in enumerate(A[::-1]):
        i = n - i
        b = sum(B[i - 1::i])
        if b % 2 != a:
            ans.append(str(i))
            B[i - 1] = 1
    print(len(ans))
    print(' '.join(ans))

if __name__ == '__main__':
    main()
n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**4+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)

    
    

### FIXED CODE ###

n, m = map(int,input().split())
B = [list(map(int,input().split())) for i in range(n)]

C = [[] for i in range(10**5+10)]

for i in range(n):
    C[B[i][0]].append(B[i][1])
for i in range(len(C)):
    C[i].sort(reverse=1)

#print(C[:10])
notst=1
st=0
ans = 0

Bl = [0 for i in range(10**4+2)]
for i in range(1, m+1):
    for j in range(len(C[i])):
        Bl[C[i][j]] += 1
    if notst == 1 and len(C[i]) > 0:
        notst = 0
        st = C[i][0]
    if notst == 0 and len(C[i]) > 0:
        if st < C[i][0]:
            st = C[i][0]
    while st > 0 and Bl[st] == 0:
        st -= 1
    ans += st
    # print(ans)
    # print(Bl[:10])
    Bl[st] -= 1

print(ans)
words = {"dream": "A", "dreamer": "A", "erase": "A", "eraser": "A"}

ans = []

inputs = list(input())

tmp1 = []

for c in reversed(inputs):
  
  tmp1.append(c)
  
  tmp2 = "".join([x for x in reversed(tmp1)])
  
  if tmp2 in words:
    ans.append("".join(tmp2))
    tmp1.clear()
    tmp2.clear()

ans = [x for x in reversed(ans)]

if "".join(ans) == "".join(inputs):
  print("YES")
else:
  print("No")

### FIXED CODE ###

words = {"dream": "A", "dreamer": "A", "erase": "A", "eraser": "A"}
 
ans = []
 
inputs = str(input())
 
inputs = inputs.replace("eraser", "").replace("erase", "").replace("dreamer", "").replace("dream", "")

if len(list(inputs)) > 0:
  print("NO")
else:
  print("YES")
from math import factorial

s = int(input())
 
ans = 0
for i in range(s // 3):
    box = i + 1  # 箱の数
    ball = s - 3 * box # あらかじめ箱に３こずつ入れたあとの残りの玉の数

　　# 箱の入れ方が何通りあるか計算。
    # 割り算を // ではなく / とするとfloat型の計算となりオーバーフローする可能性がある。
    # factorial(s_ + i) // (factorial(s_) * factorial(i))ではなくfactorial(s_ + i) // (factorial(s_) // factorial(i))としても同様にオーバーフローする可能性がある。
    ans += factorial(s_ + i) // (factorial(s_) * factorial(i)) % (10**9 + 7)

print(ans % (10 ** 9 + 7))

### FIXED CODE ###

s = int(input())

x = s // 3

def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result

ans = 0
for i in range(x):
    Box = i + 1
    Nokori = s - 3 * Box
    ans_ = cmb(Nokori + Box - 1, Box - 1) 
    ans += ans_
print(ans % (10 ** 9 + 7))
n,k = map(int,input().split())

x = [n-k*i for i in range(n//k+2)]
x[-1] = abs(x[-1])
print(min(x))

### FIXED CODE ###

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

a1 = b
b1 = a

c1 = a1
a2 = c

print(a2,b1,c1)
import collections
n,k = map(int,input().split())
if k > n+1 and k != (n-1)*(n-2)//2:
    print(-1)
elif k == 0:
    if n == 2:
        print(1,2)
    else:
        print(-1)  
else:
    if k == (n-1)*(n-2)//2:
        print(n-1)
        for i in range(2,n+1):
            print(1,i)
    else:
        L = collections.deque()
        for i in range(3,n):
            L.append([1,i])
        for i in range(2,n-1):
            for j in range(i+2,n+1):
                L.append([i,j])
        for i in range(k):
            L.popleft()
        if k != n+1:
            print(len(L)+n)
            for i in range(len(L)):
                print(L[i][0],L[i][1])
            for i in range(n-1):
                print(i+1,i+2)
            for i in range(1):
                print(n,1)

### FIXED CODE ###

n,k = map(int,input().split())
if k > (n-1)*(n-2)/2:
    print(-1)
else:
    ans = []
    for i in range(1,n):
        ans.append([1,i+1])
    L = []
    for i in range(2,n+1):
        for j in range(i+1, n+1):
            L.append([i,j])
    for i in range((n-1)*(n-2)//2-k):
        ans.append(L[i])
    print(len(ans))
    for i in range(len(ans)):
        print(ans[i][0], ans[i][1])
A, B = map(int, input().split())

white = '.'
black = '#'
grid = [[black * 100] for i in range(50)] + [[white * 100] for i in range(50)]

for i in range(A-1):
    grid[(i % 50) * 2][0] = grid[(i % 50) * 2][0][:(i % 50) * 2] + white + grid[(i % 50) * 2][0][(i % 50) * 2 + 1:]

for i in range(B-1):
    grid[(i % 50) * 2+49][0] = grid[(i % 50) * 2+49][0][:(i % 50) * 2] + black + grid[(i % 50) * 2+49][0][(i % 50) * 2 + 1:]

print(100, 100)
for g in grid:
    print(g[0])

### FIXED CODE ###

A, B = map(int, input().split())

white = '.'
black = '#'
grid = [[black * 100] for i in range(50)] + [[white * 100] for i in range(50)]

for i in range(A-1):
    grid[(i // 50)*2][0] = grid[(i // 50)*2][0][:(i % 50) * 2] + white + grid[(i // 50)*2][0][(i % 50) * 2 + 1:]

for i in range(B-1):
    grid[(i // 50)*2 + 51][0] = grid[(i // 50)*2 + 51][0][:(i % 50) * 2] + black + grid[(i // 50)*2 + 51][0][(i % 50) * 2 + 1:]

print(100, 100)
for g in grid:
    print(g[0])
X = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

for i in range(len(make_divisors(X))):
    A = make_divisors(X)[i]
    for j in range(-int(X**(1/5)),int(X**(1/5))+1):
        if (A+j)**5-j**5==X:
            a = j + A
            b = j
            break
        else:
            continue
        break
    else:
        continue
    break
print(a,b)
    

### FIXED CODE ###

X = int(input())
def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

for i in range(len(make_divisors(X))):
    A = make_divisors(X)[i]
    for j in range(-64,119):
        if (A+j)**5-j**5==X:
            a = j + A
            b = j
            break
        else:
            continue
        break
    else:
        continue
    break
print(a,b)
A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if A < B:
    if (A+V*T >= B+ W*T):
        print("YES")
    else:
        print("NO")
else:
     if (A+V*T <= B+ W*T):
        print("YES")
    else:
        print("NO")

### FIXED CODE ###

A, V = map(int, input().split())
B, W = map(int, input().split())
T = int(input())

if A < B:
    if (A+V*T >= B+ W*T):
        print("YES")
    else:
        print("NO")
else:
    if (A-V*T <= B - W*T):
        print("YES")
    else:
        print("NO")
def lcm(x, y):
    return (x * y) // math.gcd(x, y)

a,b,c,d = map(int,input().split())
t = 0
l = b-a+1

c_count = (b // c) - ((a-1) // c)

d_count = (b // d) - ((a-1) // d)

cd = c * d
cd_count =  (b // cd) - ((a-1) // cd)

lc = lcm(c,d)
lc_count = (b // lc) - ((a-1) // lc)

print(l-c_count-d_count+cd_count+lc)

### FIXED CODE ###

def gcd(a,b):
	if b == 0:
		return a
	else:
		return gcd(b , a%b)	

a,b,c,d = map(int,input().split())
t = 0
l = b-a+1

c_count = (b // c) - ((a-1) // c)

d_count = (b // d) - ((a-1) // d)

lc = (c*d) // gcd(c,d)
lc_count = (b // lc) - ((a-1) // lc)

print(l-c_count-d_count+lc_count)
value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 1)

for i in range(m+1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)


### FIXED CODE ###


value_index = dict()
n, x, m = map(int, input().split())
a = [0] * (m + 1)
s = [0] * (m + 2)

for i in range(m + 1):
    a[i] = x % m
    s[i+1] = s[i] + a[i]
    if i == n - 1:
        print(s[i+1])
        quit()
    if a[i] in value_index:
        break
    value_index[a[i]] = i
    x = x * x % m

l = value_index[a[i]]
r = i

loop_sum = s[r] - s[l]
loop_n = (n - l) // (r - l)
rem = (n - l) % (r - l)

ans = s[l] + loop_n * loop_sum + s[l+rem] - s[l]
print(ans)
N=int(input())

if  N%2=1:
    print((N//2+1)/N)

else:
    print(1/2)

### FIXED CODE ###

N=int(input())

if  N%2==1:
    print((N//2+1)/N)

else:
    print(1/2)
n,m=map(int,input().split())
a=['.']
a*=n
ans=0
for i in range(m):
    si,ci=input().split()
    si=int(si)
    ci=str(ci)
    if a[si-1]=='.':
        a[si-1]=ci
    else:
        if a[si-1]==ci:
            continue
        else:
            ans=-1
            break

if ans==-1 or (n>=2 and a[0]=='0'):
    print(-1)
else:
    if n==1 and a[0]=='.':
        a[0]=0
    elif a[0]=='.':
        a[0]=1
    for i in range(1,n):
        if a[i]=='.':
            a[i]='0'
    a=''.join(a)
    print(a)

### FIXED CODE ###

n,m=map(int,input().split())
a=['.']
a*=n
ans=0
for i in range(m):
    si,ci=input().split()
    si=int(si)
    ci=str(ci)
    if a[si-1]=='.':
        a[si-1]=ci
    else:
        if a[si-1]==ci:
            continue
        else:
            ans=-1
            break

if ans==-1 or (n>=2 and a[0]=='0'):
    print(-1)
else:
    if n==1 and a[0]=='.':
        a[0]='0'
    elif a[0]=='.':
        a[0]='1'
    for i in range(1,n):
        if a[i]=='.':
            a[i]='0'
    a=''.join(a)
    print(a)