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

s = list(input().strip())
n = len(s)
end = n - 2

count = 0

if n >= 3:
  while True:
    changed = False
    i = 0
    while i < end:
      if s[i] == 'A' and s[i + 1] == 'B' and s[i + 2] == 'C':
        changed = True
        if i >= 1 and s[i - 1] == 'A':
          s[i - 1] = 'B'
          s[i] = 'C'
          s[i + 1] = 'A'
          s[i + 2] = 'A'
          count = count + 2
          i = i + 2
        else:
          s[i] = 'B'
          s[i + 1] = 'C'
          s[i + 2] = 'A'
          count = count + 1
          i = i + 2
      else:
        i = i + 1

    if not changed:
      break

print(count)

### FIXED CODE ###

s = input().strip().replace('BC', 'D')
n = len(s)

count = 0
a_count = 0
for i in range(n):
  if s[i] == 'A':
    a_count += 1
  elif a_count > 0 and s[i] == 'D':
    count += a_count
  else:
    a_count = 0

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

N = int(input())
s_list=[]

for _ in range(N):
    s_list.append(input())
    
count=0
for i in range(N):
    for j in range(i+1,N):
        s1=[]
        s2=[]
        for k in range(10):
            s1.append(s_list[i][k])
            s2.append(s_list[j][k])
        if sorted(s1)==sorted(s2):
            count+=1
print(count)

### FIXED CODE ###

N = int(input())
s_list=[]
s_dict={}
count=0

for i in range(N):
    s = "".join(sorted(input()))
    if s not in s_dict:
        s_dict[s]=0
    else:
        s_dict[s]+=1
        count+=s_dict[s]
print(count)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

n, *a = map(int, read().split())
mod = 10 ** 9 + 7
bit = [0] * 61
ans = 0
for aa in a:
    for j, check in enumerate(bin(aa)[2:][::-1]):
        if check == '1':
            bit[j] += 1
for i, b in enumerate(bit):
    ans += pow(2, i, mod) * ((n - b) * b % mod)
    ans %= mod
print(ans)


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
sys.setrecursionlimit(10 ** 7)

import numpy as np

n = int(readline())
a = np.array(read().split(), np.int64)
ans = 0
mod = 10 ** 9 + 7
for i in range(63):
    b = (a >> i) & 1
    x = np.count_nonzero(b)
    y = n - x
    x *= y
    for j in range(i):
        x *= 2
        x %= mod
    ans += x
print(ans % mod)
### BUGGY CODE ###

from itertools import combinations
from functools import reduce
from operator import mul
N = int(input())


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


A = factorization(N)
l = []
for a in A:
    l += [a[0]] * a[1]

ans = 0
for i in range(1, len(l)+1):
    for s in set(combinations(l, i)):
        r = reduce(mul, s) - 1
        if r == 0:
            continue
        if N // r == N % r:
            ans += r

print(ans)

### FIXED CODE ###

N = int(input())


def divisor(n): #nの約数を全て求める
    i = 1
    table = []
    while i * i <= n:
        if n%i == 0:
            table.append(i)
            table.append(n//i)
        i += 1
    table = list(set(table))
    return table


A = divisor(N)
A = [i - 1 for i in A]

ans = 0
for a in A:
    if a == 0:
        continue
    if N // a == N % a:
        ans += a

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

ans=1
a,b=map(int,input().split())
if a<0 and b>0:
    print ("Zero")
else:
    for i in (range(a,b+1)):
        ans*=i
    if ans>0:
        print ("Positive")
    else:
        print ("Negative")

### FIXED CODE ###

a,b=map(int,input().split())
if a<=0<=b:
    print ("Zero")
elif (min(0,b)-a)%2:
    print ("Positive")
else:
    print ("Negative")
### BUGGY CODE ###

class Dijkstra():
    """ ダイクストラ法
    重み付きグラフにおける単一始点最短路アルゴリズム

    * 使用条件
        - 負のコストがないこと
        - 有向グラフ、無向グラフともにOK

    * 計算量はO(E*log(V))

    * ベルマンフォード法より高速なので、負のコストがないならばこちらを使うとよい
    """
    class Edge():
        """ 重み付き有向辺 """
        def __init__(self, _to, _cost):
            self.to = _to
            self.cost = _cost

    def __init__(self, V):
        """ 重み付き有向辺
        無向辺を表現したいときは、_fromと_toを逆にした有向辺を加えればよい

        Args:
            V(int): 頂点の数
        """
        self.G = [[] for i in range(V)]  # 隣接リストG[u][i] := 頂点uのi個目の隣接辺
        self._E = 0  # 辺の数
        self._V = V  # 頂点の数

    @property
    def E(self):
        """ 辺数
        無向グラフのときは、辺数は有向グラフの倍になる
        """
        return self._E

    @property
    def V(self):
        """ 頂点数 """
        return self._V

    def add(self, _from, _to, _cost):
        """ 2頂点と、辺のコストを追加する """
        self.G[_from].append(self.Edge(_to, _cost))
        self._E += 1

    def shortest_path(self, s):
        """ 始点sから頂点iまでの最短路を格納したリストを返す
        Args:
            s(int): 始点s
        Returns:
            d(list): d[i] := 始点sから頂点iまでの最短コストを格納したリスト。
                     到達不可の場合、値はfloat("inf")
        """
        import heapq
        que = []  # プライオリティキュー（ヒープ木）
        d = [10**15] * self.V
        d[s] = 0
        heapq.heappush(que, (0, s))  # 始点の(最短距離, 頂点番号)をヒープに追加する

        while len(que) != 0:
            cost, v = heapq.heappop(que)
            # キューに格納されている最短経路の候補がdの距離よりも大きければ、他の経路で最短経路が存在するので、処理をスキップ
            if d[v] < cost: continue

            for i in range(len(self.G[v])):
                # 頂点vに隣接する各頂点に関して、頂点vを経由した場合の距離を計算し、今までの距離(d)よりも小さければ更新する
                e = self.G[v][i]  # vのi個目の隣接辺e
                if d[e.to] > d[v] + e.cost:
                    d[e.to] = d[v] + e.cost  # dの更新
                    heapq.heappush(que, (d[e.to], e.to))  # キューに新たな最短経路の候補(最短距離, 頂点番号)の情報をpush
        return d

def main():
    N,M=map(int,input().split())
    key=[]
    for i in range(0,M):
        a,b=map(int,input().split())
        c=list(map(int,input().split()))
        s=sum(2**(c[j]-1) for j in range(0,b))
        key.append((s,a))


    node=2**N
    djk=Dijkstra(node)
    for i in range(0,M):
        for j in range(0,node):
            s,a=key[i]
            djk.add(j,s|j,a)

    d=djk.shortest_path(0)
    if d[node-1]==10**15:
        print(-1)
    else:
        print(d[node-1])

if __name__=="__main__":
    main()

### FIXED CODE ###

N,M=map(int,input().split())
key=[]
cost=[]
for i in range(0,M):
    a,b=map(int,input().split())
    c=list(map(int,input().split()))
    s=sum(2**(c[j]-1) for j in range(0,b))
    key.append(s)
    cost.append(a)

node=2**N

dp=[[10**10 for i in range(0,node)] for j in range(0,M)]

for i in range(0,M):
    dp[i][node-1]=0
#i:何番までか j:手に入れた鍵
for i in range(0,M):
    for j in range(1,node):
        k=node-1-j
        if i==0:
            if k|key[0]==node-1:
                dp[0][k]=cost[0]
        else:
            dp[i][k]=min(dp[i-1][k],dp[i-1][k|key[i]]+cost[i])

if dp[M-1][0]>=10**10:
    print(-1)
else:
    print(dp[M-1][0])
### BUGGY CODE ###

S = input('')
Q = int(input(''))
for i in range(Q):
    str = input('')
    if(str.count(' ') == 0 and str == '1'):
        S = S[::-1]
    elif(str[0] == '2' and str[2] == '1'):
        S = '{0}{1}'.format(str[4], S)
    elif(str[0] == '2' and str[2] == '2'):
        S = '{0}{1}'.format(S, str[4])
print(S)

### FIXED CODE ###

S = input('')
Q = int(input(''))
head, tail, rev_flag = '', '', 1
for i in range(Q):
    char = input()
    if char == '1':
        rev_flag *= -1
    else:
        t, f, c = char.split()
        if (f == '1' and rev_flag == 1) or (f == '2' and rev_flag == -1):
            head = c + head
        elif (f == '2' and rev_flag == 1) or (f == '1' and rev_flag == -1):
            tail = tail + c
if rev_flag == 1:
    print(head, S, tail, sep='')
else:
    print(tail[::-1], S[::-1], head[::-1], sep='')
### BUGGY CODE ###

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

max_A=max(AB)[0]+h
DP=[float("inf")]*max_A
DP[0]=0

for i in range(h):
    for a,b in AB:
        DP[i+a]=min(DP[i+a],DP[i]+b)

print(min(DP[h:]))

### FIXED CODE ###

h,n=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(n)]

A_max=max(AB)[0]
DP=[0]+[float("inf")]*(h+A_max)
for i in range(h):
    if DP[i]==float("inf"):continue
    for a,b in AB:
        t=DP[i]+b
        if t<DP[i+a]:
            DP[i+a]=t
print(min(DP[h:]))
### BUGGY CODE ###

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

cnt = 0
for i in range(N-1):
    if S[i] == '#' and S[i+1] == '.':
        tmp_S = list(S)
        tmp_S[i+1] = '#'
        S = "".join(tmp_S)
        cnt += 1

print(cnt)


### FIXED CODE ###

from itertools import accumulate


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

black = [0 for _ in range(N)]
white = [0 for _ in range(N)]

for i, s in enumerate(S):
    if s == '#':
        black[i] = 1
    else:
        white[i] = 1

# 累積和
black = [0] + black
black = list(accumulate(black))
white = [0] + white[::-1]
white = list(accumulate(white))[::-1]

ans = []
for i in range(N+1):
    ans.append(black[i] + white[i])

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

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


def solve(n, k, a):
    ch = set([i for i in range(n)])
    for _ in range(k):
        if len(ch) == 0:
            break
        b = [0] * n
        ii = list(ch)
        for i in ii:
            cnt = 0
            for j in range(n):
                if j - a[j] - 0.5 < i < j + a[j] + 0.5:
                    cnt += 1
            b[i] = cnt
            if b[i] == n:
                ch.remove(i)
        a = b
    return a


def main():
    n, k = ria()
    a = ria()
    wia(solve(n, k, a))


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
def rs(): return sys.stdin.readline().rstrip()
def ri(): return int(sys.stdin.readline())
def ria(): return list(map(int, sys.stdin.readline().split()))
def ws(s): sys.stdout.write(s + '\n')
def wi(n): sys.stdout.write(str(n) + '\n')
def wia(a): sys.stdout.write(' '.join([str(x) for x in a]) + '\n')


def solve(n, k, a):
    # wia(a)
    for _ in range(k):
        b = [0] * n
        for i in range(n):
            l = max(0, i - a[i])
            r = min(n-1, i + a[i])
            b[l] += 1
            if r < n-1:
                b[r+1] -= 1
        for i in range(1, n):
            b[i] += b[i-1]
        a = b
        # wia(a)
        if sum(a) == n * n:
            break
    return a


def main():
    n, k = ria()
    a = ria()
    wia(solve(n, k, a))


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

import sys

N, M = list(map(int, input().split()))
E = [[] for i in range(N)]

for i in range(M):
    a, b = list(map(int, input().split()))
    a -= 1; b -= 1
    E[a].append(b)
    E[b].append(a)
    
par = [-1] * N
q = [(0, 0)]

while q:
    v, p = q.pop(0)
    
    if par[v] != -1: continue
    par[v] = p
    
    for u in E[v]:
        q.append((u, v))
    
for p in par[1:]:
    if p == -1:
        print('No')
        sys.exit()
        
print('Yes')
for p in par[1:]:
    print(p+1)

### FIXED CODE ###

import sys
input=sys.stdin.readline
from collections import deque

def main():
    N, M = list(map(int, input().split()))
    E = [deque() for i in range(N)]
    
    for i in range(M):
        a, b = list(map(int, input().split()))
        a -= 1; b -= 1
        E[a].append(b)
        E[b].append(a)
        
    par = [-1] * N
    q = deque([(0, 0)])
    c = 0
    while q:
        v, p = q.popleft()
        
        if par[v] != -1: continue
        par[v] = p+1
        c += 1
        
        for u in E[v]:
            if par[u] != -1: continue
            q.append((u, v))
        
    if c < N: print('No')
    else: 
        print('Yes')
        print('\n'.join(list(map(str, par[1:]))))
            
if __name__ == '__main__':
    main()
### BUGGY CODE ###

N = int(input())
L = sorted(list(map(int, input().split())))
cnt = 0
for i in range(len(L)):
    for j in range(i + 1, len(L)):
        for k in range(j + 1, len(L)):
            a, b, c = L[i], L[j], L[k]
            if c >= a + b:
                break
            if a < b + c and b < c + a:
                cnt += 1
print(cnt)


### FIXED CODE ###

from bisect import bisect_left

N = int(input())
L = sorted(list(map(int, input().split())))

ans = 0
for i in range(N):
    for j in range(i + 1, N):
        a = L[i]
        b = L[j]
        idx = bisect_left(L, a + b)
        ans += idx - 1 - j
print(ans)
### BUGGY CODE ###

n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a.sort(reverse=True)
a=a+[0]

i=0
while(1):
  while a[0]>=a[1]:
    a[0]=a[0]/2
    i=i+1
    if i==m:
      break
  if i==m:
    break
  a.sort(reverse=True)
 
ans=0
for i in range(n):
  ans=ans+int(a[i])
print(ans)

  

### FIXED CODE ###

#リストの挿入と最大値の取得を同時に行う
#そのようなものを高速でできるデータ構造としてheapq(優先度つきqがあげられる)
#最大値を取得する関数はheapqには入ってないためリストの要素を-1倍してから最小値を求めればいい
n,m=list(map(int,input().split()))
a=list(map(int,input().split()))
a=list(map(lambda x:x*(-1),a))

import heapq
heapq.heapify(a)
for i in range(m):
  min_a=heapq.heappop(a)*(-1)
  heapq.heappush(a,min_a//2*(-1))
print(sum(a)*(-1))
### BUGGY CODE ###

N = int(input())
a=0
flag=0
for i in range(1,10**6):
    a+=7*10**(i-1)
    if a%N==0:
        print(i)
        flag=1
        break
if flag==0:
    print(-1)

### FIXED CODE ###

N = int(input())
a=0
flag=0
for i in range(1,N+1):
    a=(a*10+7)%N   
    if a==0:
        print(i)
        flag=1
        break

if flag==0:
    print(-1)
### BUGGY CODE ###

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

graph = [[float('inf')]*H*W for _ in range(H*W)]
nv = [(-1, 0), (1, 0), (0, -1), (0, 1)]

for h in range(H):
    for w in range(W):
        if S[h][w]=='.':
            for nx, ny in nv:
                if H <= h+nx or h+nx < 0 or W <= w+ny or w+ny < 0:
                    continue
                if S[h+nx][w+ny]=='.':
                    graph[W*h+w][W*(h+nx)+(w+ny)] = 1

for k in range(H*W):
    for i in range(H*W):
        for j in range(H*W):
            graph[i][i]=0
            graph[i][j] = min(graph[i][j], graph[i][k] + graph[k][j])
ans = 0
for i in range(H*W-1):
    for j in range(i+1, H*W):
        if graph[i][j] != float('inf'):
            ans = max(ans, graph[i][j])
print(ans)

### FIXED CODE ###

from collections import deque
H, W = map(int, input().split())
area = ['#']*(W+2)
for i in range(H):
    area += ['#']+list(input())+['#']
area += ['#']*(W+2)
H+=2
W+=2
move = [-1, 1, W, -W]
ans = 0
for i in range(H):
    for j in range(W):
        st = W*i+j
        if area[st]=='#': continue
        dq = deque([])
        dist = [-1]*(H*W)
        dq.append(st)
        dist[st] = 0
        while dq:
            now = dq.popleft()
            for dx in move:
                nxt = now+dx
                if dist[nxt]>=0 or area[nxt]=='#': continue
                dist[nxt] = dist[now]+1
                ans = max(ans, dist[nxt])
                dq.append(nxt)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
def query():
    p = b_num-1
    q = n+b_num-2
    res=mx
    while q-p>1:
        if p&1 == 0:
            res = min(res,segl[p])
        if q&1 == 1:
            res = min(res,segl[q])
            q -= 1
        p = p//2
        q = (q-1)//2
    if p == q:
        res = min(res,segl[p])
    else:
        res = min(min(res,segl[p]),segl[q])
    return res


if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            c = query()
            print(c if c!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)


### FIXED CODE ###

import sys
input = sys.stdin.readline

n,Q=map(int,input().split())
b_num = 2**(n-1).bit_length()
mx = 10**9
segl=[mx]*2*b_num 

def update( k, x):
    k += b_num-1
    segl[k] = x
    while k+1:
        k = (k-1)//2
        segl[k] = min(segl[k*2+1],segl[k*2+2])
    
if __name__ == '__main__':
    xs = []
    for i in range(n):
        s,t,x=map(int,input().split())
        xs += [(s-x-0.4,True,x,i), (t-x-0.5,False,x,i)]
    for _ in range(Q):
        xs.append((int(input()),2))
    xs.sort(key=lambda x:x[0])
    for x in xs:
        if x[1]==2:
            print(segl[0] if segl[0]!= mx else -1)
            continue
        update(x[3], x[2] if x[1] else mx)
### BUGGY CODE ###

k,s = map(int,input().split())

ans = 0
if(s == 0):
  print(1)
  exit()
elif(s == 3*k):
  print(1)
  exit()
  
for i in range(0,k+1):
  for j in range(0,k+1):
    for k in range(0,k+1):
      if(i + j + k == s):
        ans += 1
        
print(ans)

### FIXED CODE ###

k,s = map(int,input().split())

ans = 0
if(s == 0):
  print(1)
  exit()
elif(s == 3*k):
  print(1)
  exit()
  
for i in range(0,k+1):
  for j in range(0,k+1):
    z = s - i - j
    if(z >= 0 and z <= k):
      ans += 1
        
print(ans)
### BUGGY CODE ###

n = int(input())
s = []

for i in range(n):
	s.append(sorted(list(input())))

s = sorted(s)
count = 0
for i in range(n-1):
	for j in range(i+1,n):
		if s[i] == s[j]:
			count += 1
		else:
			break


print(count)



### FIXED CODE ###



n = int(input())
s = []

def comb2(x):
	if x==0:
		return 0
	ans = x*(x-1)/2
	return ans

for i in range(n):
	s.append(sorted(list(input())))

s = sorted(s)
count = [0 for _ in range(len(s))]

x = 0

for i in range(n-1):
	if s[i] == s[i+1]:
		count[x] += 1
	else:
		count[x] += 1
		x = x + 1
	if i == n-2:
		count[x] += 1

ans = 0
#print (count)
for i in count:
	ans += comb2(i)


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


N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
ans = [[0]*1 for _ in range(N+1)]
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    ans[data[i][0]].append(data[i][2])

for j in range(1,M+1):
    a = P[j-1]
    b = ans[a].index(j)
    print(str(a*(10**6)+b).zfill(12))






### FIXED CODE ###


N,M = list(map(int, input().split()))
P = []
Y = []
for _ in range(M):
    p,y = list(map(int, input().split()))
    P.append(p)
    Y.append(y)
count = [0]*(N+1)
ans = [0]*(M+1)
data = [[p,y,i] for p,y,i in zip(P,Y,range(1,M+1))]

data.sort(key=lambda x: x[1])

for i in range(M):
    count[data[i][0]] += 1
    ans[data[i][2]] = count[data[i][0]]


for j in range(1,M+1):
    a = P[j-1]
    b = ans[j]
    print(str(a*(10**6)+b).zfill(12))
### BUGGY CODE ###

A = int(input())
B = int(input())
C = int(input())
X = int(input())

if min(A, B, C, X) == X:
	print(0)

def num_patterns(A, B, C, X):
    if X == 0:
      	return 1

    if min(A, B, C, X) == X:
        return 0
    branch_A = num_patterns(A - 1, B    , C    , X - 500) if A > 0 else 0
    branch_B = num_patterns(A    , B - 1, C    , X - 100) if B > 0 else 0
    branch_C = num_patterns(A    , B    , C - 1, X - 50 ) if C > 0 else 0
    return branch_A + branch_B + branch_C

print(num_patterns(A, B, C, X))

### FIXED CODE ###

import functools

A = int(input())
B = int(input())
C = int(input())
X = int(input())

if min(A, B, C, X) == X:
	print(0)

@functools.lru_cache(1000)
def num_patterns(A, B, C, X):
    if X == 0:
      	return 1

    if min(A, B, C, X) == X:
        return 0

    if A > 0:
        return sum(
            num_patterns(0, B, C, X - 500 * nA) if X >= 500 * nA else 0
            for nA in range(0, A + 1)
        )
    if B > 0:
        return sum(
            num_patterns(0, 0, C, X - 100 * nB) if X >= 100 * nB else 0
            for nB in range(0, B + 1)
        )
    if C > 0 and X % 50 == 0 and X / 50 <= C:
        return 1
    else:
        return 0

print(num_patterns(A, B, C, X))
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [T.count(i) for i in range(2019)]
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))

    # mx = int(S) // 2019
    # print(mx)
    # bl = [2019 * i for i in range(1, mx+1)]
    # ct = 0
    # for b in bl:
    #     blen = len(str(b))
    #     for i in range(len(S) - blen + 1):
    #         s = S[i:(i+blen)]
    #         if s == b:
    #             ct += 1
    # print(ct)

    # bf = [0 for _ in range(2019)]
    # for i in range(len(S)):



    # sl = [int(S[i]) for i in range(len(S))]
    # ct = 0
    # for i in range(len(S)):
    #     crt = sl[i]
    #     for j in range(i, len(S)):
    #         if i != j:
    #             crt *= 10
    #             crt += sl[j]
    #         # s = S[i:(j+1)]
    #         # si = int(s)
    #         if crt % 2019 == 0:
    #             ct += 1
    # print(ct)
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

if __name__ == '__main__':
    main()

### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(S: str):
    T = [0 for _ in range(len(S) + 1)]
    for i in range(len(S) - 1, -1, -1):
        T[i] = (T[i+1] + int(S[i]) * pow(10, len(S) - 1 - i, 2019)) % 2019
    # T = [int(S[i:]) % 2019 if i < len(S) else 0 for i in range(len(S) + 1)]
    M = [0 for _ in range(2019)]
    # M = [T.count(i) for i in range(2019)]
    for t in T:
        M[t] += 1
    ct = 0
    for m in M:
        ct += m * (m - 1) / 2

    print(int(ct))
    return


# Generated by 1.1.6 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    # S = int(next(tokens))  # type: int
    S = str(next(tokens))
    solve(S)

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

first_step_string = input()
query_num = int(input())
query_li = list()
for _ in range(query_num):
    query_li.append(input().split())

ans = first_step_string
for query in query_li:
    if query[0] == '1':
        ans = ans[::-1]
    else:
        if query[1] == '1':
            ans = query[2] + ans
        else:
            ans += query[2]

print(ans)


### FIXED CODE ###

from collections import deque

s = deque(input())
query_num = int(input())
query_li = list()
for _ in range(query_num):
    query_li.append(input().split())

rev_flag = False
for query in query_li:
    if query[0] == '1':
        rev_flag = not rev_flag
    elif (query[1] == '1' and rev_flag) or (query[1] == '2' and not rev_flag):
        s.append(query[2])
    else:
        s.appendleft(query[2])

if rev_flag:
    print(''.join(deque(reversed(s))))
else:
    print(''.join(s))
### BUGGY CODE ###

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

table = []

for i in range(n+1):
    table.append([0]*(i+1))

for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

for _ in range(q):
    start,end = map(int,input().split())
    res = 0
    for i in range(start,end+1):
        res += sum(table[i][start:])
    print(res)


### FIXED CODE ###

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

table = []
for i in range(n+1):
    table.append([0]*(n+1))
for i in range(m):
    a,b = map(int,input().split())
    table[b][a] += 1

#2...n
for i in range(2,n+1):

    #1...n-1
    for j in range(1,n+2-i):
        table[i+j-1][j] += table[i+j-1][j+1]+table[i+j-2][j]-table[i+j-2][j+1]

for _ in range(q):
    start,end = map(int,input().split())
    print(table[end][start])