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

# 繰り返し二乗法 (mod 有り)
def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while n > 0:
        if n % 2 == 0:
            a = a ** 2 % mod
            n //= 2
        else:
            res = res * a % mod
            n -= 1
    return (res % mod)


# 繰り返し二乗法 (mod 有り) を利用して nCk を高速に返す
# mod が素数のときのみ利用可能 (フェルマーの小定理を利用しているため)
def mod_comb(n, k, mod=(10 ** 9 + 7)):
    res1 = 1
    for i in range(n, (n - k), -1):
        res1 *= i
        res1 %= mod
    res2 = 1
    for i in range(1, (k + 1)):
        res2 *= i
        res2 %= mod
    return ((res1 * mod_rep_pow(res2, (mod - 2), mod)) % mod)


n = int(input().strip())
a = list(map(int, input().split()))
b = {}
length = -1
for i in range(n + 1):
    if a[i] not in b:
        b[a[i]] = i
    else:
        length = i - b[a[i]]
        break
x = n - length
for i in range(1, n + 2):
    print(mod_comb(n + 1, i) - mod_comb(x, (i - 1)))


### FIXED CODE ###

def mod_rep_pow(a, n, mod=(10 ** 9 + 7)):
    res = 1
    while 0 < n:
        if n & 1:
            res = (res * a) % mod
            n -= 1
        else:
            a = (a ** 2) % mod
            n //= 2
    return (res % mod)


def mod_inverse(a, mod=(10 ** 9 + 7)):
    return mod_rep_pow(a, (mod - 2))


def mod_comb(facts, facts_inverse, n, k, mod=(10 ** 9 + 7)):
    return (facts[n] * facts_inverse[k] * facts_inverse[n - k])


n = int(input().strip())
a = list(map(int, input().split()))
not_unique = sum(a) - sum([i for i in range(1, n + 1)])
b = []
for i in range(n + 1):
    if a[i] == not_unique:
        b.append(i)
x = n - (b[1] - b[0])
mod = 10 ** 9 + 7
facts = [1] * (n + 2)
for i in range(0, n + 1):
    facts[i + 1] = (facts[i] * (i + 1) % mod)

facts_inverse = [1] * (n + 2)
facts_inverse[n + 1] = mod_inverse(facts[n + 1])
for i in range(n + 1, 0, -1):
    facts_inverse[i - 1] = (facts_inverse[i] * (i)) % mod

for i in range(1, n + 2):
    if x < (i - 1):
        print(mod_comb(facts, facts_inverse, (n + 1), i) % mod)
    else:
        print((mod_comb(facts, facts_inverse, (n + 1), i) - (mod_comb(facts, facts_inverse, x, (i - 1)))) % mod)
### BUGGY CODE ###

import copy

H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

A_copy = copy.deepcopy(A)
cnt = 0
while True:
    flag = False
    for i in range(H):
        if '.' in A[i]:
            flag = True
            break
    else:
        break
    if flag:
        for i in range(H):
            for j in range(W):
                if A[i][j] == '#':
                    if i != 0:
                        A_copy[i-1][j] = '#'
                    if i != H-1:
                        A_copy[i+1][j] = '#'
                    if j != 0:
                        A_copy[i][j-1] = '#'
                    if j != W-1:
                        A_copy[i][j+1] = '#'
        A = copy.deepcopy(A_copy)
        cnt += 1

print(cnt)

### FIXED CODE ###

from collections import deque


H, W = map(int, input().split())
A = [list(input()) for _ in range(H)]

INF = 10 ** 5
d = [[10 ** 5] * W for _ in range(H)]

q = deque()

for i in range(H):
    for j in range(W):
        if A[i][j] == '#':
            d[i][j] = 0
            q.append((i, j))

dy = [-1, 1, 0, 0]
dx = [0, 0, -1, 1]

while q:
    y, x = q.popleft()

    for i in range(4):
        ny = y + dy[i]
        nx = x + dx[i]

        if (0 <= ny < H and 0 <= nx < W and
            A[ny][nx] != '#' and d[ny][nx] == INF):

            d[ny][nx] = d[y][x] + 1
            q.append((ny, nx))

ans = 0
for i in range(H):
    for j in range(W):
        ans = max(ans, d[i][j])

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

n, k = map(int, input().split())
l = list(map(int, input().split()))
ans = 9999999999999
for i in range(len(l) - k + 1):
    tl = l[i:i + k]
    min_l = min(0, tl[0])
    max_l = max(0, tl[-1])
    min_abs = min(abs(min_l), abs(max_l))
    max_abs = max(abs(min_l), abs(max_l))
    ans = min(ans, min_abs * 2 + max_abs)
print(ans)

### FIXED CODE ###

n, k = map(int, input().split())
l = list(map(int, input().split()))
ans = 9999999999999
for i in range(len(l) - k + 1):
    min_l = min(0, l[i])
    max_l = max(0, l[i+k-1])
    min_abs = min(abs(min_l), abs(max_l))
    max_abs = max(abs(min_l), abs(max_l))
    ans = min(ans, min_abs * 2 + max_abs)
print(ans)
### BUGGY CODE ###

S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, mod=13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y

    else:
        X = int(X)
        X = (X * pow(10, i-1, mod=13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y

print(dp[-1][5] % 1000000007)


### FIXED CODE ###

S = input()
N = len(S)
dp = []
for _ in range(N+1):
    dp.append([0] * 13)
dp[0][0] = 1
p = 10**9+7

for i in range(1, N+1):
    X = S[N-i]
    if X == '?':
        for j in range(10):
            X = (j * pow(10, i-1, 13)) % 13
            for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
                Y = dp[i-1][k]
                Z = (X + k) % 13  # 新たなあまり
                dp[i][Z] += Y % p

    else:
        X = int(X)
        X = (X * pow(10, i-1, 13)) % 13
        for k in range(13):  # 上段の各あまりに対して、xのあまりを加える
            Y = dp[i-1][k]
            Z = (X + k) % 13  # 新たなあまり
            dp[i][Z] += Y % p

print(dp[-1][5] % 1000000007)
### BUGGY CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = ans * i
print(ans%(10**9 + 7))

### FIXED CODE ###

n = int(input())
ans = 1
for i in range(1,n+1):
    ans = (ans * i)%(10**9+7)
print(ans)
### BUGGY CODE ###

import sys
from bisect import bisect_left, bisect, insort_left, insort
A = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        insort(A, int(s[7:]))
    elif s[2] == "t":
        S.append(A.pop())
    else:
        break
print(*S, sep="\n")



### FIXED CODE ###

import sys
from heapq import heapify, heappush, heappop
hq = []
S = []
for s in sys.stdin:
    if s[2] == "s":
        heappush(hq, -int(s[7:]))
    elif s[2] == "t":
        S.append(-heappop(hq))
    else:
        break
print("\n".join(map(str, S)))
### BUGGY CODE ###

S=list(input())
c=0
while len(S)>1:
    before=len(S)
    # 双方向から見ればループ回数は半分になる？
    for i in range(before//2):
    #for i in range(before-1):
        if S[i]+S[i+1]=="01" or S[i]+S[i+1]=="10":
            c+=2
            #S.pop(i)
            #S.pop(i)
            del S[i:i+2]
            break
        if S[-i-1]+S[-i-2]=="10" or S[-i-1]+S[-i-2]=="01":
            c+=2
            if i==0:
                del S[-i-2:]
            else:
                del S[-i-2:-i]
            break
    if before==len(S):
        break
print(c)


### FIXED CODE ###

S=input()
print(2*min(S.count("0"), S.count("1")))
### BUGGY CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        for c in range(101):
            for d in range(101):
                x = 100 * (a * A + b * B)
                y = c * C + d * D
                if x + y <= F and y <= x * E // 100 and x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

print(ans_A, ans_B)


### FIXED CODE ###

A, B, C, D, E, F = map(int, input().split())

tmp = 0
ans_A = 0
ans_B = 0
for a in range(31):
    for b in range(31):
        x = 100 * (a * A + b * B)
        if x > F:
            break
        for c in range((x // 100 * E) // C + 1):
            for d in range(((x // 100 * E) - c) // D + 1):
                y = c * C + d * D
                if x + y > F or y > x * E // 100:
                    break
                if x + y != 0:
                    if y / (x + y) > tmp:
                        ans_A = x + y
                        ans_B = y
                        tmp = y / (x + y)

if ans_A == 0:
    print(100 * A, 0)
else:
    print(ans_A, ans_B)
### BUGGY CODE ###

a,b=map(int,input().split())
ans=0

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

for i in cf(a,b):
    for j in range(2,i):
        if i%j == 0:
            break
    else:
        ans+=1

print(ans)

### FIXED CODE ###

a,b=map(int,input().split())
ans=1

def factorization(n):
    arr = []
    temp = n
    for i in range(2,int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])

    if temp!=1:
        arr.append([temp, 1])

    if arr==[]:
        arr.append([n, 1])

    return arr

a_list=factorization(a)
b_list=factorization(b)

a_new=[a[0] for a in a_list]
b_new=[b[0] for b in b_list]

if a_new[0]==b_new[0]==1:
    ans=0

for i in a_new:
    if i in b_new:
        ans += 1

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

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

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

neg_inf = float("-Inf")
no_answer = False

start = 1
end = M

distance = {}
distance[start] = 0
previous = {}

for i in range(M-1):
    for f,t,w in edges:
        if distance.get(f,neg_inf) + w - P > distance.get(t,neg_inf):
            distance[t] = distance[f] + w - P
            previous[t] = f

path = []
node = end
if node in previous:
    while node != start:
        path.append(node)
        node = previous[node]
        if len(path) > M:
            no_answer = True
            break
    path.append(start)

for f,t,w in edges:
    if distance.get(f,neg_inf) + w - P > distance.get(t,neg_inf) and t in path:
        no_answer = True
        break

if no_answer:
    print(-1)
else:
    print(max(0,distance[end]))

### FIXED CODE ###

def is_reachable(edges,start,end):
  g = {}
  for f,t,w in edges:
    if f in g: g[f].append(t)
    else: g[f] = [t]
  visiting = [start]
  visited = {}
  while visiting:
    v = visiting.pop()
    if v in visited: continue
    if v == end: return True
    visited[v] = True
    for v2 in g.get(v, ()):
      if v2 in visited or v2 in visiting: continue
      visiting.append(v2)
  return False

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

edges = []
for _ in range(M):
    a,b,c = map(int, input().split())
    edges.append((a,b,c))

neg_inf = float("-Inf")
no_answer = False

start = 1
end = N

distance = {}
for i in range(1,N+1):
  distance[i] = neg_inf
distance[start] = 0

for i in range(N-1):
    for f,t,w in edges:
        if distance[f] + w - P > distance[t]:
            distance[t] = distance[f] + w - P

for f,t,w in edges:
    if distance[f] + w - P > distance[t] and is_reachable(edges,t,end):
        no_answer = True
        break

if no_answer:
    print(-1)
else:
    print(max(0,distance[end]))
### BUGGY CODE ###

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

dp = [10 ** 5 for i in range(N)]

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif 0 < i <= K:
        tmp = [dp[i - (j + 1)] + abs(h_array[i] - h_array[i - (j + 1)]) for j in range(i)]
        dp[i] = min(tmp)
    elif K < i:
        tmp = [dp[i - (j + 1)] + abs(h_array[i] - h_array[i - (j + 1)]) for j in range(K)]
        dp[i] = min(tmp)
print(dp[N - 1])


### FIXED CODE ###

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

dp = [10 ** 5 for i in range(N)]

for i in range(N):
    if i == 0:
        dp[0] = 0
    elif 0 < i <= K:
        tmp = [dp[i - (j + 1)] + abs(h_array[i] - h_array[i - (j + 1)]) for j in range(i)]
        dp[i] = min(tmp)
    elif K < i:
        tmp = [dp[i - (j + 1)] + abs(h_array[i] - h_array[i - (j + 1)]) for j in range(K)]
        dp[i] = min(tmp)
print(dp[N - 1])
### BUGGY CODE ###

N = int(input())
inputs = [float(i) for i in input().split()]

dp = [[0.0 for _ in range(N+1)] for _ in range(N+1)]
dp[1][0] = 1 - inputs[0]
dp[1][1] = inputs[0]
for i in range(2, N+1):
    tmp_dp = [0.0 for _ in range(N+1)]
    for j in range(i+1):
        if j == 0:
            dp[i][j] = dp[i-1][j] * (1 - inputs[i-1])
        else:
            dp[i][j] = dp[i-1][j] * (1 - inputs[i-1]) + dp[i-1][j-1] * inputs[i-1]

print(sum(dp[-1][(N+1)//2:]))


### FIXED CODE ###

import numpy as np

N = int(input())
inputs = np.array([float(i) for i in input().split()])

dp = np.array([np.array([0.0 for _ in range(N+1)]) for _ in range(N+1)])
dp[1][0] = 1 - inputs[0]
dp[1][1] = inputs[0]
for i in range(2, N+1):
    dp[i][1:] = dp[i-1][1:] * (1.0 - inputs[i-1]) + dp[i-1][:N] * inputs[i-1]
    dp[i][0] = dp[i-1][0] * (1.0 - inputs[i-1])

print(sum(dp[-1][(N+1)//2:]))
### BUGGY CODE ###

n, m = map(int, input().split())
jobs = dict()

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [b]
    else:
        jobs[a].append(b)
# print(jobs)
days = []
money_list = [0]
for i in range(1, m+1):
    # print('days', days)
    if i in jobs.keys():
        money_list.extend(jobs[i])
    # print(money_list)
    max_money = money_list.pop(money_list.index(max(money_list)))
    days.append(max_money)
    if max_money == 0:
        money_list.append(0)
print(sum(days))


### FIXED CODE ###

import heapq

n, m = map(int, input().split())
jobs = dict()

for i in range(n):
    a, b = map(int, input().split())
    if not a in jobs.keys():
        jobs[a] = [-b]
    else:
        jobs[a].append(-b)
# print(jobs)
sum_money = 0
money_list = [0]
heapq.heapify(money_list)
for i in range(1, m+1):
    if i in jobs.keys():
        for money in jobs[i]:
            heapq.heappush(money_list, money)
    # print(money_list)
    max_money = -heapq.heappop(money_list)
    sum_money += max_money
    if max_money == 0:
        heapq.heappush(money_list, 0)
print(sum_money)
### BUGGY CODE ###

N = int(input())
a = list(map(int,input().split()))
s = 0
for i in range(N):
    b = a[i]
    for j in range(i+1,N):
        s += b*a[j]
print(s%(pow(10,9)+7))

### FIXED CODE ###

N = int(input())
a = list(map(int,input().split()))
a_s = sum(a)
mod = 10**9+7
s = 0
for i in range(N-1):
    b = a[i]
    a_s -= b
    s += b*(a_s)
    s %= mod
print(s)
### BUGGY CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = -1

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    cnt += 1
    
print(cnt)

### FIXED CODE ###

from collections import deque

h,w = map(int,input().split())
matrix = [["a" for _ in range(w+2)]] + [list("a" + input() + "a") for _ in range(h)] + [["a" for _ in range(w+2)]]

matrix_list1 = deque()
cnt = 0

for i in range(1,h+1):
    for j in range(1,w+1):
        if matrix[i][j] == "#":
            matrix_list1.append([i,j])

while len(matrix_list1) != 0:     
    for _ in range(len(matrix_list1)):
        x,y = matrix_list1.popleft()
        if matrix[x+1][y] == ".":
            matrix[x+1][y] = "#"
            matrix_list1.append([x+1,y])
        if matrix[x-1][y] == ".":
            matrix[x-1][y] = "#"
            matrix_list1.append([x-1,y])
        if matrix[x][y+1] == ".":
            matrix[x][y+1] = "#"
            matrix_list1.append([x,y+1])
        if matrix[x][y-1] == ".":
            matrix[x][y-1] = "#"
            matrix_list1.append([x,y-1])
    else:
        if len(matrix_list1) > 0:
            cnt += 1
    
print(cnt)
### BUGGY CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce


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

def main():
	mod = 10**9 + 7
	N = int(input())
	A = [i for i in map(int, input().split())]
	
	ans = reduce(lcm, A)
	"""
	a = 1
	for i in A:
		a = lcm(a, i)
	"""
	#print(a, ans)
	B = [ans//i for i in A]
	print(sum(B) % mod)

if __name__ == "__main__":
	main()


### FIXED CODE ###

#from math import gcd
from fractions import gcd
from functools import reduce

mod = 10**9 + 7

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


N = int(input())
A = [i for i in map(int, input().split())]

ans = reduce(lcm, A)

#print(ans)
B = [ans//i for i in A]

print(sum(B) % mod)
### BUGGY CODE ###

import fractions

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

def divisor(n): 
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
  
A_list = divisor(A)
B_list = divisor(B)

box = list(set(A_list) & set(B_list))
box = sorted(box)

tmp = []

for l in range(len(box)-1):
  for m in range((l+1),len(box)):
    if fractions.gcd(box[l],box[m]) != 1:
      tmp.append(box[m])
      
print(len(box)-len(set(tmp)))

### FIXED CODE ###

#l=list(map(int, input().split()))
a,b=map(int, input().split())
#l=list(map(int, input().split()))
#n = int(input())
def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table
def is_prime(n):
    for i in range(2, n + 1):
        if i * i > n:
            break
        if n % i == 0:
            return False
    return n != 1



ans = 1
temp1 = divisor(a)
temp2 = divisor(b)
hoge = []
if len(temp1) < len(temp2):
    hoge = temp1
    hoge2 = temp2
else:
    hoge = temp2
    hoge2 = temp1

temp = []
for i in hoge:
    if i in hoge2:
        temp.append(i)

#print (temp)
for i in temp:
    if is_prime(i):
        ans += 1

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

N=int(input())
S=input()
count=0
for i in range(N):
    for j in range(i,N):
        for k in range(j,N):
            if  S[i]!=S[j] and S[j]!=S[k] and S[k]!=S[i] and (j-i)!=(k-j):
                count+=1
print(count) 

### FIXED CODE ###

N=int(input())
S=input()
# N=int(Input[0][0])
# S=Input[1][0]
import math
count=0
counter={'R':0,'G':0,'B':0}
for i in S:
    counter[i]+=1
s=counter['R']*counter['G']*counter['B']
for i in range(1,N-1):
    for j in range(i+1,N):
        k=2*j-i
        if k<=N and (S[i-1]!=S[j-1] and S[i-1]!=S[k-1] and S[j-1]!=S[k-1]):
                count+=1
print(s-count)
### BUGGY CODE ###

import collections
N,Q = map(int,input().split())
T = input()
S = T.replace("AC","WW")

for i in range(Q):
    l,r = map(int,input().split())
    l,r = l-1,r-1
    num = collections.Counter(S[l:r+1])["W"]//2
    if T[l] == "C" and T[r] == "A":
        num -= 1
    print(num)

### FIXED CODE ###

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

t = [0]*(N+1)
for i in range(N):
    t[i+1] = t[i] + (S[i:i+2] == "AC")
    
for i in range(Q):
    l,r = map(int,input().split())
    print(t[r-1]-t[l-1])
### BUGGY CODE ###

n, k = map(int, input().split())
h = list(map(int, input().split()))
 
a = [0]*n
 
for i in range(1, n):
  a[i] = min([a[j] + abs(h[i]-h[j]) for j in range(max(0, i-k), i)])
print(a[-1])

### FIXED CODE ###

n, k = map(int, input().split())
hs = list(map(int, input().split()))
 
dp = [0]*n
 
for i in range(1, n):
  first = max(0, i-k)
  dp[i] = min([d + abs(hs[i]-h) for d, h in zip(dp[first:i], hs[first:i])])
print(dp[-1])
### BUGGY CODE ###

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines

def main():
    a, b, c, x, y = map(int, input().split())
    r = float('inf')
    for piza_a in range(x + 1):
        for piza_b in range(y + 1):
            piza_c = max(x - piza_a, y - piza_b) * 2
            tmp = piza_a * a + piza_b * b + piza_c * c
            r = min(r, tmp)
    print(r)

if __name__ == '__main__':
    main()

### FIXED CODE ###

def main():
    a, b, c, x, y = map(int, input().split())
    r = float('inf')
    for piza_c in range(0, max(x, y) * 2 + 1, 2):
        piza_a = max(0, x - piza_c // 2)
        piza_b = max(0, y - piza_c // 2)
        r = min(r, piza_c * c + piza_a * a + piza_b * b)
    print(r)

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

def solve(N):
    if N <= 20:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                return

    print(0, flush=True)
    low_sex = input()
    if low_sex == 'Vacant':
        return
    print(N - 1, flush=True)
    high_sex = input()
    if high_sex == 'Vacant':
        return
    high, low = N - 1, 0
    while high - low > 1:
        mid = (high + low) // 2
        print(mid, flush=True)
        mid_sex = input()
        if mid_sex == 'Vacant':
            return

        if (high - mid + 1) % 2 == 1 and high_sex != mid_sex or \
           (high - mid + 1) % 2 == 0 and high_sex == mid_sex:
            low = mid
            low_sex = mid_sex
        else:
            high = mid
            high_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))

### FIXED CODE ###

def get_sex(i):
    print(i, flush=True)
    return input()


def solve(N):
    if N <= 19:
        for i in range(N):
            print(i, flush=True)
            s = input()
            if s == 'Vacant':
                exit()

    low_sex = get_sex(0)
    if low_sex == 'Vacant':
        exit()
    high_sex = get_sex(N - 1)
    if high_sex == 'Vacant':
        exit()

    high, low = N - 1, 0
    while high > low:
        mid = (high + low) // 2
        mid_sex = get_sex(mid)
        if mid_sex == 'Vacant':
            exit()

        if (mid - low) % 2 == 1:
            if mid_sex != low_sex:
                low = mid
                low_sex = mid_sex
            else:
                high = mid
                high_sex = mid_sex
        else:
            if mid_sex != low_sex:
                high = mid
                high_sex = mid_sex
            else:
                low = mid
                low_sex = mid_sex


if __name__ == '__main__':
    solve(int(input()))
### BUGGY CODE ###

n, m = map(int, input().split())
l, r = map(int, input().split())
s1 = {int(x) for x in range(l, r+1)}
for i in range(m-1):
    l, r = map(int, input().split())
    s2 = {int(x) for x in range(l, r+1)}
    s1 = s2.intersection(s1)
    
print(len(s1))

### FIXED CODE ###

n, m = [int(x) for x in input().split()]
l = [0] * m
r = [0] * m
for i in range(m):
    l[i], r[i] = map(int, input().split())

L = max(l)
R = min(r)

if L <= R:
    print(R - L + 1)
else:
    print(0)