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

import sys
input=sys.stdin.readline
import string

def main():
    s = input().strip()
    t = input().strip()

    if not all(s.find(c) >= 0 for c in t):
        print(-1)
        exit()
    
    sa = [[] for _ in string.ascii_lowercase]
    for i,c in enumerate(s):
        sa[ord(c)-ord('a')].append(i+1)
#    print(sa)

    ls = len(s)
    ans = 1 # 条件を満たす整数
    i = 1 # s の何番目の文字から探し始めるか
    for c in t:
        a = sa[ord(c)-ord('a')]
        if len(a) == 0 or i > a[-1]:
            ans += ls-i+1
            i = 1
        for j in a:
            if j >= i:
                ans += j-i+1
                i = j+1
                break
#        print("c,a,ans,i=", c, a, ans, i)
    print(ans-1)

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import string
import bisect

def main():
    s = input().strip()
    t = input().strip()

    if not all(s.find(c) >= 0 for c in t):
        print(-1)
        exit()
    
    sa = [[] for _ in string.ascii_lowercase]
    ai = ord('a')
    for i,c in enumerate(s):
        sa[ord(c)-ai].append(i+1)
#    print(sa)

    ls = len(s)
    ans = 1 # 条件を満たす整数
    i = 1 # s の何番目の文字から探し始めるか
    for c in t:
        a = sa[ord(c)-ai]
        if len(a) == 0 or i > a[-1]:
            ans += ls-i+1
            i = 1
        bi = bisect.bisect_left(a,i)
        if bi < len(a):
            ans += a[bi]-i+1
            i = a[bi]+1
#        print("c,a,ans,i=", c, a, ans, i)
    print(ans-1)

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

import numpy as np
N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pnts = np.array([K] * N)
reduc = np.ones(N, int)

# main
for i in A:
    pnts -= reduc
    pnts[i - 1] += 1
    
# output
for i in pnts:
    print("{}".format("Yes" if i > 0 else "No"))

### FIXED CODE ###

N, K, Q = map(int, input().split())
A = [int(input()) for _ in range(Q)]
pnts = [0] * N

for i in A:
    pnts[i - 1] += 1

for i in pnts:
    if K - Q + i > 0:
        print("Yes")
    else:
        print("No")
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
num = [i for i in range(n)]
B = [0]*(n)
C = []
ans = 0
for i in range(n):
  if sum(B[j-1] for j in list(filter(lambda x:x%(n-i) == 0, num))) != A[n-i-1]:
    B[n-i-1] = 1
    ans += 1
    C.append(n-i)
print(ans)
print(*C)

### FIXED CODE ###

n = int(input())
A = list(map(int, input().split()))
num = [i for i in range(n)]
B = [0]*(n)
C = []
ans = 0
for i in range(n-1, -1, -1):
  ms = sum(B[i::i+1])
  if ms % 2 != A[i]:
    ans += 1
    C.append(i+1)
    B[i] = 1
print(ans)
print(*C)
### BUGGY CODE ###

X,Y,Z,K = map(int,input().split())
l_a = list(map(int,input().split()))
l_b = list(map(int,input().split()))
l_c = list(map(int,input().split()))
l_a.sort(reverse = True)  
l_b.sort(reverse = True)  
l_c.sort(reverse = True)
l_d = [a + b for a in l_a for b in l_b]
l_d.sort(reverse = True)
l_d[:3000]
l_e = [ab + c for ab in l_d for c in l_c]
l_e.sort(reverse = True)

for i in range(K):
    print(l_e[i])

### FIXED CODE ###

X,Y,Z,K=map(int,input().split())
A=[int(x) for x in input().split()]
A.sort(reverse=True)
B=[int(x) for x in input().split()]
B.sort(reverse=True)
C=[int(x) for x in input().split()]
C.sort(reverse=True)
D=[a+b for a in A for b in B]
D.sort(reverse=True)
D=D[:3000]
E=[ab+c for ab in D for c in C]
E.sort(reverse=True)
for i in range(K):
  print(E[i])
### BUGGY CODE ###

import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

ans=float("inf")
all_order=list(itertools.permutations(r))
for i in range(len(all_order)):
    tmp=0
    pre_location=all_order[i][0]-1
    for j in range(1,n):
        location=all_order[i][j]-1
        tmp+=d[pre_location][location]
        pre_location=location
    ans=min(ans,tmp)
print(ans)

### FIXED CODE ###

import itertools

N,M,R=map(int,input().split())
r=list(map(int,input().split()))
n=len(r)

graph=[[float("inf")]*N for _ in range(N)]
for i in range(M):
    A,B,C=map(int,input().split())
    A-=1
    B-=1
    graph[A][B]=C
    graph[B][A]=C

def dijkstra(start,cost):
    d=[float("inf")]*N
    used=[False]*N
    d[start]=0

    while True:
        v=-1
        for i in range(N):
            if (not used[i]) and (v==-1):
                v=i
            elif (not used[i]) and d[i]<d[v]:
                v=i
        if v==-1:
            break
        used[v]=True

        for j in range(N):
            d[j]=min(d[j],d[v]+cost[v][j])
    
    return d

d=[]
for i in range(N):
    d.append(dijkstra(i,graph))

ans=float("inf")
for city in itertools.permutations(r):
    tmp=0
    for i in range(n-1):
        tmp+=d[city[i]-1][city[i+1]-1]
    ans=min(ans,tmp)
print(ans)
### BUGGY CODE ###

import math

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)
  return divisors

def main():
  N = int(input().strip())
  A = list(map(int, input().strip().split()))
  divs_dict = dict()
  for a in A:
    divs = make_divisors(a)
    for d in divs:
      if d in divs_dict.keys():
        divs_dict[d] += 1
      else:
        divs_dict[d] = 1
  
  result_divs = []
  for k in divs_dict.keys():
    if divs_dict[k] >= N-1:
      result_divs.append(k)
  print(sorted(result_divs)[-1])

if __name__ == '__main__':
  main()

### FIXED CODE ###

import sys
input = sys.stdin.readline
import math
from fractions import gcd
import operator
from functools import reduce
from itertools import accumulate

def read():
    N = int(input().strip())
    A = list(map(int, input().strip().split()))
    return N, A


def prime_factorization_preprocess(n):
    """
    エラトステネスの篩を用いて、sqrt(n)以下の素数を列挙する
    """
    m = math.floor(math.sqrt(n)) + 1
    primes = []
    is_prime = [True for i in range(m)]
    for i in range(2, m):
        if is_prime[i]:
            primes.append(i)
            for j in range(i+i, m, i):
                is_prime[j] = False
    return primes


def prime_factorization(x, primes):
    """
    試し割り法により、数値の素因数分解を求める
    """
    factors = defaultdict(int)
    for p in primes:
        if x % p == 0:
            n = 0
            while x % p == 0:
                x //= p
                n += 1
            factors[p] = n
    return factors


def solve(N, A, AMAX = 10**9, INF=10**9):
    sl = list(accumulate(A, gcd))
    sr = list(reversed(list(accumulate(reversed(A), gcd))))
    max_gcd = sl[-1]
    for i in range(N):
        # gcdの単位元は0
        v = 0
        if i > 0:
            v = gcd(v, sl[i-1])
        if i < N-1:
            v = gcd(v, sr[i+1])
        max_gcd = max(max_gcd, v)
    return max_gcd


if __name__ == '__main__':
    inputs = read()
    print(solve(*inputs))
### BUGGY CODE ###

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

ans = []
for i in range(n):
  tmpidx = A.index(min(A))
  ans.append(tmpidx+1)
  A[tmpidx] = 10 ** 9
  
for a in ans:
  print(a)

### FIXED CODE ###

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

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

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

s = input()
q = int(input())
a=1
for _ in range(q):
  t = input()
  if t=='1':
    a *= -1
  else:
    if t[2]=='1':
      s = t[4:] + s[::a]
    else:
      s = s[::a] + t[4:]
    a=1
print(s[::a])

### FIXED CODE ###

s=input();q=int(input());r,a=0,[[],[]]
for _ in range(q):
  t=input()
  if t=='1':r=-(-~r%2)
  else:a[~-r+int(t[2])].append(t[4])
print(''.join(a[~-r+1][::-1])+s[::r or 1]+''.join(a[~-r+2]))
### BUGGY CODE ###

#!/usr/bin/python3

import sys
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

N, M = [int(x) for x in input().split()]
A = [int(x) for x in input().split()]
A.sort(reverse=True)

for _ in range(M):
    A[0] = A[0] // 2
    A.sort(reverse=True)

print(sum(A))



    

### FIXED CODE ###

#!/usr/bin/python3

import sys
import heapq
# input = sys.stdin.readline
sys.setrecursionlimit(100000)
MOD = 10 ** 9 + 7

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

Q = []
for a in A:
    heapq.heappush(Q, -a)

for _ in range(M):
    a = heapq.heappop(Q)
    a = (-a)//2
    heapq.heappush(Q, -a)



print(-sum(Q))
### BUGGY CODE ###

N = int(input())
emplist = [int(x) for x in input().split()]
sum = 0
for i in range(1,N+1):
    if sum < N-1:
        x = emplist.count(i)
        sum += x
        print(x)
    else:
        print(0)

### FIXED CODE ###

from collections import Counter
N = int(input())
emplist = [int(x) for x in input().split()]

ans = Counter(emplist)

for i in range(1,N+1):
    print(ans[i])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
n = int(input())
a = list(map(int, input().split()))
a.reverse()
mod = 7 + 10**9
leng = len(format(max(a), 'b'))
data = [[0 for i in range(leng+1)] for j in range(n)]
#pre
for i in range(n):
    k = list(bin(a[i]))
    k.reverse()
    ll = len(k)
    for j in range(1, leng+1):
        temp = data[i - 1][j]
        if j - 1 >= ll:
            data[i][j] = temp
            continue
        if k[j - 1] == "1":
            data[i][j] = temp + 1
        else:
            data[i][j] = temp
ans = 0
a.reverse()
data.reverse()
for i in range(n-1):
    k = format(a[i], 'b')
    k = list(k.zfill(leng))
    k.reverse()
    for j in range(leng):
        if k[j] == "1":
            ans += ((n - i - 1) - data[i+1][j+1]) * (2**j)
            ans %= mod
        else:
            ans += data[i+1][j+1] * (2**j)
            ans %= mod
print(ans)


### FIXED CODE ###

def main():
    import sys
    input = sys.stdin.readline
    n = int(input())
    a = list(map(int, input().split()))
    a.reverse()
    mod = 7 + 10**9
    leng = len(format(max(a), 'b'))
    bit_acc = [0 for i in range(leng)]
    for i in range(n):
        #先頭から二進数を0埋めした
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                bit_acc[j] += 1
    ans = 0
    p = [pow(2,leng - 1 - j, mod) for j in range(leng)]
    for i in range(n):
        bit_data = format(a[i], 'b').zfill(leng)
        for j in range(leng):
            if bit_data[j] == '1':
                ans += (n - bit_acc[j]) * p[j]
            else:
                ans += bit_acc[j] * p[j]
            ans %= mod
    print((ans * 500000004) % mod)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

n = int(input())
a = []
b = []
look = 1
end = 0
count = 0
for i in range(n):
    a.append(int(input()))
while end == 0:
    count += 1
    b.append(look)
    look = a[look - 1]
    for i in range(len(b)):
        if b[i] == look:
            end = -1
            break
    else:
        if look == 2:
            end = count
print(end)

### FIXED CODE ###

n = int(input())
a = []
b = [0]*n
look = 1
end = 0
count = 0
for i in range(n):
    a.append(int(input()))
while end == 0:
    count += 1
    b[look-1] = 1
    look = a[look - 1]
    if b[look - 1] == 1:
        end = -1
    else:
        if look == 2:
            end = count
print(end)
### BUGGY CODE ###

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

x = [[0 for _ in range(m)] for i in range(n)]
for i in range(m):
    l, r = [int(i) for i in input().split()]
    for j in range(l-1, r):
        x[j][i] = 1

counter = 0
for i in range(n):
    if sum(x[i]) == m:
        counter += 1

print(counter)

### FIXED CODE ###

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

ll = []
rr = []
for i in range(m):
    l, r = [int(i) for i in input().split()]
    ll.append(l)
    rr.append(r)

ans = min(rr) - max(ll) + 1
if ans < 0:
    ans = 0
print(ans)
### BUGGY CODE ###

n=int(input())
s=list(input())
x=[]
y=[]
z=[]
count=0

for i in range(n-2):
    y=[]
    if x.count(s[i])!=0:
        continue
    else:
        x.append(s[i])
        for j in range(i+1,n-1):
                for k in range(j+1,n):
                    v=s[j]+s[k]
                    if y.count(v)!=0:
                        continue
                    else:
                        y.append(v)
                        count+=1
                        if count==1000:
                            print(1000)
                            exit()
                        
                
        
    
print(count)


### FIXED CODE ###

n=int(input())
s=list(input())
count=0

for i in range(1000):
    if len(str(i))==1:
        i=str(0)+str(0)+str(i)
    elif len(str(i))==2:
        i=str(0)+str(i)
    else:
        i=str(i)
    x=0
    for j in range(n):
        if s[j]==i[x]:
            x+=1
            if x==3:
                count+=1
                break
print(count)
### BUGGY CODE ###

import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(input())
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [(0, s)]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      if v in vis: continue
      vis.add(v[1])
      for p in self.e[v[1]]:
        d[p[0]] = min(d[p[0]], d[v[1]] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, (d[p[0]], p[0]))
    return d[t]
d = dijkstra(N, e)
print(d.path(1, 0) + 1)

### FIXED CODE ###

import sys
from collections import defaultdict as dd
import heapq
input = sys.stdin.buffer.readline
N = int(input())
e = dd(list)
for i in range(1, N):
  n1 = 10 * i
  n2 = i + 1
  e[i].append((n1 % N, 0))
  e[i].append((n2 % N, 1))
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d[t]
d = dijkstra(N, e)
print(d.path(1, 0) + 1)
### BUGGY CODE ###

def main():
    s = input()
    t = input()
    ls = len(s)
    lt = len(t)
    dp = [[0] * (lt+1) for _ in range(ls+1)]

    for i in range(ls):
        for j in range(lt):
            if s[i] == t[j]:
                dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

    #import numpy as np
    #print(np.array(dp))

    #from collections import deque
    #ans = deque()

    ans = ''
    i, j = ls, lt
    while i > 0 and j > 0:
        if dp[i][j] == dp[i-1][j]:
            i -= 1
        elif dp[i][j] == dp[i][j-1]:
            j -= 1
        else:
            i -= 1
            j -= 1
            #ans.appendleft(s[i])
            ans = s[i] + ans
    #print(''.join(ans))
    print(ans)
if __name__ == '__main__':
    main()

### FIXED CODE ###

s = input()
t = input()
ls = len(s)
lt = len(t)
dp = [[0] * (lt+1) for _ in range(ls+1)]

for i in range(ls):
    for j in range(lt):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j]+1)
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i+1][j])
        dp[i+1][j+1] = max(dp[i+1][j+1], dp[i][j+1])

#import numpy as np
#print(np.array(dp))

#from collections import deque
#ans = deque()

ans = ''
i, j = ls, lt
while i > 0 and j > 0:
    if dp[i][j] == dp[i-1][j]:
        i -= 1
    elif dp[i][j] == dp[i][j-1]:
        j -= 1
    else:
        i -= 1
        j -= 1
        #ans.appendleft(s[i])
        ans = s[i] + ans
#print(''.join(ans))
print(ans)
### BUGGY CODE ###

# input
A, B, Q = map(int, input().split())
S, T, X = [], [], []
for _ in range(A):
    S.append(int(input()))

for _ in range(B):
    T.append(int(input()))

for _ in range(Q):
    X.append(int(input()))

# end of world
EOW = 10 ** 10

# boundary info
tbounds = [(T[i+1] + T[i]) // 2 for i in range(B-1)]
sbounds = [(S[i+1] + S[i]) // 2 for i in range(A-1)]

# add pivot
tbounds.insert(0, 0)
tbounds.append(EOW)
sbounds.insert(0, 0)
sbounds.append(EOW)

# temple to shrine
ttos = []
cur = 0
for i in range(B):
    while True:
        if T[i] <= sbounds[cur]:
            break
        cur += 1
    ttos.append(cur-1)

# shrine to temple
stot = []
cur = 0
for i in range(A):
    while True:
        if S[i] <= tbounds[cur]:
            break
        cur += 1
    stot.append(cur-1)

for x in X:
    snear = 0
    while True:
        if x <= sbounds[snear]:
            break
        snear += 1
    tnears_range = range(max(0, stot[snear-1]), min(stot[snear-1] + 4, B))
    best = abs(S[snear-1]-x) + abs(T[stot[snear-1]]-S[snear-1])
    for j in tnears_range:
        dist = abs(T[j]-x) + abs(S[ttos[j]]-T[j])
        if dist < best:
            best = dist
    # svisit = 0
    # tnear = 0
    # best = EOW * 2
    # # search
    # for i in range(A):
    #     tnear = stot[i]
    #     dist = abs(S[i]-x) + abs(T[tnear]-S[i])
    #     if best > dist:
    #         best = dist
    #     else:
    #         break
    # for i in range(max(0, tnear-3), min(tnear+3, B)):
    #     snear = ttos[i]
    #     dist = abs(T[i]-x) + abs(S[snear]-T[i])
    #     if best > dist:
    #         best = dist
    print(best)
    # print(min(min(abs(S[i]-x) + abs(T[nt]-S[i]) for (i, nt) in enumerate(stot)), min(abs(T[i]-x) + abs(S[ns]-T[i]) for (i, ns) in enumerate(ttos))))


### FIXED CODE ###

import bisect
A, B, Q = map(int, input().split())
INF = 10 ** 18
s = [-INF] + [int(input()) for i in range(A)] + [INF]
t = [-INF] + [int(input()) for i in range(B)] + [INF]
for q in range(Q):
    x = int(input())
    b, d = bisect.bisect_right(s, x), bisect.bisect_right(t, x)
    res = INF
    for S in [s[b - 1], s[b]]:
        for T in [t[d - 1], t[d]]:
            d1, d2 = abs(S - x) + abs(T - S), abs(T - x) + abs(S - T)
            res = min(res, d1, d2)
    print(res)
### BUGGY CODE ###

import math
def ncr(n,r):
    return math.factorial(n)//(math.factorial(n-r)*math.factorial(r))
def factorize(n):
    d = {}
    m = 2
    while m*m <= n:
        if n%m == 0:
            d[m] = 0
        while n%m == 0:
            n //= m
            d[m] += 1
        m += 1
    if n > 1:
        d[n] = 1
    return d
count = 1
n,m = map(int,input().split())
mod = 10**9+7
b = factorize(m)
for i in b:
    count *= ncr(b[i]+n-1,b[i])%mod
print(count%mod)

### FIXED CODE ###

N,M = map(int,input().split())
MOD = 10**9+7
from collections import Counter
c = Counter()
m = 2

while(m**2 <= M):
    if M%m == 0:
        while(M%m == 0):
            c[m] += 1
            M //= m
    else:
        m += 1
if M > 1 : c[M] += 1
MAXN = N+100
fac = [0 for _ in range(MAXN)]
inv = [0 for _ in range(MAXN)]
finv = [0 for _ in range(MAXN)]
fac[0] = fac[1] = 1
inv[1] = 1
finv[0] = finv[1] = 1
for i in range(2,MAXN):
    fac[i] = (i*fac[i-1]) % MOD
    inv[i] = (-inv[MOD%i]*(MOD//i))%MOD
    finv[i] = (finv[i-1]*inv[i])%MOD

def comb(n,k):
    return (fac[n]*(finv[k]*finv[n-k]%MOD))%MOD
ans = 1
for i in c:
    ans *= comb(c[i]+N-1,N-1)
    ans %= MOD
print(ans)
### BUGGY CODE ###

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

all = 0
ways =0
for k in range(n):
    delk = balls[0:k] + balls[k + 1::]
    all = 0
    ways= 0
    for i in range(1, n+1):
        a = delk.count(i)
        all += a
        ways += a*(a - 1) // 2
        if all>=n:
            break
    print(ways)


### FIXED CODE ###

n = int(input())
balls = list(map(int, input().split()))
conbi = [0]*n
for i in balls:
    conbi[i-1] +=1
result = 0
for j in range(n):
    result += (conbi[j]*(conbi[j]-1))//2
for k in balls:
    print(result-conbi[k-1]+1, end=" ")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

def main(N, A_list):
    mod = (10 ** 9) + 7
    tmp = []
    for i in range(len(A_list)):
        for j in range(i+1, len(A_list), 1):
            tmp.append(A_list[i] * A_list[j])

    val = 0
    for x in tmp:
        val += x

    print(val % mod)


N = int(input())
A_list = list(map(int, input().split()))
main(N, A_list)

### FIXED CODE ###

# -*- coding: utf-8 -*-

def main(N, A_list):
    total_list = []
    total = 0
    for i in range(len(A_list)):
        total += A_list[i]
        total_list.append(total)

    num = 0
    for i in range(len(A_list)-1):
        num += A_list[i] * (total_list[len(A_list)-1]-total_list[i])

    val = num % ((10 ** 9) + 7)
    print(val)


N = int(input())
A_list = list(map(int, input().split()))
main(N, A_list)
### BUGGY CODE ###

n = int(input())
A = list(map(int, input().split()))
X = [str(A[0])]
append_ = True if n % 2 != 0 else False
for a in A[1:]:
    if append_:
        X.append(str(a))
    else:
        X.insert(0, str(a))
    append_ = not append_
print(" ".join(X))


### FIXED CODE ###

from collections import deque
n = int(input())
A = list(map(int, input().split()))
X = deque([str(A[0])])
append_ = True if n % 2 != 0 else False
for a in A[1:]:
    if append_:
        X.append(str(a))
    else:
        X.appendleft(str(a))
    append_ = not append_
print(" ".join(X))
### BUGGY CODE ###

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

for i in range(n):
  print(syain.count(i+1))
  syain = [s for s in syain if s != i+1]


### FIXED CODE ###

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

b = [0]*(n+2)

for i in range(n-1):
  b[a[i]] += 1
  
for i in range(1,n+1):
  print(b[i])
### BUGGY CODE ###

#200404C
N, K = map(int, input().split())

while abs(N-K) < N:
    N = abs(N-K)
print(N)

### FIXED CODE ###

#200404C
N, K = map(int, input().split())
flag = 1
X = N%K
if abs(X-K)<X:
    print(abs(X-K))
else:
    print(X)
### BUGGY CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]

for p, q in pq_array:
    cnt = 0
    for l, r in lr_array:
        if p <= l and r <= q:
            cnt += 1
    print(cnt)


### FIXED CODE ###

n, m, q = map(int, input().split())
lr_array = [[int(x) for x in input().split()] for y in range(m)]
pq_array = [[int(x) for x in input().split()] for y in range(q)]


def solve1():
    table = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        table[l][r] += 1
    for i in range(1, n + 1):
        for j in range(1, n + 1):
            table[i][j] = table[i][j - 1] + table[i][j]
    for p, q in pq_array:
        res = 0
        for i in range(p, q + 1):
            # print(i)
            res += table[i][q]
        print(res)

    return 0


# 横軸：スタート
# 縦軸：ゴール
# 2次元累積和で解く
def solve2():
    cumulative_lr = [[0 for x in range(n + 1)] for y in range(n + 1)]
    for l, r in lr_array:
        for i in range(1, l + 1):
            for j in range(r, n + 1):
                cumulative_lr[i][j] += 1

    for p, q in pq_array:
        print(cumulative_lr[p][q])


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

sn,qn=map(int,input().split())
s=input()
x=list(list(map(int,input().split())) for _ in range(qn))

import math

s2=[0]*(sn+1)

for i in range(sn-1):
	if s[i]=='A' and s[i+1]=='C':
		s2[i]=0.5
		s2[i+1]=0.5

al=sum(s2)

for i in range(qn):
	res=al-math.ceil(sum(s2[:x[i][0]-1]))-math.ceil(sum(s2[x[i][1]:]))
	print(int(res))

### FIXED CODE ###

sn,qn=map(int,input().split())
s=input()
x=list(list(map(int,input().split())) for _ in range(qn))

s2=[0]*sn

for i in range(sn-1):
	if s[i]=='A' and s[i+1]=='C':
		s2[i+1]=s2[i]+1
	else:
		s2[i+1]=s2[i]

for i in range(qn):
	res=s2[x[i][1]-1]-s2[x[i][0]-1]
	print(res)