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

from numba import njit, i8
import numpy as np

n, k = map(int, input().split())
MOD = 998244353

lr = []
for _ in range(k):
    l, r = map(int, input().split())
    lr += (list(range(l, r + 1)))

lr.sort(reverse=True)
lr = np.array(lr)

dp = np.zeros(n, dtype=np.int64)
dp[0] = 1


@njit(cache=True)
def solve(n, lr, dp):
    for i in range(n - 1):
        for k in lr:
            if i + 1 - k >= 0:
                dp[i + 1] += dp[i + 1 - k]
                dp[i + 1] %= MOD
    return dp[-1]


print(solve(n, lr, dp))

### FIXED CODE ###

def solve(l, r, i):
    if i - l < 1:
        return 0
    return dp[i - l] - dp[max(i - r - 1, 0)]


n, k = map(int, input().split())
MOD = 998244353
lr = [list(map(int, input().split())) for _ in range(k)]

dp = [0] * (n + 1)
dp[1] = 1

for i in range(2, n + 1):
    tmp = 0
    for l, r in lr:
        tmp += solve(l, r, i)
    tmp = tmp % MOD
    dp[i] = (dp[i - 1] + tmp) % MOD

print(tmp)
### BUGGY CODE ###

# D - Not Divisible
def aline_mintomax(arr, N):
    for i in reversed(range(1,N)):
        for j in range(i):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]
    return arr

N = int(input()) # 【1行】1数字
num_list = list(map(int, input().split())) 
ind_list = [i for i in range(N)]
num_list = aline_mintomax(num_list, N)
for i in range(N-1):
    if num_list[i+1] == num_list[i]:
        ind_list.remove(i)
        continue
    for j in range(i):
        if num_list[i] % num_list[j] == 0 :
            ind_list.remove(i)
            break
for i in range(N-1):
    if num_list[N-1] % num_list[i] == 0 :
        ind_list.remove(N-1)
        break
print(len(ind_list))

### FIXED CODE ###

# D - Not Divisible
N = int(input())
a = list(map(int, input().split()))
a.sort()
MAX = a[-1]
l = [0]*(MAX+1)
for i in range(N):
    l[a[i]] += 1
    
answer = 0
for i in range(N):
    if l[a[i]] == 1:
        answer += 1
    for g in range(a[i], MAX+1, a[i]):
        l[g] = 10
print(answer)
### BUGGY CODE ###

#10:30
s = input()
n = len(s)
now = [1,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  last = now
  now = [0 for _ in range(13)]
  here = s[i]
  if here == '?':
    for k in range(10):
      for j in range(13):
        now[(10*j+k)%13] += last[j]
  else:
    k = int(here)
    for j in range(13):
      now[(10*j+k)%13] += last[j]
  for j in range(13):
    now[j] %= 10**9+7
print(now[5])

### FIXED CODE ###

#10:30
s = input()
n = len(s)
now = [1,0,0,0,0,0,0,0,0,0,0,0,0]
for i in range(n):
  last = now
  now = [0 for _ in range(13)]
  here = s[i]
  if here == '?':
    for k in range(10):
      for j in range(13):
        now[(10*j+k)%13] += last[j]
  else:
    k = int(here)
    for j in range(13):
      now[(10*j+k)%13] += last[j]
  for j in range(13):
    now[j] %= 10**9+7
print(now[5])
### BUGGY CODE ###

n=int(input())
ans=1
while ans<n:
  ans*=2
  if ans>n:
    ans//=2
print(ans)

### FIXED CODE ###

n=int(input())
ans=1
while ans<n:
  ans*=2
  if ans>n:
    ans//=2
    break
print(ans)
### BUGGY CODE ###

from itertools import permutations 
n,m=map(int,input().split())
cost=[]
for i in range(m):
    cost.append([int(i) for i in input().split()])
clr=[]
for i in range(n):
    clr.append([int(i) for i in input().split()])
l=[i for i in range(m)]
ind=[[] for i in range(210)]
for i in range(n):
    for j in range(n):
        curr=(i+1+j+1)%3 
        ind[curr].append(clr[i][j]-1)
mini=10**9 
for i in permutations(l,3): 
    curr=0 
    for j in range(3):
        for x in ind[j]: 
            curr+=cost[x][i[j]]
    mini=min(mini,curr)
print(mini)

### FIXED CODE ###

from itertools import permutations 
n,m=map(int,input().split())
cost=[]
for i in range(m):
    cost.append([int(i) for i in input().split()])
clr=[]
for i in range(n):
    clr.append([int(i) for i in input().split()])
l=[i for i in range(m)]
ind=[[0 for j in range(m)] for i in range(4)]
for i in range(n):
    for j in range(n):
        curr=(i+1+j+1)%3 
        ind[curr][clr[i][j]-1]+=1 
mini=10**9 
for i in range(m):
    for j in range(m):
        for k in range(m):
            if i==j or i==k or j==k:
                continue 
            curr=0 
            for it in range(3): 
                for it1 in range(m): 
                    if it==0:
                        k1=i 
                    elif it==1:
                        k1=j 
                    else:
                        k1=k 
                    curr+=ind[it][it1]*cost[it1][k1] 
            mini=min(mini,curr)
print(mini)
### BUGGY CODE ###

n=int(input())
l=[int(x) for x in input().split()]
c=0
for i in range(len(l)-2):
    for j in range(i+1,len(l)-1):
        for k in range(j+1,len(l)):
            if l[i]<l[j]+l[k] and l[j]<l[i]+l[k] and l[k]<l[i]+l[j]:
                c=c+1
print(c)                


### FIXED CODE ###

def CountTriangles( A): 
  n = len(A); 
  A.sort();  
  count = 0; 
  for i in range(n - 1, 0, -1): 
        l = 0; 
        r = i - 1; 
        while(l < r): 
            if(A[l] + A[r] > A[i]): 
                count += r - l;  
                r -= 1;  
            else:  
                l += 1;  
  print(count)
n=int(input())
l=[int(x) for x in input().split()]
CountTriangles(l)
### BUGGY CODE ###

# coding: utf-8
# Your code here!

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

def gcd(x, y):
    if x == 0:
        return y
    if y == 0:
        return x
        
    if y > x:
        temp = y
        y = x
        x = temp
    amari = x % y
    if amari == 0:
        return y
    else:
        return gcd(y, amari)
        
L = [0]
for i in range(N):
    l = L[-1]
    L.append(gcd(l, A[i]))
    
R = [0]
for i in reversed(range(N)):
    r = R[0]
    R.insert(0, gcd(r, A[i]))

M = [gcd(L[i], R[i+1]) for i in range(N)] # i=1,...,N

print(max(M))


### FIXED CODE ###

# coding: utf-8
# Your code here!

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

def gcd(x, y):
    if x == 0:
        return y
    if y == 0:
        return x
        
    if y > x:
        temp = y
        y = x
        x = temp
    amari = x % y
    if amari == 0:
        return y
    else:
        return gcd(y, amari)
        
L = list(range(N))
L[0] = 0
for i in range(N-1):
    L[i+1] = gcd(L[i], A[i])
    
R = list(range(N))
R.append(0)
for i in reversed(range(N)):
    R[i] = gcd(R[i+1], A[i])

M = [gcd(L[i], R[i+1]) for i in range(N)] # i=1,...,N

print(max(M))
### BUGGY CODE ###

from copy import deepcopy

a,b,n = [int(i) for i in input().split()]

score = 0
for i in range(n+1):
    tmp = int(a * i / b) - a * int(i / b)
    if score <= tmp:
        score = deepcopy(tmp)
    else:
        print(score)
        exit()
print(score)

### FIXED CODE ###


a,b,n = [int(i) for i in input().split()]

score = 0

if n < b:
  print(int(a * n / b) - a * int(n / b))
else:
  n = b-1
  print(int(a * n / b) - a * int(n / b))
### BUGGY CODE ###

from sys import stdin
 
N = int(stdin.readline().strip())
A = [int(x) for x in stdin.readline().strip().split(" ")]

sum_num = 0

for i in range(len(A)):
    flag = 0
    for j in range(len(A)):
        if i == j:
            continue
        if A[i] % A[j] == 0:
            flag = 1
            break
    if flag == 0:
        sum_num += 1
            

print(sum_num)


### FIXED CODE ###

from sys import stdin
 
N = int(input())
A = sorted(int(x) for x in input().split())
max_num = A[-1] + 1
count = [0] * max_num

for i in A:
    if count[i] != 0:
        count[i] = 2
        continue
    else:
        for j in range(i, max_num, i):
            count[j] += 1

sum_num = sum(count[i] == 1 for i in A)
print(sum_num)
### BUGGY CODE ###

import sys
input = sys.stdin.readline
N, Q = map(int, input().split())
STX = []
D = []
D2 = []
ans = [0]*Q
timer = 0
m = 0

for _ in range(N):
    stx = list(map(int, input().split()))
    STX.append(stx)
    if stx[2] > m:
        m = stx[2]

for _ in range(Q):
    ds = int(input())
    D.append(-ds)
    D2.append(-ds)

while True:
    for d in D:
        if d > 0:
            for s in STX:
                if d == s[2] and timer >= s[0] and timer < s[1]:
                    ans[D2.index(d-timer)] = D.pop(D.index(d))
                    break
                
    if D == []:
        break

    elif min(D) >= m:
        for a in ans:
            if a == 0:
                print(-1)
            else:
                print(a)
        break

    D = list(map(lambda x: x+1, D))
    timer += 1

### FIXED CODE ###

import sys
input = sys.stdin.readline
from bisect import bisect_left
N, Q = map(int, input().split())
W = [tuple(map(int, input().split())) for _ in range(N)]
W.sort(key=lambda x:x[2])
D = [int(input()) for _ in range(Q)]
ans = [-1]*Q
skip = [-1]*Q
for s, t, x in W:
    l = bisect_left(D, s-x)
    r = bisect_left(D, t-x)
    while l < r:
        if skip[l] == -1:
            ans[l] = x
            skip[l] = r
            l += 1
        else:
            l = skip[l]
print(*ans, sep='\n')
### BUGGY CODE ###

import itertools

N = int(input())
L = [int(x) for x in input().split(' ')]

count = 0
paris = list(itertools.combinations(L[1:], 2))
for i, a in enumerate(L[:-2]):
    count += sum([(a < b + c) * (b < c + a) * (c < a + b) for b, c in paris])
    del paris[:(N-i-2)]
print(count)



### FIXED CODE ###

N = int(input())
L = sorted([int(x) for x in input().split(' ')], reverse=True)

count = 0
while len(L) > 2:
    a = L.pop(0)
    ic = len(L) - 1
    for ib, b in enumerate(L):
        diff = a - b
        while L[ic] <= diff and ib < ic:
            ic -= 1
        count += ic - ib
        if ib >= ic:
            break

print(count)
### BUGGY CODE ###

import math
def main():
    #N,K,C=map(int,input().split())
    #A=list(map(int,input().split()))
    N=input()
    S=input()
    N=int(N)
    ans=0
    ind=[]
    tmp={"R":0,"G":0,"B":0}
    for i in S:
        tmp[i]+=1
        ind.append(tmp.copy())
    #print(ind)
    for i in range(0,N-2):
        for j in range(i+1,N-1):
            if S[i]==S[j]:
                continue
            for k in tmp.keys():
                if k!=S[i] and k!=S[j]:
                    col=k
                    break
            #print(i,j,col)
            if 2*j-i <N and S[j+j-i]==col:
                ans-=1
            ans+=(ind[-1][col]-ind[j][col])
    print(ans)

main()


### FIXED CODE ###

N=input()
S=input()
N=int(N)
ans=0
ind=[]
tmp={"R":0,"G":0,"B":0}
for i in S:
    tmp[i]+=1
    ind.append(tmp.copy())
#print(ind)
for i in range(0,N-2):
    for j in range(i+1,N-1):
        if S[i]==S[j]:
            continue
        for k in tmp.keys():
            if k!=S[i] and k!=S[j]:
                col=k
                break
        #print(i,j,col)
        if 2*j-i <N and S[j+j-i]==col:
            ans-=1
        ans+=(ind[-1][col]-ind[j][col])
print(ans)
### BUGGY CODE ###

N=int(input()) 
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):
    c[-1-j] +=int(bit[j])    
ans = 0
for i in range(k):
  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 ###

N=int(input())
A=[int(i) for i in input().split()]
C=[]
l=0
C.append(([(0,-1),(A[0],0)]))
for i in range(1,2**N):
  s=set()
  s.add((A[i],i))
  for k in range(l+1):
    if i&(1<<k):
      a,b=C[i^(1<<k)]
      s.add(a)
      s.add(b)
  s=sorted(list(s))
  C.append([s[-2],s[-1]])
  if i==2**(l+1)-1:
    l+=1
ans=[0]
for i in range(1,2**N):
  a,b=C[i]
  ans.append(max(ans[-1],a[0]+b[0]))
  print(ans[-1])

### FIXED CODE ###

N=int(input())
A=[int(i) for i in input().split()]
C=[]
l=0
C.append(([(0,-1),(A[0],0)]))
for i in range(1,2**N):
  biggest,second=(A[i],i),(0,-1)
  for k in range(l+1):
    if i&(1<<k):
      for a in C[i^(1<<k)]:
        if a[0]>biggest[0]:
          second=biggest
          biggest=a
        elif a[0]>second[0] and biggest!=a:
          second=a
  C.append([second,biggest])
  if i==2**(l+1)-1:
    l+=1
ans=[0]
for i in range(1,2**N):
  a,b=C[i]
  ans.append(max(ans[-1],a[0]+b[0]))
  print(ans[-1])
### BUGGY CODE ###

N, Q = map(int, input().split())
S = str(input())
SD = [0]*N

for n in range(N - 1):
    SD[n] = S[n]+S[n+1]

for q in range(Q):
    l, r = map(int, input().split())
    cnt = 0
    print(SD[l-1:r-1].count("AC"))

### FIXED CODE ###

N, Q = map(int, input().split())
S = str(input())
SD = {}

cnt = 0
for n in range(1, N):
    if S[n-1] + S[n] == "AC":
        cnt += 1
    SD[n] = cnt

for q in range(1, Q+1):
    l, r = map(int, input().split())
    print(SD.get(r-1, 0)-SD.get(l-1, 0))
### BUGGY CODE ###

n=int(input())
a=tuple(map(int,input().split()))
for cnt, val in enumerate(a):
    num=0
    for j in a[cnt:]:
        if j == cnt + 1:
            num += 1
    print(num)
print(0)

### FIXED CODE ###

import collections
N = int(input())
A = list(map(int, input().split()))
count = collections.Counter(A)
for n in range(N):
  print(count[n+1])
### BUGGY CODE ###

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

S = list(input())

ansList=[]
for i in range(N-1):
  if S[i] =="A" and S[i+1] =="C":
      ansList.append(1)
  else:
    ansList.append(0)

for i in range(Q):
  l,r = map(int, input().split())
  print(sum(ansList[l-1:r-1]))


### FIXED CODE ###

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

S = list(input())

ansList=[0]
ans=0
for i in range(N-1):
  if S[i] =="A" and S[i+1] =="C":
      ans+=1
      ansList.append(ans)
  else:
    ansList.append(ans)

for i in range(Q):
  l,r = map(int, input().split())
  print(ansList[r-1]-ansList[l-1])
### BUGGY CODE ###

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

for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

visited = [False] * n
def dfs(i, src, depth=0):
    global ans
    if depth==3:
        if not i in g[src]:
            g[src].append(i)
            g[i].append(src)
            ans+=1
    else:
        for t in g[i]:
            if visited[t]:
                continue
            else:
                visited[t] = True
                dfs(t, src, depth+1)
                visited[t] = False
    return

ans = 0
for i in range(n):
    visited[i] = True
    dfs(i, i, 0)
    visited[i] = False
print(ans)



### FIXED CODE ###

import sys
sys.setrecursionlimit(10**7)

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

for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

# 2部グラフかどうかを判定する
# 色の初期化、0:未着色
colors = [0]*n
def dfs(v, color):
    """
    parm v: node
    param color: 1 or -1
    """
    colors[v] = color
    for to in g[v]:
        if colors[to] == color:
            return False
        
        if colors[to] == 0:
            if not dfs(to, -color):
                return False
    return True

def is_bipartite():
    return dfs(0, 1)

if is_bipartite():
    # すべての対抗で辺が張れる
    print(colors.count(-1)*colors.count(1) - m)
else:
    # すべての対抗の辺が張れる
    print((n*(n-1))//2 - m)
### BUGGY CODE ###

# -*- coding utf-8 -*-
import math


def calc_C(n, r):
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M

# col
for i in range(M):
    ans += i * (M - i) * N * N

ans = ans * calc_C(N * M - 2, K - 2) % (10**9 + 7)
print(ans)


### FIXED CODE ###

# -*- coding utf-8 -*-
import math


def calc_C(n, r):
    return (math.factorial(n) // (math.factorial(n - r) * math.factorial(r))) % (10**9 + 7)


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

ans = 0

# row
for i in range(N):
    ans += i * (N - i) * M * M % (10**9 + 7)

# col
for i in range(M):
    ans += i * (M - i) * N * N % (10**9 + 7)

ans = ans % (10**9 + 7)
ans = ans * calc_C(N * M - 2, K - 2) % (10**9 + 7)
print(ans)
### BUGGY CODE ###

import numpy as np
N, K, Q = map(int, input().split())
A = np.array([K] * N)
for q in range(Q):
    answered = int(input())
    A[answered - 1] += 1
    A = A - 1
    #print(A)

for item in A:
    if item <= 0:
        print('No')
    else:
        print('Yes')

### FIXED CODE ###

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

answered = [K - Q] * N

for q in range(Q):
    correct = int(input())
    answered[correct - 1] += 1
for item in answered:
    if item <= 0:
        print('No')
    else:
        print('Yes')
### BUGGY CODE ###

import math
# Calculate amount of water that won't oveflow
def calc(a,b,deg): 
    
    rad = math.radians(deg)
    deg90_in_rad = math.radians(90)
    a_sect = a*math.sin(rad) - b*math.sin(deg90_in_rad - rad)
    b_sect = b*math.sin(deg90_in_rad - rad) - a*math.sin(rad) # 縦と水の切片

    if b_sect >= 0:
        sqr_a = a * b_sect 
        tri_a = (b-b_sect)*a*1/2  

    else:
        sqr_a = 0
        tri_a = (a - a_sect) * b *1/2

    if b*math.tan(math.pi/2-rad)>a:
        return (a*b - a*math.tan(rad)*a*1/2) *a
    else:
        return b*math.tan(rad/2-rad)*b*1/2*a
    # print(a_sect, b_sect)
    return (sqr_a + tri_a) * a

import bisect
def main():
    a, b, x = list(map(int, input().split()))

    left = 0
    right = 90
    deg = 45
    while True:
        y = calc(a, b, deg)
        if abs(y - x) < 10**-6:
            break
        if y > x:
            deg, left = (right+deg)/2, deg
        elif y < x:
            deg, right = (left+deg)/2, deg
        
    print(deg)

if __name__ == "__main__":
    main()


### FIXED CODE ###

import math
# Calculate amount of water that won't oveflow
def calc(a,b,deg): 
    
    rad = math.radians(deg)
    # deg90_in_rad = math.radians(90)
    # a_sect = a*math.sin(rad) - b*math.sin(deg90_in_rad - rad)
    # b_sect = b*math.sin(deg90_in_rad - rad) - a*math.sin(rad) # 縦と水の切片

    # if b_sect >= 0:
    #     sqr_a = a * b_sect 
    #     tri_a = (b-b_sect)*a*1/2  

    # else:
    #     sqr_a = 0
    #     tri_a = (a - a_sect) * b *1/2
    # total_area = (sqr_a + tri_a) 

    if b*math.tan(math.pi/2-rad) <= a:
        total_area = (b*math.tan(math.pi/2-rad)*b*1/2)
    if b*math.tan(math.pi/2-rad)>a:
        total_area = (a*b - a*math.tan(rad)*a*1/2)       

    return total_area * a

import bisect
def main():
    a, b, x = list(map(int, input().split()))

    left = 0
    right = 90
    deg = 45
    while True:
        y = calc(a, b, deg)
        if y - x >= -10 ** -7 and y - x <= 0:
            break
        if y > x:
            deg, left = (right+deg)/2, deg
        elif y < x:
            deg, right = (left+deg)/2, deg
    print(deg)

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

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy

def main():
    n = int(input())
    a = list(map(int, input().split()))
    for i in range(n):
        tmp_a = deepcopy(a)
        tmp_a[i] = -1
        tmp_a_c = Counter(tmp_a)
        tmp_a_cc = [tmp_a_c[i] for i in tmp_a_c if tmp_a_c[i] > 1]
        r = 0
        for cc in tmp_a_cc:
            r += factorial(cc) // (factorial(2) * factorial(cc-2))
        print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

from math import factorial
from itertools import combinations
from collections import Counter
from copy import deepcopy
from operator import mul
from functools import reduce

def cmb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under

def main():
    n = int(input())
    a = list(map(int, input().split()))
    a_c = Counter(a)
    a_c_sum = 0
    for c in a_c:
        if a_c[c] >= 2:
            a_c_sum += cmb(a_c[c], 2)

    for ea in a:
        if a_c[ea] <= 1:
            sa = 0
        elif a_c[ea] == 2:
            sa = 1
        else:
            sa = cmb(a_c[ea], 2) - cmb(a_c[ea] - 1, 2)
        print(a_c_sum - sa)


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

import sys
read = sys.stdin.read
readlines = sys.stdin.readlines
def main():
    n, k = map(int, input().split())
    r = n
    nums = set()
    while True:
        n = abs(n - k)
        if n in nums:
            break
        else:
            r = min(r, n)
            nums.add(n)
    print(r)


if __name__ == '__main__':
    main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    n = abs(n - (n // m) * m)
    n = min(n, abs(n - m))
    print(n)

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

import numpy as np

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

for i in range(n):
  x = a[i]
  t = t * x


if t > 10**18:
    print('-1')
else:
    print(t)

### FIXED CODE ###

import numpy as np

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

if any([i == 0 for i in a]):
    print('0')
else:
    for i in range(n):
        x = a[i]
        t = t * x
        if x == 0:
            break
        if t > 10**18:
            break

    if t > 10**18:
        print('-1')
    else:
        print(t)
### BUGGY CODE ###

from collections import deque
S=deque(input())
Q=int(input())
for _ in range(Q):
    target = input()
    if target == '1':
        S.reverse()
    else:
        a,b,c=target.split()
        if b=='1':
            S.appendleft(c)
        else:
            S.append(c)
print(''.join(list(S)))

### FIXED CODE ###

from collections import deque
S=deque(input())
Q=int(input())
r='1'
for _ in range(Q):
    target = input()
    if target == '1':
        if r=='1':
            r='2'
        else:
            r='1'
    else:
        a,b,c=target.split()
        if b=='1' and r=='1':
            S.appendleft(c)
        elif b=='2' and r=='1':
            S.append(c)
        elif b=='1' and r=='2':
            S.append(c)
        else:
            S.appendleft(c)
if r=='2':
    S.reverse()
print(''.join(list(S)))
### BUGGY CODE ###

import itertools


def read():
    N = int(input())

    return N,


def solve(N, ):
    move = 1000000000000
    for i in range(N//2):
        a = i + 1
        if N % a != 0:
            continue
        b = N // a
        move = min(move, a + b - 2)
    return move


if __name__ == '__main__':
    input = read()
    print(solve(*input))


### FIXED CODE ###

import itertools


def read():
    N = int(input())

    return N,


def solve(N, ):
    move = 1000000000000
    a = 1
    b = N
    while a < b:
        b = N // a
        if N % a == 0:
            move = min(move, a + b - 2)
        a += 1
    return move


if __name__ == '__main__':
    input = read()
    print(solve(*input))