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

n = int(raw_input())

li = []
for i in range(n):
    cmd = raw_input().split()
    if cmd[0] == 'insert':
        li.append(cmd[1])
    elif cmd[0] == 'delete':
        try:
            p = li[::-1].index(cmd[1])
            li.pop(-p-1)
        except:
            pass
    elif cmd[0] == 'deleteFirst':
        li.pop()
    elif cmd[0] == 'deleteLast':
        li.pop(0)
for e in li[::-1]:
    print e,

### FIXED CODE ###

import sys,gc
    
A=[]
fp =0
bp =0

n=int(raw_input())
while n:
    s = raw_input()
    if s[0] == 'i':
        A.append(int(s[7:]))
        fp += 1
    elif s[6] == ' ':
        try:
            i = A[::-1].index(int(s[7:]))
            if i!=-1:
                del A[-i-1]
                fp -=1
        except:
            pass
    elif s[6] == 'F':
        A.pop()
        fp -=1
    elif s[6] == 'L':
        bp +=1
    n -=1

for e in A[bp:fp+1][::-1]:
    print int(e),
### BUGGY CODE ###

import sys
input = sys.stdin.readline


def calc(N, adj, ignore, dp, prevs):
    s, t = ignore
    if len(adj[s]) == 1:
        return float("Inf")
    if ignore[0] != -1:
        adj[s].remove(t)
    for i in range(prevs, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        for nxt in adj[i]:
            dp[i] += (dp[nxt] + 1) / n
    if ignore[0] != -1:
        adj[s].add(t)

    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    x = [(-1, -1)] + [None] * M
    for i in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
        x[i+1] = (s-1, t-1)
    x.sort(reverse=True)
    ans = float("Inf")
    dp = [0.0] * (N)
    prevs = N - 1
    for ignore in x:
        tmp = calc(N, adj, ignore, dp, prevs)
        ans = min(ans, tmp)
        if tmp != float("inf"):
            prevs = ignore[0]
    print(ans)


if __name__ == "__main__":
    main()


### FIXED CODE ###

def calc(N, adj, dp, ignore):
    s, t = ignore
    for i in range(N-1, -1, -1):
        dp[i] = 0.0
        n = len(adj[i])
        if i == s:
            n -= 1
        for nxt in adj[i]:
            if i == s and nxt == t:
                continue
            dp[i] += (dp[nxt] + 1) / n
    return dp[0]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        s, t = map(int, input().split())
        adj[s-1].add(t-1)
    dp1 = [0.0] * N
    ans = calc(N, adj, dp1, (-1, -1))
    dp2 = [0.0] * N
    for i in range(N-1, -1, -1):
        if len(adj[i]) <= 1:
            continue
        j = i
        mx = -1
        for nxt in adj[i]:
            if dp1[nxt] > mx:
                j = nxt
                mx = dp1[nxt]
        tmp = calc(N, adj, dp2, (i, j))
        ans = min(ans, tmp)
    print(ans)


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

import sys
input = sys.stdin.readline

R, G, B, N = map(int, input().split())

r = N // R
g = N // G
b = N // B

c = 0
for i in range(r + 1):
    for j in range(g + 1):
        t = N - i * R - j * G
        if t == 0:
            c += 1
            continue
            
        if t < 0:
            continue
            
        if t % B == 0:
            c += 1
                
print(c)

### FIXED CODE ###

import sys
input = sys.stdin.readline

R, G, B, N = map(int, input().split())

r = N // R

c = 0
for i in range(r + 1):
    p = N - i * R
    for j in range(int(p // G) + 1):
        t = p - j * G
        if t == 0:
            c += 1
            break
            
        if t % B == 0:
            c += 1
                
print(c)
### BUGGY CODE ###

n=int(raw_input())
a=map(int,raw_input().split())
now=a
while 1:
    l=len(now)
    if l==1:
        print(now[0])
        break
    if now[l/2-1]==now[l/2] or now[l/2]==now[l/2+1]:
        print(now[l/2])
        break
    if now[l/2-1]<now[l/2]<now[l/2+1]:
        if now[l/2-2]>=now[l/2]:
            print(now[l/2])
            break
        if now[l/2+2]<=now[l/2]:
            print(now[l/2])
            break
    if now[l/2+1]<now<now[l/2-1]:
        if now[l/2+2]>=now[n/l]:
            print(now[l/2])
            break
        if now[l/2-2]<=now[l/2]:
            print(now[l/2])
            break
    else:
        nx=[]
        for i in xrange(l-2):
            tmp=[]
            tmp.append(now[i])
            tmp.append(now[i+1])
            tmp.append(now[i+2])
            tmp.sort()
            nx.append(tmp[1])
        now=nx


### FIXED CODE ###

def check(m):
    tmpa = [-1] * 2 * n
    for i in xrange(2 * n - 1):
        if a[i] < m:
            tmpa[i] = 0
        else:
            tmpa[i] = 1

    idx = n -1
    while idx < 2 * n - 1:
        idx += 1
        if tmpa[idx - 1] == tmpa[idx]:
            rr = tmpa[idx]
            ridx = idx - 1
            break
    else:
        rr = -1
        ridx = 2 * n - 1

    idx = n - 1
    while idx > 0:
        idx -= 1
        if tmpa[idx + 1] == tmpa[idx]:
            ll = tmpa[idx]
            lidx = idx + 1
            break
    else:
        ll = -1
        lidx = -1

    if rr == ll == -1:
        if n % 2 == 0:
            if tmpa[n - 1] == 1:
                return False
            else:
                return True
        else:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
    elif ridx - (n - 1) == (n - 1) - lidx:
        if rr != ll:
            if tmpa[n - 1] == 1:
                return True
            else:
                return False
        else:
            if rr==1:
                return True
            else:
                return False
    elif ridx - (n - 1) > (n - 1) -lidx:
        if ll == 1:
            return True
        else:
            return False
    else:
        if rr == 1:
            return True
        else:
            return False

n = int(raw_input())
a = map(int,raw_input().split())
l = 1
r = 2 * n
while r - l > 1:
    m = (r + l)/2
    if check(m):
        l = m
    else:
        r = m
print(l)
### BUGGY CODE ###

H,W = map(int,input().split())
G=[input() for _ in range(H)]
A=[[[0,0,0,0] for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(1,W):
    if G[h][w-1] == '.':
      A[h][w][0] = A[h][w-1][0]+1
  for w in range(W-2,-1,-1):
    if G[h][w+1] == '.':
      A[h][w][1] = A[h][w+1][1]+1
for w in range(W):
  for h in range(1,H):
    if G[h-1][w] == '.':
      A[h][w][2] = A[h-1][w][2]+1
  for h in range(H-2,-1,-1):
    if G[h+1][w] == '.':
      A[h][w][3] = A[h+1][w][3]+1
ans=0
for h in range(H):
  for w in range(W):
    if G[h][w] == '.':
      ans = max(ans,sum(A[h][w])+1)
print(ans)

### FIXED CODE ###

H,W = map(int,input().split())
G=[input() for _ in range(H)]
A_u=[[0 for _ in range(W)] for _ in range(H)]
A_d=[[0 for _ in range(W)] for _ in range(H)]
A_r=[[0 for _ in range(W)] for _ in range(H)]
A_l=[[0 for _ in range(W)] for _ in range(H)]
for h in range(H):
  for w in range(1,W):
    if G[h][w-1] == '.':
      A_r[h][w] = A_r[h][w-1]+1
  for w in range(W-2,-1,-1):
    if G[h][w+1] == '.':
      A_l[h][w] = A_l[h][w+1]+1
for w in range(W):
  for h in range(1,H):
    if G[h-1][w] == '.':
      A_d[h][w] = A_d[h-1][w]+1
  for h in range(H-2,-1,-1):
    if G[h+1][w] == '.':
      A_u[h][w] = A_u[h+1][w]+1
ans=0
for h in range(H):
  for w in range(W):
    if G[h][w] == '.':
      ans = max(ans,A_r[h][w]+A_l[h][w]+A_d[h][w]+A_u[h][w]+1)
print(ans)
### BUGGY CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
B = A[:][::-1]

def ncr(n, r, p):
  num = den = 1
  for i in range(r):
    num = (num * (n - i)) % p
    den = (den * (i + 1)) % p
  return (num * pow(den, p - 2, p)) % p
p=10**9+7

comb = {}
for i in range(K-1, N):
  comb[(i, K-1)] = ncr(i, K-1, p)

ans = 0
for i in range(K-1, N):
  ans += A[i] * comb[(i, K-1)]
  ans %= p 
for i in range(K-1, N):
  ans -= B[i] * comb[(i, K-1)]
  ans %= p
print(ans)


### FIXED CODE ###

N, K = map(int, input().split())
A = list(map(int, input().split()))
A = sorted(A)
B = A[:][::-1]

fac = [1, 1]
finv = [1, 1]
inv = [0, 1]
Mod = 10**9+7
def COMinit():
  #N_C_kのN
  for i in range(2, 10**5+10):
    fac.append(fac[-1]*i%Mod)
    inv.append((-inv[Mod%i] * (Mod//i)) % Mod)
    finv.append(finv[-1] * inv[-1] % Mod)


def COM(n, k):
  if n < 0 or k < 0 or n < k:
    return 0
  return fac[n] * (finv[k] * finv[n-k] % Mod) % Mod

COMinit()

comb = {}
for i in range(K-1, N):
  comb[(i, K-1)] = COM(i, K-1)

ans = 0
for i in range(K-1, N):
  ans += A[i] * comb[(i, K-1)]
  ans %= Mod
for i in range(K-1, N):
  ans -= B[i] * comb[(i, K-1)]
  ans %= Mod
print(ans)
### BUGGY CODE ###

"""nCk (逆元ver) """
def comb(n,k):
    nCk = 1
    mod = 998244353
    for i in range(n-k+1, n+1):
        nCk *= i
        nCk %= mod
    for i in range(1, k+1):
        nCk *= pow(i, mod-2, mod)
        nCk %= mod
    return nCk

n,m,k = map(int,input().split())
mod = 998244353
ans = 0

for x in range(k+1):
    if x==0:
        ans += m*pow(m-1, n-1, mod)
        ans %= mod
    else:
        ans += m*pow(m-1, n-1-x, mod)*comb(n-1, x)
        ans %= mod
print(ans%mod)

### FIXED CODE ###

class Cmb:
    def __init__(self, N, mod=998244353):
        self.fact = [1,1]
        self.fact_inv = [1,1]
        self.inv = [0,1]
        
        """ 階乗を保存する配列を作成 """
        for i in range(2, N+1):
            self.fact.append((self.fact[-1]*i) % mod)
            self.inv.append((-self.inv[mod%i] * (mod//i))%mod)
            self.fact_inv.append((self.fact_inv[-1]*self.inv[i])%mod)
    
    """ 関数として使えるように、callで定義 """
    def __call__(self, n, r, mod=998244353):
        if (r<0) or (n<r):
            return 0
        r = min(r, n-r)
        return self.fact[n] * self.fact_inv[r] * self.fact_inv[n-r] % mod

n,m,k = map(int,input().split())
mod = 998244353
ans = 0
c = Cmb(N=n, mod=mod)
for x in range(k+1):
    if x==0:
        ans += m*pow(m-1, n-1, mod)
        ans %= mod
    else:
        ans += m*pow(m-1, n-1-x, mod)*c(n-1, x)%mod
        ans %= mod
print(ans%mod)
### BUGGY CODE ###

K,S = map(int,input().split())
c=0
L=list(range(0,K+1))
for i in L:
    for j in L:
        for k in L:
            if i+j+k == S:
                c+=1
print(c)

### FIXED CODE ###

K,S = map(int, input().split())
res = 0
for x in range(0,K+1):
    for y in range(0,K+1):
        if 0 <= S - x - y <= K:
            res += 1
print(res)
### BUGGY CODE ###

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

f = [1, 1]
for i in range(n-1)[::-1]:
  if i+1 in alist and i+2 in alist:
    print(0)
    exit()
  elif i+1 in alist and i+2 not in alist:
    f = [f[1]] + [f[0]]
  elif i+1 not in alist and i+2 in alist:
    f = [f[0]] + [f[0]]
  else:
    f = [f[0]+f[1]] + [f[0]]
     
print(int(f[0]%div_num))

### FIXED CODE ###

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

if n == 1:
  print(1)
  exit()

f = [0 for i in range(n)]
f[-2:] = [1, 1]
for i in range(m):
  f[int(input())-1] = -1

div_num = 1000000007

for i in range(n-2)[::-1]:
  if f[i] == -1:
    continue
  if f[i+1] == -1 and f[i+2] == -1:
    print(0)
    exit()
  elif f[i+1] == -1 and f[i+2] != -1:
    f[i] = f[i+2]
  elif f[i+1] != -1 and f[i+2] == -1:
    f[i] = f[i+1]
  else:
    f[i] = f[i+1]+f[i+2]

if f[0] != -1 and f[1] != -1:
  print(int((f[0]+f[1])%div_num))
elif f[0] == -1 and f[1] != -1:
  print(int(f[1]%div_num))
elif f[0] != -1 and f[1] == -1:
  print(int(f[0]%div_num))
else:
  print(0)
### BUGGY CODE ###

import sys
from collections import deque


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


def main():
    H, W, M = map(int, input().split())
    lh = [0] * H
    lw = [0] * W
    s = set()
    for _ in range(M):
        h, w = map(int, input().split())
        lh[h - 1] += 1
        lw[w - 1] += 1
        s.add((h-1, w-1))

    maxh = max(lh)
    maxw = max(lw)
    for i in range(H):
        if lh[i] !=maxh:
            continue
        for j in range(W):
            if lw[j] !=maxw:
                continue
            if (i,j) not in s:
                print(maxh+maxw)
                exit()

    print(maxh+maxw-1)



if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
from collections import deque


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


def main():
    H, W, M = map(int, input().split())
    lh = [0] * H
    lw = [0] * W
    s = set()
    for _ in range(M):
        h, w = map(int, input().split())
        lh[h - 1] += 1
        lw[w - 1] += 1
        s.add((h-1, w-1))

    maxh = max(lh)
    maxw = max(lw)
    wlist=[]
    for j in range(W):
        if maxw==lw[j]:
            wlist.append(j)



    for i in range(H):
        if lh[i] !=maxh:
            continue
        for j in wlist:
            if (i,j) not in s:
                print(maxh+maxw)
                exit()

    print(maxh+maxw-1)



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

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

for i in range(m):
    b, c = map(int, input().split())
    test = test + [c for i in range(b)]
test.sort(reverse=True)
print(sum(test[:n]))

### FIXED CODE ###

from collections import defaultdict

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

test_dict = defaultdict(int)

for j in test:
    test_dict[j] += 1

for k in range(m):
    b, c = map(int, input().split())
    test_dict[c] += b

count = 0
sum_val = 0
for l in sorted(test_dict, reverse=True):
    if n-count>0:
       sum_val += l * min(test_dict[l], n-count)
       count += min(test_dict[l], n-count)
    else:
       break
print(sum_val)
### BUGGY CODE ###

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

def calc(n):
    return sum([i for i in range(1, n+1)]) / n
ex = []
for i in p:
    ex.append(calc(i))
    
max_ex = 0
for i in range(0, N-(K-1)):
    temp = sum(ex[i:i+K])
    if temp > max_ex:
        max_ex = temp

print(max_ex)

### FIXED CODE ###

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

Es = [(1+p_i)/2 for p_i in p]

t = sum(Es[0:k])
ans = t

for i in range(n-k):
    t -= Es[i]
    t += Es[i+k]
    ans = max(ans,t)

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

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
memo = [[] for _ in range(N + 1)]


def dfs(s, p=-1):
    sub_tree = []
    for t in edge[s]:
        if t == p:
            continue
        sub_tree.append(dfs(t, s))
    memo[s].extend(sub_tree)
    return sum(sub_tree) + 1


dfs(1)
for i in range(2, N + 1):
    x = sum(memo[i])
    rest = N - x - 1
    memo[i].append(rest)


cnt = 0
for lis in memo[1:]:
    if len(lis) == 1:
        continue
    # 頂点iが穴あきとならない->頂点から伸びてるやつ1つだけ黒の場合がダメ
    tmp = pow(2, N - 1, mod) - 1  # ぜんぶ白の場合を引いとく
    for x in lis:
        black = pow(2, x, mod) - 1
        tmp = (tmp - black + mod) % mod
    cnt = (cnt + tmp) % mod

div = pow(2, N, mod)
ans = cnt * pow(div, mod - 2, mod) % mod
print(ans)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)
mod = 10 ** 9 + 7

N = int(input())
edge = [[] for _ in range(N + 1)]
for _ in range(N - 1):
    x, y = map(int, input().split())
    edge[x].append(y)
    edge[y].append(x)

# 頂点iから伸びてる枝それぞれのサイズ
ans = 0
pow2 = [1] * (N + 1)
for i in range(1, N + 1):
    pow2[i] = pow2[i - 1] * 2 % mod


def dfs(s, p=-1):
    global ans
    res = 1
    tmp = pow2[N-1] - 1
    for t in edge[s]:
        if t == p:
            continue
        size = dfs(t, s)
        res += size
        tmp = (tmp - pow2[size] + 1 + mod) % mod
    if N != res:
        tmp = (tmp - pow2[N-res] + 1 + mod) % mod
    ans = (ans + tmp) % mod
    return res


dfs(1)
div = pow2[N]
print(ans*pow(div, mod-2, mod) % mod)
### BUGGY CODE ###

import fractions
from functools import reduce
import copy


def gcd_list(numbers):
    return reduce(fractions.gcd, numbers)


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

ans = 1
for i in range(N):
    a = copy.copy(A)
    a.pop(i)
    g = gcd_list(a)
    if g > ans:
        ans = g
print(ans)


### FIXED CODE ###

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

    divisors.sort(reverse=True)
    return divisors


N = int(input())
A = sorted([int(x) for x in input().split()])

ans = 1
for i in range(2):
    div_list = make_divisors(A[i])

    for div_i in div_list:
        wrong_count = 0

        for A_i in A:
            if A_i % div_i != 0:
                wrong_count += 1

        if wrong_count <= 1 and div_i > ans:
            ans = div_i

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

mod = int(1e9 + 7)
N = int(input())
A = list(map(int, input().split()))
S = 0
j = 1
for c in range(61):
  m = 0
  n = 0
  for i in range(N):
    if A[i] % 2 == 1:
      m += 1
    else:
      n += 1
    A[i] //= 2
  S += ((m * n) * j) % mod
  j *= 2
  j %= mod
  S %= mod
S %= mod
print(S)


### FIXED CODE ###

mod = int(1e9 + 7)
N = int(input())
A = [format(i, '060b') for i in map(int, input().split())]
S = 0
for k in range(60):
  s = [b[59-k] for b in A]
  v = s.count('0')*s.count('1')
  S += (v<<k)
S %= mod
print(S)
### BUGGY CODE ###

import collections

n = int(input())
s = [''.join(sorted(list(input()))) for i in range(n)]


cnt = 0
for i in range(len(s)):
    d = collections.Counter()
    d.update(s[i+1:])
    cnt += d[s[i]]

print(cnt)

### FIXED CODE ###

n = int(input())
s = [''.join(sorted(input())) for i in range(n)]

cnt = 0
dic = {}
for i in s:
    dic.setdefault(i, 0)
    cnt += dic[i]
    dic[i] += 1

print(cnt)
### BUGGY CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    min = 2020
    for i in range(l, r + 1):
        for j in range(l, i):
            if i * j % 2019 <= min:
                min = i * j % 2019

    print(min)

if __name__ == "__main__":
    main()


### FIXED CODE ###

def main():
    (l, r) = list(map(int, input().split()))

    ans = 2020
    for i in range(l, min(r + 1, l + 2019)):
        for j in range(i + 1, min(r + 1, i + 2020)):
            mod = i * j % 2019
            if mod <= ans:
                ans = mod

    print(ans)

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

#各丸太を何回切るか、どこで切るか
#丸太iをKi回切る場合、その丸太の最小はL//Kiとなる
#あとは、どの丸太を何回切るかを求めればよい。
"""
長い丸太ほど多く切るべき
丸太が2本、1本が10**9でもう一本が1。10**9回切れるのであれば1本目に全振りするのがベスト。

結論、元の長さの比に基づいて割り当てればよい。
一番短い丸太の長さを1として各丸太の
"""
from math import ceil
import heapq
N,K = map(int,input().split())
A = list(map(int,input().split()))
A.sort()
pivot = A[0]
hiritu = [int(ceil(a/pivot)) for a in A]
hirituSum = sum(hiritu)
kaisu = []
for i in range(N):
    h = hiritu[i]
    k = int(K*h/hirituSum)
    kaisu.append(k)
    K -= k
"""
if K >= 1000000:
    for i in range(N):
        h = hiritu[i]
        k = int(ceil(K*h/hirituSum))
        kaisu.append(k)
        K -= k
"""
leng = []
for i in range(N):
    a = A[i]
    k = kaisu[i]
    leng.append(((-a/(k+1)),k,a))
heapq.heapify(leng)
for _ in range(K):
    l,k,a = heapq.heappop(leng)
    l = -a/(k+2)
    heapq.heappush(leng,(l,k+1,a))
l,k,a = heapq.heappop(leng)
l *= -1
print(ceil(l))

### FIXED CODE ###

from math import ceil
N,K = map(int,input().split())
A = list(map(int,input().split()))

def is_ok(X):
    #最大値をX以下にできるか
    cnt = 0
    for a in A:
        cnt += ceil(a/X)-1
    return cnt <= K

def bisearch(high,low):
    while high - low > 1:
        mid = (high+low)//2
        if is_ok(mid):
            high = mid
        else:
            low = mid
    return high

print(bisearch(10**9+1,0))
### BUGGY CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        for l in range(k+1):
            if i + j + l == s:
                count += 1
print(count)

### FIXED CODE ###

k, s = map(int, input().split())
count = 0
for i in range(k+1):
    for j in range(k+1):
        if 0 <= s - (i + j) <= k:
            count += 1
print(count)
### BUGGY CODE ###

def abs_min(current, move):
    f = current+move
    b = current-move
    if abs(f) <= abs(b):
        return f
    else:
        return b
    
nums = [int(e) for e in input().split()]
current = nums[0]
num = nums[1]
move = nums[2]

#print(current)
for i in range(num):
    current = abs_min(current, move)
    #print(current)

print(abs(current))


### FIXED CODE ###

nums = [int(e) for e in input().split()]
current = nums[0]
num = nums[1]
move = nums[2]


current = abs(current)

res = current // move

if res >= num:
    print(current - move*num)
else:
    current = current - move * res
    num -= res
    if num%2 == 0:
        print(current)
    else:
        print(abs(current-move))
### BUGGY CODE ###

dict={}
dict2={}
n,m=map(int,input().split())
for i in range(m):
	p,m=map(int,input().split())
	dict[i]=[p,m]
	if p not in dict2:
		dict2[p]=[m]
	else:
		dict2[p].append(m)
for d in dict:
	a='{:0=6}'.format(dict[d][0])
	c=sorted(dict2[dict[d][0]]).index(dict[d][1])+1
	c='{:0=6}'.format(c)
	print(a+c)

### FIXED CODE ###

n,m=map(int,input().split())
pys=[0]*m
for i in range(m):
	p,y=map(int,input().split())
	pys[i]=(p,y,i)
pys.sort(key=lambda x:x[1])

num=[0]*n
ans=[0]*m
for p,y,i in pys:
	num[p-1]+=1
	ans[i]=str(p).zfill(6)+str(num[p-1]).zfill(6)

for a in ans:
	print(a)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline
    N = int(input())
    A = list(map(int, input().split(" ")))

    mod = 10**9+7
    res = 0
    for i in range(N-1):
        for j in range(i, N):
            if i >= j: continue
            res += A[i] * A[j]
    print(res % mod)

if __name__ == "__main__":
    main()

### FIXED CODE ###

import sys
 
def main():
    def input():return sys.stdin.readline()[:-1]
    N = int(input())
    A = list(map(int, input().split(" ")))
 
    mod = 10**9+7
    res = 0

    S = sum(A)
    S2 = sum(map(lambda x: x**2, A))
    print((S**2-S2) // 2 % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

# https://atcoder.jp/contests/abc122/tasks/abc122_c
import itertools

N, Q = map(int, input().split())
N = int(N)
S = input()
lr = []
for _ in range(Q):
    l, r = map(int, input().split())
    lr.append((l - 1, r - 1))
locations = []
for i in range(N - 1):
    if S[i] == 'A' and S[i + 1] == 'C':
        locations.append(i)
# print(locations)

for l, r in lr:
    subset = list(itertools.filterfalse(lambda x: x < l, locations))
    subset = list(itertools.filterfalse(lambda x: x > r, subset))
    # print(l, r, subset)
    num_substring = len(subset)
    # print('num_substring', num_substring)
    if num_substring == 0:
        print(0)
        continue
    if subset[-1] == r:
        print(num_substring - 1)
    else:
        print(num_substring)


### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
cnt = [0]
for i in range(2, len(S) + 1):
    if S[i - 2:i] == 'AC':
        v = cnt[-1] + 1
    else:
        v = cnt[-1]
    cnt.append(v)

# print('cnt', cnt)
for _ in range(Q):
    l, r = map(int, input().split())
    ans = cnt[r - 1] - cnt[l - 1]
    print(ans)