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

from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = []
for i in range(q):
    l, r = list(map(int, input().split()))
    query.append((r, l, i))

query.sort()
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for x in range(q):
    r, l, z = query[x]
    for i in range(right, r):
        if appear[c[i]] != -1:
            bit.add(appear[c[i]]+1, -1)
        appear[c[i]] = i
        bit.add(appear[c[i]]+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

for i in range(q):
    print(ans[i])


### FIXED CODE ###

from bisect import *
import sys
input = sys.stdin.readline
n, q = map(int, input().split())
c = list(map(int, input().split()))
class BIT():
    def __init__(self, n):
        self.size = n
        self.bit = [0] * (n+1)

    def sum(self, i):
        s = 0
        while i > 0:
            s += self.bit[i]
            i -= i & -i
        return s

    def add(self, i, x):
        while i <= self.size:
            self.bit[i] += x
            i += i & -i
query = [list(map(int, input().split()))+[i] for i in range(q)]
query.sort(key = lambda x: x[1])
appear = [-1]*(n+2)
bit = BIT(n)

right = 0
ans = [None]*(q)
for l, r, z in query:
    for i in range(right, r):
        num = appear[c[i]]
        if num != -1:
            bit.add(num+1, -1)
        appear[c[i]] = i
        bit.add(i+1, 1)
    right = r
    ans[z] = bit.sum(r) - bit.sum(l-1)

print(*ans, sep="\n")
### BUGGY CODE ###

#D    高橋君と見えざる手 / An Invisible Hand
N,T = [int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
Max = 1
count = 0
for i in range(N-1,0,-1):
    for j in range(i-1,-1,-1):
        if (A[i]-A[j])>Max:
            Max = A[i]-A[j]
            count = 1
        elif (A[i]-A[j])==Max:
            count +=1

print(count)

### FIXED CODE ###

#D    高橋君と見えざる手 / An Invisible Hand
N,T = [int(i) for i in input().split(" ")]
A=[int(i) for i in input().split(" ")]
Max = 0
count = 1
Min = A[0]
for i in range(N):
    if A[i] <= Min :
        Min = A[i]
    else :
        temp = A[i]-Min
        if temp > Max:
            Max = temp 
            count = 1
        elif temp == Max :
            count += 1
print(count)
### BUGGY CODE ###

N=int(input())
*A,=map(int,input().split())
M=1000*1000*1000+7
S=0
for i in range(N-1):
  for j in range(i+1,N):
    S+=A[i]*A[j]
    
print("{}".format(S%M))




### FIXED CODE ###

N=int(input())
*A,=map(int,input().split())
M=1000*1000*1000+7
S=[0]*N

SS=0
for i in range(N-1,0,-1):
  S[i-1]=A[i]+S[i]
  SS+=A[i-1]*S[i-1]

print("{}".format(SS%M))
### BUGGY CODE ###

N,M = map(int,input().split())
H = list(map(int,input().split()))
A=[]
count = list(range(N))
for i in range(M):
    A.append(sorted(list(map(int,input().split()))))

for j in range(M):
     if H[A[j][0]-1]>H[A[j][1]-1]:
                             if A[j][1]-1 in count:
                                 count.remove(A[j][1]-1)
                             else:
                                 pass
     elif H[A[j][0]-1]<H[A[j][1]-1]:
                              if A[j][0]-1 in count:
                                 count.remove(A[j][0]-1)
                              else:
                                  pass 
     else:
           if A[j][1]-1 in count:
                     count.remove(A[j][1]-1)
           else:
               pass
           if A[j][0]-1 in count:
                     count.remove(A[j][0]-1)
           else:
               pass
print(len(count))                     


### FIXED CODE ###

n,m=map(int,input().split())
h=list(map(int,input().split()))
count=[1]*n
for i in range(m):
  a,b=map(int,input().split())
  if h[a-1]>h[b-1]:
    count[b-1]=0
  elif h[a-1]==h[b-1]:
    count[a-1]=0
    count[b-1]=0
  else:
    count[a-1]=0
print(sum(count))
### BUGGY CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
a = list(map(lambda x: x*(-1), a))

for i in range(m) :
  heapq.heapify(a)
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)

### FIXED CODE ###

import heapq

n,m = map(int, input().split())
a = list(map(int, input().split()))
for i in range(n) :
  a[i] *= -1

heapq.heapify(a)
for i in range(m) :
  at = -1*(-1*heapq.heappop(a)//2)
  heapq.heappush(a, at)

print(sum(a)*-1)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
digit = [0]*60

for i in A:
    b = i
    tmp = 0
    while(b):
        digit[tmp] += b & 1
        tmp += 1
        b >>= 1

ans = 0
for i in range(60):
    ans = (ans + (digit[i]*(N-digit[i]) % mod) * pow(2, i, mod) % mod) % mod

print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
mod = 10**9 + 7
digit = [0]*60

for i in A:
    b = i
    tmp = 0
    while(b):
        digit[tmp] += b & 1
        tmp += 1
        b >>= 1

ans = 0
for i in range(60):
    ans = (ans + (digit[i]*(N-digit[i]) % mod) * pow(2, i, mod) % mod) % mod

print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
while n>=0:
  if n-k<=0:
    print(min(abs(n-k),n))
    break
  n=n-k

### FIXED CODE ###

n,k=map(int,input().split())
print(min(n%k,abs(n%k-k)))
### BUGGY CODE ###

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
#print(S)
dpyoko = [[1]*(W) for i in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            dpyoko[i][j] = 0
        else:
            if j != 0:
                dpyoko[i][j] += dpyoko[i][j-1]
dptate = [[1]*(W) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            dptate[i][j] = 0
        else:
            if i != 0:
                dptate[i][j] += dptate[i-1][j]
#print(dpyoko)
#print(dptate)
for j in range(W-1,-1,-1):
    for i in range(H):
        if dpyoko[i][j] == 0:
            continue
        if j == W-1:
            continue
        dpyoko[i][j] = max(dpyoko[i][j],dpyoko[i][j+1])
#print(dpyoko)
for i in range(H-1,-1,-1):
    for j in range(W):
        if dptate[i][j] == 0:
            continue
        if i == H-1:
            continue
        dptate[i][j] = max(dptate[i][j],dptate[i+1][j])
#print(dptate)
dp = [[0]*(W) for i in range(H)]
res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        dp[i][j] = dptate[i][j]+dpyoko[i][j]-1 
        if res < dp[i][j]:
            res = dp[i][j]
print(res)       


### FIXED CODE ###

H,W = map(int,input().split())
S = [list(input()) for i in range(H)]
#print(S)
dpyoko = [[1]*(W) for i in range(H)]
for j in range(W):
    for i in range(H):
        if S[i][j] == '#':
            dpyoko[i][j] = 0
        else:
            if j != 0:
                dpyoko[i][j] += dpyoko[i][j-1]
dptate = [[1]*(W) for i in range(H)]
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            dptate[i][j] = 0
        else:
            if i != 0:
                dptate[i][j] += dptate[i-1][j]
for j in range(W-1,-1,-1):
    for i in range(H):
        if dpyoko[i][j] == 0:
            continue
        if j == W-1:
            continue
        dpyoko[i][j] = max(dpyoko[i][j],dpyoko[i][j+1])
for i in range(H-1,-1,-1):
    for j in range(W):
        if dptate[i][j] == 0:
            continue
        if i == H-1:
            continue
        dptate[i][j] = max(dptate[i][j],dptate[i+1][j])
dp = [[0]*(W) for i in range(H)]
res = 0
for i in range(H):
    for j in range(W):
        if S[i][j] == '#':
            continue
        dp[i][j] = dptate[i][j]+dpyoko[i][j]-1 
        if res < dp[i][j]:
            res = dp[i][j]
print(res)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
while len(a) > 0:
  m = min(a)
  a = [a[i]%m for i in range(len(a)) if a[i]%m > 0]
  a.append(m)
print(m)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
while len(a) > 1:
  m = min(a)
  a = [a[i]%m for i in range(len(a)) if a[i]%m > 0]
  a.append(m)
print(m)
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))
m = n
q = []

for i in range(n):
    q.append(p[i])
    if not p[i] <= min(q):
        m -= 1

print(m)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))
m = n
q = 2 * (10 ** 5)

for i in range(n):
    q = min(p[i],q)
    if not p[i] <= q:
        m -= 1

print(m)
### BUGGY CODE ###

from collections import deque

n = int(input())
a = deque(map(int, input().split()))
a.appendleft(0)
a.append(0)
a = list(a)
kaisa = deque()
ans = list()

for i in range(len(a)):
    if i == 0:
        continue
    diff = a[i] - a[i - 1]
    kaisa.append(diff)

for i in range(n):
    ans = list(kaisa).copy()
    new_num = kaisa[i] + kaisa[i + 1]
    ans.remove(kaisa[i])
    ans.remove(kaisa[i + 1])
    ans.insert(i, new_num)
    print(sum([abs(n) for n in ans]))


### FIXED CODE ###

from collections import deque

n = int(input())
a = deque(map(int, input().split()))
a.appendleft(0)
a.append(0)

sum = sum([abs(a[i + 1] - a[i]) for i in range(len(a) - 1)])
ans = 0

for i in range(n):
    ans = sum
    ans = ans - abs(a[i + 1] - a[i]) - abs(a[i + 2] - a[i + 1]) + abs(a[i + 2] - a[i])
    print(ans)
### BUGGY CODE ###

from collections import deque

# import sys

# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh, Dw = map(int, input().split())
    Dh -= 1
    Dw -= 1
    S = []
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    for i in range(H):
        S.append(["#", "#"] + list(input()) + ["#", "#"])
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    dist = [[10 ** 18] * (4 + W) for _ in range(H + 4)]
    # print(S, warp)

    def bfs(i, j):
        q = deque()
        q.append((i, j))
        dist[i][j] = 0
        while q:
            a, b = q.popleft()
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if S[a + x][b + y] == ".":
                        warp = abs(x) + abs(y) != 1
                        d = dist[a][b] + int(warp)
                        if d < dist[a + x][b + y]:
                            dist[a + x][b + y] = d
                            if warp:
                                q.append((a + x, b + y))
                            else:
                                q.appendleft((a + x, b + y))
                            # print(q)

    bfs(Ch + 2, Cw + 2)
    if dist[Dh + 2][Dw + 2] == 10 ** 18:
        print(-1)
    else:
        print(dist[Dh + 2][Dw + 2])


if __name__ == "__main__":
    main()


### FIXED CODE ###

from collections import deque

# import sys

# input = sys.stdin.readline
# sys.setrecursionlimit(10 ** 7)


def main():
    H, W = map(int, input().split())
    Ch, Cw = map(int, input().split())
    Ch -= 1
    Cw -= 1
    Dh, Dw = map(int, input().split())
    Dh -= 1
    Dw -= 1
    S = []
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    for i in range(H):
        S.append(["#", "#"] + list(input()) + ["#", "#"])
    S.append(["#"] * (4 + W))
    S.append(["#"] * (4 + W))
    dist = [[10 ** 18] * (4 + W) for _ in range(H + 4)]
    # print(S, warp)

    def bfs(i, j):
        q = deque()
        q.append((i, j))
        dist[i][j] = 0
        while q:
            a, b = q.popleft()
            for x in range(-2, 3):
                for y in range(-2, 3):
                    if S[a + x][b + y] == ".":
                        warp = abs(x) + abs(y) != 1
                        d = dist[a][b] + int(warp)
                        if d < dist[a + x][b + y]:
                            dist[a + x][b + y] = d
                            if warp:
                                q.append((a + x, b + y))
                            else:
                                q.appendleft((a + x, b + y))
                            # print(q)

    bfs(Ch + 2, Cw + 2)
    if dist[Dh + 2][Dw + 2] == 10 ** 18:
        print(-1)
    else:
        print(dist[Dh + 2][Dw + 2])


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

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    l, r = map(int, input().split())
    ans = [i for i in range(l, r+1)]
    for _ in range(m-1):
        l, r = map(int, input().split())
        ans = [i for i in ans if l <= i <= r]
    print(len(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def input(): return sys.stdin.readline().rstrip()

def main():
    _, m = map(int, input().split())

    max = -1
    min = 10 ** 5 + 1
    for _ in range(m):
        l, r = map(int, input().split())
        if l > max:
            max = l
        if r < min:
            min = r
    if min - max < 0:
        print(0)
    else:
        print(min - max + 1)

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

#n=int(input())
#h1,m1,h2,m2,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

t=list(input())
m=0
n=len(t)
for i in range(n):
    if t[i]=="?":
        t[i]="D"
m=""
for i in t:
    m+=i
print(m)


### FIXED CODE ###

#n=int(input())
#h1,m1,h2,m2,k=map(int,input().split())
#a=list(map(int,input().split()))
#l=[list(map(int,input().split())) for i in range(n)]
#l=[list(input().split()) for i in range(n)]

t=list(input())
n=len(t)
m=""
for i in range(n):
    if t[i]=="?":
        m+="D"
    else:
        m+=t[i]
print(m)
### BUGGY CODE ###

k = int(input())
target = 7
if k % 2 == 0:
  print(-1)
  exit()
for i in range(1000000 + 1):
  if target % k == 0:
    print(i + 1)
    exit()
  target *= 10
  target += 7
print(-1)

### FIXED CODE ###

def main():

    k = int(input())
    a = [0] * (10 ** 6 + 1)
    a[0] = 7 % k
    if a[0] == 0:
        print(1)
        exit()
    for i in range(1, k + 1):
        a[i] = (a[i - 1] * 10 + 7) % k
        if a[i] == 0:
            print(i + 1)
            exit()
    print(-1)

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

n,a = map(int,input().split())
x = list(map(int,input().split()))
ans = 0
for bit in range(2**n):
    x_sum = 0
    count = 0
    for j in range(n):
        if bit>>j&1:
            x_sum += x[j]
            count += 1
    if count > 0:
        if x_sum == a*count:
            ans += 1
print(ans)

### FIXED CODE ###

def makelist(n,m,p):
    return [[[0 for k in range(p)]for i in range(m)]for j in range(n)]

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

dp = makelist(n+1,n+1,n*a+1)
dp[0][0][0] = 1
for j in range(n+1):
    for k in range(n+1):
        for s in range(n*a+1):
            if j*k > 0 and s >= x[j-1]:
                dp[j][k][s] = dp[j-1][k][s] + dp[j-1][k-1][s-x[j-1]]
            elif j >= 1 and s < x[j-1]:
                dp[j][k][s] = dp[j-1][k][s]
ans = 0
for k in range(1,n+1):
    ans += dp[n][k][k*a]
print(ans)
### BUGGY CODE ###

from scipy.misc import comb
# from scipy.special import comb
n = int(input())
a = sorted(list(map(int,input().split())))[::-1]
ans = 0
for i in range(1,n):
    b = comb(a[0],a[i])
    if b >= ans:
        ans1 = a[i]
        ans = b
print(a[0],ans1)


### FIXED CODE ###

import math
n = int(input())
a = sorted(list(map(int,input().split())))
b = (a[-1]+1)//2
d = float("inf")
for i in a:
    if abs(b-i) < d:
        d = abs(b-i)
        ans = i
print(a[-1],ans)
### BUGGY CODE ###

N = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())

L = [N,0,0,0,0,0]

time = 0
while L != [0,0,0,0,0,N]:
  if L[4] != 0:
    if L[4] > e:
      L[5] = L[5] + e
      L[4] = L[4] - e
    else:
      L[5] = L[5] + L[4]
      L[4] = 0
  if L[3] != 0:
    if L[3] > d:
      L[4] = L[4] + d
      L[3] = L[3] - d
    else:
      L[4] = L[4] + L[3]
      L[3] = 0
  if L[2] != 0:
    if L[2] > c:
      L[3] = L[3] + c
      L[2] = L[2] - c
    else:
      L[3] = L[3] + L[2]
      L[2] = 0
  if L[1] != 0:
    if L[1] > b:
      L[2] = L[2] + b
      L[1] = L[1] - b
    else:
      L[2] = L[2] + L[1]
      L[1] = 0
  if L[0] != 0:
    if L[0] > a:
      L[1] = L[1] + a
      L[0] = L[0] - a
    else:
      L[1] = L[1] + L[0]
      L[0] = 0
  time = time + 1
  
print(time)

### FIXED CODE ###

N = int(input())
a = int(input())
b = int(input())
c = int(input())
d = int(input())
e = int(input())
if min(a,b,c,d,e) == a:
  if N % a == 0:
    print(N//a + 4)
  else:
    print(N//a + 5)
elif min(b,c,d,e) == b:
  if N % b == 0:
    print(N//b + 4)
  else:
    print(N//b + 5)
elif min(c,d,e) == c:
  if N % c == 0:
    print(N//c + 4)
  else:
    print(N//c + 5)
elif min(d,e) == d:
  if N % d == 0:
    print(N//d + 4)
  else:
    print(N//d + 5)
else:
  if N % e == 0:
    print(N//e + 4)
  else:
    print(N//e + 5)
### BUGGY CODE ###

N=int(input()) 
A = [ bin(int(i))[2:].zfill(60) for i in input().split()] 

mod = 10**9+7
c = [0]*60
for i in A:
  for j in range(60):
    if i[j] == '1':
      c[-1-j] +=1     
ans = 0
for i in range(60):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)


### FIXED CODE ###

N=int(input()) 
import math
A=list(map(int, input().split())) 
k =  len(bin(max(A))[2:])
mod = 10**9+7

c = [0]*k

for i in A:
  bit = bin(i)[2:].zfill(k)
  for j in range(k):
    if bit[j] == '1':
      c[-1-j] +=1
      
ans = 0
for i in range(k):
  ans = (ans +(2**i)*(c[i]*(N-(c[i]))))%mod
  
print(ans)
### BUGGY CODE ###

from scipy.sparse.csgraph import dijkstra

n,x,y = map(int,input().split())

route = [[0 for _ in range(n)]for _ in range(n)]
for i in range(n-1):
	route[i][i+1] = 1

route[x-1][y-1] = 1
route[y-1][x-1] = 1

#res = shortest_path(route, unweighted=False,directed=False)
res = dijkstra(route, directed=False)


ans = [0 for _ in range(n)]
for i in range(n):
	for j in range(i,n):
		ans[int(res[i][j])] += 1

for i in range(1,n):
	print(ans[i])


### FIXED CODE ###

from scipy.sparse.csgraph import dijkstra
import sys
def main():
	input = sys.stdin.readline

	n,x,y = map(int,input().split())

	route = [[0 for _ in range(n)]for _ in range(n)]
	for i in range(n-1):
		route[i][i+1] = 1

	route[x-1][y-1] = 1
	route[y-1][x-1] = 1
	route = tuple(route)
	#res = shortest_path(route, unweighted=False,directed=False)
	res = tuple(dijkstra(route, directed=False))

	ans = [0 for _ in range(n)]
	for i in range(n):
		for j in range(i,n):
			ans[int(res[i][j])] += 1

	for i in range(1,n):
		print(ans[i])
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import math

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

ans = 0
for x in range(N+1):
    ans = max(ans,math.floor((A*x)/B) - A * math.floor(x/B))

print(ans)

### FIXED CODE ###

import math

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

x = min(B-1,N)
ans = math.floor((A*x)/B) - A * math.floor(x/B)

print(ans)
### BUGGY CODE ###

import numpy as np
n,m,q = [int(i) for i in input().split()]

trains = np.zeros([n+1,n+1],dtype = np.int32)

for i in range(m):
    x,y = [int(i) for i in input().split()]
    trains[x][y] += 1
    
ans_arr = np.cumsum(np.cumsum(trains,axis = 0),axis = 1)
    
for i in range(q):
    x,y = [int(i) for i in input().split()]
    ans = ans_arr[y][y] - ans_arr[x-1][y] - ans_arr[y][x-1] + ans_arr[x-1][x-1]
    print(ans)


### FIXED CODE ###

import numpy as np
n,m,q = [int(i) for i in input().split()]

trains = np.zeros([n+1,n+1],dtype = np.int32)

l,r = np.split(np.array([input().split() for _ in range(m)],dtype = np.int32),2,1)
p,q = np.split(np.array([input().split() for _ in range(q)],dtype = np.int32),2,1)


np.add.at(trains,(l,r),1)
ans_arr = np.cumsum(np.cumsum(trains,axis = 0),axis = 1)

p -= 1
ans = ans_arr[q,q] - ans_arr[p,q] - ans_arr[q,p] + ans_arr[p,p]
print('\n'.join(ans.astype(str).flatten()))
### BUGGY CODE ###

import copy as cp
N = int(input())
numbers = [int(input()) for i in range(N)]

max_num = max(numbers)

for i in range(len(numbers)):
    if numbers[i] == max_num:
        temp_numbers = cp.copy(numbers)
        temp_numbers.pop(i)
        print(max(temp_numbers))
    else :
        print(max_num)

### FIXED CODE ###

N = int(input())
numbers = [int(input()) for i in range(N)]

# 最大値を取得
max_num = max(numbers)

# 最大値を同じ値がいくつ在るかを確認
max_nums = numbers.count(max_num)

if max_nums >= 2:
    for i in range(len(numbers)):
        print(max_num)
else :
    max_index = numbers.index(max(numbers))
    for i in range(len(numbers)):
        if i == max_index:
            second_max = sorted(numbers)[-2]
            print(second_max)
        else :
            print(max_num)
### BUGGY CODE ###

# coding: utf-8

import sys
import numpy as np

N, M = map(int, sys.stdin.readline().split(" ", 2))

ans = []
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    ans.append(np.array([ 1  if l-1 <= i < r else 0  for i in range(N)] ))
print(sum (1 for a in sum(ans) if a == M))
    # L.append(l)
    # R.append(r)

    


### FIXED CODE ###

# coding: utf-8

import sys
import numpy as np

N, M = map(int, sys.stdin.readline().split(" ", 2))

L = 0
R = M + N
for line in sys.stdin:
    l, r = map(int, line.split(" ", 2))
    if l > L:
        L = l
    if r < R:
        R = r
print(max(0, R - L + 1))
    # L.append(l)
    # R.append(r)
### BUGGY CODE ###

from collections import deque


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

q = deque([1])
prev=[1]
siru = [0] * (n-1)
while q:

    now = q.popleft()
    
    next = graph[now-1]

    
    for n in next:
        if not n in prev: 
            q.append(n)
            prev.append(n)
            siru[n-2] = now
    if not 0 in siru:
        break

if 0 in siru:
    print("No")
else:
    print("Yes")
    for i in range(len(siru)):
        print(siru[i])
    
        

### FIXED CODE ###

from collections import deque

def main():
    n,m = map(int, input().split())
    graph = [[] for _ in range(n)]
    for i in range(m):
        a,b = map(int, input().split())
        graph[a-1].append(b)
        graph[b-1].append(a)
    
    q = deque([1])
    prev=[1]
    siru = [0] * n
    siru[0] = 1
    while q:
    
        now = q.popleft()
        
        next = graph[now-1]
    
        
        for n in next:
            if not siru[n-1]: 
                q.append(n)
                siru[n-1] = now
    
    
    print("Yes")
    print("\n".join(map(str, siru[1:])))
if __name__ == "__main__":
    main()
### BUGGY CODE ###

k = int(input())
q = [1, 2, 3, 4, 5, 6, 7, 8, 9]
ans = 0
for i in range(k):
    ans = q.pop(0)
    x = ans
    if x%10 != 0:
        q.append(10*x + (x%10) - 1)
    q.append(10*x + (x%10))
    if x%10 != 9:
        q.append(10*x + (x%10) + 1)
print(ans)

### FIXED CODE ###

k = int(input())
l = []
for i in range(1, 10):
    l.append(i)
judge = l
for d in range(1, 10):
    tmp = []
    for i in range(len(judge)):
        val = judge[i]
        for j in range(-1, 2):
            add = val%10 + j
            if add >= 0 and add <= 9:
                tmp.append(val*10 + add)
    for i in range(len(tmp)):
        l.append(tmp[i])
    judge = tmp
print(l[k-1])
### BUGGY CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

s = input()

ans = 0

for i in range(len(s)):
    for j in range(i+1,len(s)+1):
        if s[i:j][0] == "A" and s[i:j][-1] == "Z":
            if len(s[i:j]) > ans:
                ans = len(s[i:j])

print(ans)

### FIXED CODE ###

import sys


inint = lambda: int(sys.stdin.readline())
inintm = lambda: map(int, sys.stdin.readline().split())
inintl = lambda: list(inintm())
instrm = lambda: map(str, sys.stdin.readline().split())
instrl = lambda: list(instrm())

s = input()

ans = 0
flag = 0
a = 0

for i in range(len(s)):
    if flag != 1:
        if s[i] == "A":
            flag = 1
            a = i
    elif s[i] == "Z":
        ans = i-a+1

print(ans)