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

s = list(input())
q = int(input())

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    s = s[::-1]
  else:
    if Q[1] == '1':
      s.insert(0, Q[2])
    else:
      s.append(Q[2])

for i in s:
  print(i, end ="")

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
flg = 0

for _ in range(q):
  Q = [x for x in input().split()]
  if Q[0] == '1':
    flg += 1
  else:
    if (Q[1] == '1' and flg%2==0) or (Q[1] == '2' and flg%2==1):
      s.appendleft(Q[2])
    else:
      s.append(Q[2])
if flg%2==1:
  s.reverse()

print('' . join(s))
### BUGGY CODE ###

n = int(input())
p = list(map(int,input().split()))

cnt = 0
for i in range(n):
  if min(p[:i+1]) == p[i]:
    cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
p = list(map(int,input().split()))

min_num = 10**6
cnt = 0
for i in range(n):
  if p[i] < min_num:
    min_num = p[i]
    cnt += 1
print(cnt)
### BUGGY CODE ###

n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)
ans=0
for c in range(n-2):
    for b in range(c+1,n-1):
        for a in range(b+1,n):
            if l[c]<l[a]+l[b] and l[a]+l[b]<=l[c]*2:
                ans+=1
print(ans)


### FIXED CODE ###

n=int(input())
l=sorted(list(map(int,input().split())),reverse=True)
ans=0
for c in range(n-2):
    for b in range(c+1,n-1):
        flag=0
        if l[c]-l[b]+1>l[b+1]:
            flag=1
        elif l[c]-l[b]+1<=l[n-1]:
            ans+=(n-1-b)
            flag=1
        m=n-1
        h=b+1
        while flag!=1:
            x=(h+m)//2
            bef=x
            if l[x]>l[c]-l[b]+1:
                h=x
                x=(m+h)//2
            elif l[x]<l[c]-l[b]+1:
                m=x
                x=(m+h)//2
            else:
                if x==n-1:
                    ans+=(x-b)
                    break
                if l[x+1]==l[c]-l[b]+1:
                    h=x
                    x=(m+h)//2
                else:
                    ans+=(x-b)
                    break
            if bef==x:
                ans+=(x-b)
                break
print(ans)
### BUGGY CODE ###

N = int(input())
S = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            nums = [str(x) for x in [i, j, k]]
            for s in S:
                if s == nums[0]:
                    nums = nums[1:]
                    if len(nums) == 0:
                        ans += 1
                        break
print(ans)


### FIXED CODE ###

def find(fr, target):
    for i in range(fr, len(S)):
        if S[i] == target:
            return i
    return -1

N = int(input())
S = input()
ans = 0
for i in range(10):
    for j in range(10):
        for k in range(10):
            now = find(0, str(i))
            if now == -1: continue
            now = find(now+1, str(j))
            if now == -1: continue
            now = find(now+1, str(k))
            if now == -1: continue
            ans += 1
print(ans)
### BUGGY CODE ###

s = str(input())
children = [0]*len(s)
s = [int(s) for s in s.translate(str.maketrans({"R":"0", "L":"1"}))]

for i in range(0, len(s)):
    if s[i]: #Lだったら
        for j in range(1, len(s)):
            if s[i-j] == 0:
                if j%2 == 0:
                    children[i-j] += 1
                else:
                    children[i-j+1] += 1
                break
    if s[i] == 0: #Rだったら
        for j in range(1, len(s)):
            if s[i+j] == 1:
                if j%2 == 0:
                    children[i+j] += 1
                else:
                    children[i+j-1] += 1
                break

for k in children:
    print(k)


### FIXED CODE ###

s = input()
 
res = [0] * len(s)
cnt_r = 0
cnt_l = 0
curr = "R"
last_idx = 0
 
for idx, char in enumerate(s):
    if curr == "R":
        if char == "R":
            cnt_r += 1
            #continue
        else:
            res[idx] += cnt_r // 2
            res[idx - 1] += (cnt_r - cnt_r // 2)
            last_idx = idx
            curr = "L"
            cnt_r = 0
            cnt_l = 1
            #continue
    else:
        if char == "L":
            cnt_l += 1
            #continue
        else:
            res[last_idx - 1] += cnt_l // 2
            res[last_idx] += cnt_l - (cnt_l // 2)
            curr = "R"
            cnt_l = 0
            cnt_r = 1
 
res[last_idx - 1] += cnt_l // 2
res[last_idx] += cnt_l - (cnt_l // 2)
 
print(*res)
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys

N,K,*A = map(int, sys.stdin.buffer.read().split())

for _ in range(K):
  Anext = [0 for _ in range(N+1)]
  for i in range(N):
    Anext[max(0,i-A[i])] += 1
    Anext[min(N,i+A[i]+1)] -= 1
  cumsum = 0
  for i in range(N):
    cumsum += Anext[i]
    A[i] = cumsum
  if min(A)==N:
    break

print(' '.join([str(a) for a in A]))

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys

N,K,*A = map(int, sys.stdin.buffer.read().split())

for _ in range(K):
  Anext = [0 for _ in range(N+1)]
  for i in range(N):
    Anext[max(0,i-A[i])] += 1
    Anext[min(N,i+A[i]+1)] -= 1
  cumsum = 0
  for i in range(N):
    cumsum += Anext[i]
    A[i] = cumsum
  if min(A)==N:
    break

print(' '.join([str(a) for a in A]))
### BUGGY CODE ###

#!/usr/bin/env python3
n, m = map(int, input().split())

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [0] * (m + 1)
for j in range(w[0], m + 1):
    dp[j] = v[0]

for i in range(n - 1):
    next_dp = [0] * (m + 1)
    for j in range(m + 1):
        if j < w[i + 1]:
            next_dp[j] = dp[j]
        else:
            next_dp[j] = max(v[i + 1] + dp[j - w[i + 1]], dp[j])
    dp = next_dp

print(dp[-1])


### FIXED CODE ###

#!/usr/bin/env python3
import os
import sys
from atexit import register
from io import StringIO

sys.stdin = StringIO(os.read(0, os.fstat(0).st_size).decode())
sys.stdout = StringIO()
register(lambda: os.write(1, sys.stdout.getvalue().encode()))

input = lambda: sys.stdin.readline().rstrip('\r\n')

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

w, v = [0] * n, [0] * n
for i in range(n):
    w[i], v[i] = map(int, input().split())

dp = [[0] * (m + 1) for _ in range(n)]
for j in range(w[0], m + 1):
    dp[0][j] = v[0]

for i in range(1, n):
    for j in range(m + 1):
        if j < w[i]:
            dp[i][j] = dp[i - 1][j]
        else:
            dp[i][j] = max(v[i] + dp[i - 1][j - w[i]], dp[i - 1][j])

print(dp[-1][-1])
### BUGGY CODE ###

from itertools import chain
from sys import stdin
def lcs(x, y):
    m = len(x)
    n = len(y)
    c = [[0] * 1001 for i in range(1002)]
    # x = " " + x
    # y = " " + y
    for i in range(1, m + 1):
        for j in range(1, n + 1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i - 1][j - 1] + 1
            else:
                c[i][j] = max(c[i - 1][j], c[i][j - 1])
    return max(chain.from_iterable(c))


n = int(input().rstrip())
strs = stdin.readlines()
ret = []
for i in range(n):
    s1 = strs[i*2].rstrip()
    s2 = strs[i*2+1].rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")

### FIXED CODE ###

def lcs(x, y):
    a = len(x)
    b = len(y)
    c1 = [0] * (b + 1)
    for i in range(a):
        e1 = x[i]
        c2 = c1[:]
        for j in range(b):
            if e1 == y[j]:
                c1[j+1] = c2[j] + 1
            elif c1[j+1] < c1[j]:
                c1[j+1] = c1[j]
    return c1[-1]
   
n = int(input().rstrip())
ret = []
for i in range(n):
    s1 = input().rstrip()
    s2 = input().rstrip()
    ret.append(lcs(s1, s2))
print(*ret, sep="\n")
### BUGGY CODE ###

#n=int(input())
#li=input().split()
#d=["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"]
#import numpy as np
#import math

lis=[]
#N Q
li=list(map(int,input().split()))
S=input()
for i in range(li[1]):
    #l_i r_i
    lr=list(map(int,input().split()))
    lis.append(lr)
L=[0]*(li[0]-1)
for i in range(li[0]-1):
    if S[i:i+2]=="AC":
        L[i]+=1
ans=[]
for i in range(li[1]):
    ans.append(sum(L[lis[i][0]-1:lis[i][1]-1]))
for i in range(li[1]):
    print(ans[i])


### FIXED CODE ###

#n=int(input())
#li=input().split()
#d=["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"]
#import numpy as np
#import math

lis=[]
#N Q
li=list(map(int,input().split()))
S=input()
for i in range(li[1]):
    #l_i r_i
    lr=list(map(int,input().split()))
    lis.append(lr)
L=[0]*(li[0])
for i in range(li[0]-1):
    L[i+1]+=L[i]
    if S[i:i+2]=="AC":
        L[i+1]+=1
for i in range(li[1]):
    print(L[lis[i][1]-1]-L[lis[i][0]-1])
### BUGGY CODE ###

N=int(input())
p=1
for i in range(N):
  p=p*(i+1)
print(p%1000000007)

### FIXED CODE ###

N=int(input())
p=1
for i in range(N):
  p=p*(i+1)%1000000007
print(p)
### BUGGY CODE ###

N=int(input())
L=list(map(lambda x: int(x)*(-1),input().split()))
L.sort()
from bisect import bisect
ans = 0
for i1 in range(N-2):
  for i2 in range(i1+1,N-1):
    l1,l2 = L[i1],L[i2]
    th = bisect(L[i2+1:],(l2-l1+1)*(-1))
    #print(l1,l2,L[i2+1:],(l2-l1+1)*(-1),th)
    ans += th
print(ans)

### FIXED CODE ###

N=int(input())
L=list(map(int,input().split()))
L.sort()
from bisect import bisect_left
ans = 0
for i1 in range(N-2):
  for i2 in range(i1+1,N-1):
    l1,l2 = L[i1],L[i2]
    #th = bisect_left(L[i2+1:],l1+l2)
    #print(l1,l2,L[i2+1:],(l2-l1+1)*(-1),th)
    th = bisect_left(L,l1+l2)
    ans += max(th-i2-1,0)
print(ans)
### BUGGY CODE ###

def binary(first,last,find):
    mid = first + (last - first) // 2
    if first == last:
        if Sset[first] == find:
            return True
        else:
            return False
    else:
        return bool(binary(first,mid,find) + binary(mid + 1,last,find))

Snum = int(input())
global Sset
Sset = [int(n) for n in input().split(' ')]
Tnum = int(input())
Tset = [int(n) for n in input().split(' ')]
ans = 0
for t in range(Tnum):
    ans += binary(0,Snum-1,Tset[t])
print(ans)

### FIXED CODE ###

def binary(first,last,find):
    mid = first + (last - first) // 2
    if first == last:
        if Sset[first] == find:
            return True
        else:
            return False
    else:
        if find <= Sset[mid]:
            return binary(first,mid,find)
        else:
            return binary(mid + 1,last,find)

Snum = int(input())
global Sset
Sset = [int(n) for n in input().split(' ')]
Sset.sort()
Tnum = int(input())
Tset = [int(n) for n in input().split(' ')]
ans = 0
for t in range(Tnum):
    ans += binary(0,Snum-1,Tset[t])
print(ans)
### BUGGY CODE ###

import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(19)] for _ in range(19)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 19):
        for k in range(rem2, 19):
            ans += plot[j][k]
    plot[min(18, d25[1])][min(18, d25[0])] += 1
print(ans)

### FIXED CODE ###

import sys
sys.stdin.readline

n = int(input())
a = []
for _ in range(n):
    sa = input().strip()
    tmp = 0
    for i in range(len(sa)):
        if sa[i] == '.':
            break
        tmp = tmp * 10 + int(sa[i])
    i += 1
    for j in range(i, i + 9):
        if j < len(sa):
            tmp = tmp * 10 + int(sa[j])
        else:
            tmp *= 10
    a.append(tmp)

div25 = [[0, 0] for _ in range(n)]
for i, _a in enumerate(a):
    while _a % 2 == 0:
        div25[i][0] += 1
        _a //= 2
    while _a % 5 == 0:
        div25[i][1] += 1
        _a //= 5

div25.sort(key=lambda x: (-x[1], -x[0]))

plot = [[0 for _ in range(45)] for _ in range(20)]
ans = 0
for d25 in div25:
    rem2, rem5 = max(0, 18 - d25[0]), max(0, 18 - d25[1])
    for j in range(rem5, 20):
        for k in range(rem2, 45):
            ans += plot[j][k]
    plot[d25[1]][d25[0]] += 1
print(ans)
### BUGGY CODE ###

n = int(input())

a = []
b = []

for i in range(n):
    aa, bb = map(int, input().split(' '))
    a.append(aa)
    b.append(bb)

order = list(range(n))
tmp_b = b[:]

while(True):
    ok = False
    for i in range(n - 1):
        ok = False
        if tmp_b[i] > tmp_b[i + 1]:
            tmp = tmp_b[i]
            tmp_b[i] = tmp_b[i + 1]
            tmp_b[i + 1] = tmp

            tmp = order[i]
            order[i] = order[i + 1]
            order[i + 1] = tmp
            break
        ok = True
    if ok:
        break

available = False

for i in range(10):

    margin = [0 for i in range(n)]
    now_time = 0
    for i in range(n):
        j = order[i]
        margin[j] = b[j] - (now_time + a[j])
        now_time += a[j]
    
    if min(margin) >= 0:
        available = True
        break
    else:
        min_index = margin.index(min(margin))
        max_index = margin.index(max(margin))

        tmp = order[min_index]
        order[min_index] = order[max_index]
        order[max_index] = tmp


if available:
    print('Yes')
else:
    print('No')

### FIXED CODE ###

n = int(input())

a = []
b = []

for i in range(n):
    aa, bb = map(int, input().split(' '))
    a.append(aa)
    b.append(bb)

order = sorted(range(len(b)), key=lambda k: b[k])

available = False


margin = [0 for i in range(n)]
now_time = 0
for i in range(n):
    j = order[i]
    margin[j] = b[j] - (now_time + a[j])
    now_time += a[j]

if min(margin) >= 0:
    print('Yes')
else:
    print('No')
### BUGGY CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int64)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int64)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

for j in range (M):
    count=np.count_nonzero(A<Arr[j][1])
    if count > 0:
        m=min(count,Arr[j][0])
        A[:m]=Arr[j][1]
        A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))

### FIXED CODE ###

import numpy as np


N,M=map(int,input().split())
# A=np.array(list(map(int,input().split())))
A=np.array(list(map(int,input().split())),dtype=np.int32)
A=np.sort(A)

EXC=[]

for i in range(M):
    exc=list(map(int,input().split()))
    EXC.append(exc)
excArry=np.array(EXC,dtype=np.int32)

col_num=1
Arr=excArry[np.argsort(excArry[:,col_num])[::-1]]
# print(A)
# print(Arr)

point=0


for j in range (M):
    change_Num=Arr[j][1]
    count=np.count_nonzero(A<change_Num)
    if count > 0:
        m=min(count,Arr[j][0])
        A[point:point+m]=change_Num
        point+=m
        # A=np.sort(A)
    else:
        break

print(np.sum(A))
    
#     for j in range (B):
#         count=np.count_nonzero(A<C)
#         if count>0:
#             m=min(B,count)
#             A[:m]=C
#         else:
#             continue
    
#     A=np.sort(A)

# print(np.sum(A))
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
#グループの根を返す
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 #xのグループとyのグループを結合
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
#親を全部表示
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_groupmembers(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
N, M ,K = map(int, input().split())
uf = UnionFind(N)
friend_count=[0]*N
for m in range(M):
    p,q = map(int, input().split())
    friend_count[p-1]+=1
    friend_count[q-1]+=1
    uf.union(p-1, q-1)
bgraph = {}
for k in range(K):
    p,q = map(int, input().split())
    if p-1 in bgraph.keys():
        bgraph[p-1].append(q-1)
    else:
        bgraph[p-1] = [q-1]
    if q-1 in bgraph.keys():
        bgraph[q-1].append(p-1)
    else:
        bgraph[q-1] = [p-1]
allg =  uf.all_groupmembers()
last_list=[]
for n in range(N):
    leng = uf.size(n)
    if n in bgraph.keys():
        ng = len(set(bgraph[n])&set(uf.members(n)))
    else:
        ng = 0
    last_list.append(str(leng-ng-1-friend_count[n]))
    print(str(leng-ng-1-friend_count[n]), end=" ")

### FIXED CODE ###

class UnionFind():
    def __init__(self,n):
        # リンク情報　子→親の番号　親(根)→負のサイズ
        self.d=[-1 for i in range(n)]
    
    def find(self,x):
        if(self.d[x]<0):return x
        self.d[x]=self.find(self.d[x])
        return self.d[x]
 
    def unite(self,x,y):
        x=self.find(x)
        y=self.find(y)
        if(x==y):return False
        if(self.d[x]>self.d[y]):x,y=y,x
        self.d[x]+=self.d[y]
        self.d[y]=x
        return True
 
    def same(self,x,y):return self.find(x)==self.find(y)
    def size(self,x):return -1*self.d[self.find(x)]
n,m,k=map(int,input().split())
uf=UnionFind(n)
deg=[0 for i in range(n)]
to=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    uf.unite(a,b)
    deg[a]+=1
    deg[b]+=1
for i in range(k):
    a,b=map(int,input().split())
    a-=1
    b-=1
    to[a].append(b)
    to[b].append(a)
for i in range(n):
    ans=uf.size(i)-1-deg[i]
    for j in to[i]:
        if(uf.same(i,j)):ans-=1
    print(ans,end=" ")
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
score = [1]
for i in range(K):
    score[-1] *= A[i]
for i in range(K, N):
    temp = score[-1]//A[i-K]*A[i]
    if temp > score[-1]:
        print("Yes")
    else:
        print("No")
    score.append(temp)

### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
for i in range(K, N):
    if A[i-K] < A[i]:
         print("Yes")
    else:
        print("No")
### BUGGY CODE ###

import itertools

N = int(input())
S = input()

memory = []
for v in itertools.combinations(S, 3):
  memory.append(v)
print(len(set(memory)))

### FIXED CODE ###

N = int(input())
S = input()

ans = 0
for i in range(1000):
    num = str(i).zfill(3)
    if S.find(num[0]) == -1:
        continue  # 1文字目が合っているかどうか
    S1 = S[S.find(num[0])+1:]
    if S1.find(num[1]) == -1:
        continue  # 2文字目が合っているかどうか
    S2 = S1[S1.find(num[1])+1:]
    if S2.find(num[2]) == -1:
        continue  # 3文字目が合っているかどうか
    ans += 1
print(ans)
### BUGGY CODE ###


import sys
sys.setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = {}
for i in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    if a in T:
        T[a].append(b)
    else:
        T[a] = [b]
    if b in T:
        T[b].append(a)
    else:
        T[b] = [a]

d = [0] * N

for i in range(Q):
    p, x = map(int, input().split())
    d[p - 1] += x

def dfs(u, v = -1):
    global d
    if u in T:
        for p in T[u]:
            if p != v:
                d[p] += d[u]
                dfs(p, u)

dfs(0)


print(' '.join(map(str, d)))



### FIXED CODE ###

from sys import stdin,setrecursionlimit
input = stdin.readline
setrecursionlimit(1000000) 

N, Q = map(int, input().split())
T = [[] for _ in range(2 * (10 ** 5))]
for _ in range(N - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    T[a].append(b)
    T[b].append(a)

d = [0] * N

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

def dfs(u, v):
    global d
    for p in T[u]:
        if p == v:
            continue
        d[p] += d[u]
        dfs(p, u)

dfs(0, -1)

for v in d:
    print(v)
### BUGGY CODE ###

from math import factorial

def combinations_count(n, r):
    return factorial(n) // (factorial(n - r) * factorial(r))

def main():
    n, a, b = map(int, input().split())
    whole = 2**n-1
    a = combinations_count(n, a)
    b = combinations_count(n, b)
    print((whole-a-b)%(10**9+7))

if __name__ == "__main__":
    main()

### FIXED CODE ###

mod = 10**9+7 
n, a, b = map(int, input().split())
whole = pow(2, n, mod)-1 # 2^n-1(mod p)を計算。
# nCaの計算
comb1=1
for i in range(n-a+1,n+1): # n*(n-1)*(n-2)*...*(n-a+1)(mod p)を計算
  comb1 *= i
  comb1 %= mod
for i in range(1,a+1): # 1/a!(mod p)を計算 フェルマーの小定理:1/a = a^p-2(mod p)を利用
  comb1 *= pow(i,mod-2,mod)
  comb1 %= mod
comb2=1
for i in range(n-b+1,n+1): # n*(n-1)*(n-2)*...*(n-b+1)(mod p)を計算
  comb2 *= i
  comb2 %= mod
for i in range(1,b+1):
  comb2 *= pow(i,mod-2,mod)
  comb2 %= mod
whole -= (comb1+comb2)
whole %= mod
print(whole)
### BUGGY CODE ###

S = str(input())
Q = int(input())

topFlg = True
queries = [list(map(str, input().split())) for _ in range(Q)]

for query in queries:
    if query[0] == "1":
        topFlg = not (topFlg)
    else:
        if query[1] == "1":
            S = query[2] + S if topFlg else S + query[2]
        else:
            S = S + query[2] if topFlg else query[2] + S

if not topFlg:
    S = S[::-1]

print(S)


### FIXED CODE ###

S = str(input())
Q = int(input())

topFlg = True

leftStr = ""
rightStr = ""

for _ in range(Q):
    query = list(map(str, input().split()))
    if query[0] == "1":
        topFlg = not (topFlg)
    else:
        if query[1] == "1":
            if topFlg:
                leftStr = query[2] + leftStr
            else:
                rightStr += query[2]
        else:
            if topFlg:
                rightStr += query[2]
            else:
                leftStr = query[2] + leftStr

print(leftStr + S +
      rightStr if topFlg else rightStr[::-1] + S[::-1] + leftStr[::-1])
### BUGGY CODE ###

N = int(input())
numbers = [int(n) for n in input().split()]
mlt = 1
for n in numbers:
    mlt *= n
if mlt > 1000000000000000000:
    mlt = -1
print(mlt)
    

### FIXED CODE ###

N = int(input())
numbers = [int(n) for n in input().split()]
mlt = 1
if 0 in numbers:
    print(0)
else:
    for n in numbers:
        mlt *= n
        if mlt > 1000000000000000000:
            mlt = -1
            break
    print(mlt)
### BUGGY CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
B = []
C = []

for i in range(Q):
    b, c = map(int, input().split())
    B.append(b)
    C.append(c)

for i in range(Q):
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    print(sum(A))

### FIXED CODE ###

N = int(input())
A = list(map(int, input().split()))
Q = int(input())
X = [0] * (10**5)

for i in range(N):
    X[A[i]-1] += 1

ans = sum(A)

for j in range(Q):
    b, c = map(int, input().split())
    a = X[b-1]
    X[b-1] = 0
    X[c-1] += a
    ans = ans - a*b + c*a
    print(ans)
### BUGGY CODE ###

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

l = [""] * m

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

ans3 = [i for i in range(1,n+1)]
ans3 = set(ans3)


for i in range(m):
    ans2 = [j for j in range(1,n+1) if l[i][0] <= j <= l[i][1]]
    ans3 = ans3 & set(ans2)
    ans2.clear()
    
    
print(len(ans3))

### FIXED CODE ###

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

left_max = -1
right_min = n+1

for i in range(m):
    s,t = map(int,input().split())
    left_max = max(left_max,s)
    right_min = min(right_min, t)
    
print(max(0, right_min - left_max +1))