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

"""
author : halo2halo
date : 29, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

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


def luner(n):
    if n == 0:
        return 2
    if n == 1:
        return 1

    return luner(n - 1) + luner(n - 2)


N = int(readline())
print(luner(N))

### FIXED CODE ###

"""
author : halo2halo
date : 29, Jan, 2020
"""

import sys

# import itertools
# import numpy as np

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

L=[2,1]
for _ in range(90):
    L.append(L[-1]+L[-2])
N = int(readline())
print(L[N])
### BUGGY CODE ###

import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True
cnt = 1
ans = 0

# プリム法 くっつけてく
heap = list(zip(np.minimum(abs(X - X[0]), abs(Y - Y[0])), range(N)))[1:]
heapq.heapify(heap)
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    ans += dist

    for du in zip(np.minimum(abs(X[~fixed] - X[v]), abs(Y[~fixed] - Y[v])), np.where(~fixed)[0]):
        heapq.heappush(heap, du)
    cnt += 1
print(ans)


### FIXED CODE ###

import bisect
import os
from collections import Counter, deque
from fractions import gcd
from functools import lru_cache
from functools import reduce
import functools
import heapq
import itertools
import math
import numpy as np
import re
import sys

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")

N = int(sys.stdin.readline())
X, Y = list(zip(*[map(int, sys.stdin.readline().split()) for _ in range(N)]))

X = np.array(X)
Y = np.array(Y)
Xargs = X.argsort()
Yargs = Y.argsort()

# X 座標上または Y 座標上で隣り合わないやつは隣り合うやつをたどっていけるので考えなくていい
graph = [[] for _ in range(N)]
for v, u in zip(Xargs[:-1], Xargs[1:]):
    graph[v].append((abs(X[v] - X[u]), u))
    graph[u].append((abs(X[v] - X[u]), v))
for v, u in zip(Yargs[:-1], Yargs[1:]):
    graph[v].append((abs(Y[v] - Y[u]), u))
    graph[u].append((abs(Y[v] - Y[u]), v))

heap = graph[0]
heapq.heapify(heap)
fixed = np.zeros(N, dtype=bool)
fixed[0] = True

cnt = 1
ans = 0
while cnt < N:
    dist, v = heapq.heappop(heap)
    if fixed[v]:
        continue
    fixed[v] = True
    cnt += 1
    ans += dist
    for d, u in graph[v]:
        if fixed[u]:
            continue
        heapq.heappush(heap, (d, u))

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

n = int(input())
p = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        dp[i][j] += dp[i-1][j-1]*p[i-1]
        dp[i][j] += dp[i-1][j]*(1-p[i-1])
print(sum(dp[-1][-(-n//2):]))


### FIXED CODE ###

n = int(input())
p = list(map(float, input().split()))
dp = [[0]*(n+1) for _ in range(n+1)]
dp[0][0] = 1
for i in range(1, n+1):
    for j in range(n+1):
        dp[i][j] += dp[i-1][j-1]*p[i-1]
        dp[i][j] += dp[i-1][j]*(1-p[i-1])
print(sum(dp[-1][-(-n//2):]))
### BUGGY CODE ###

from collections import deque


def main():
    from sys import stdin
    readline = stdin.readline

    INF = float('inf')

    H, W = map(int, readline().split())
    Ch, Cw = map(lambda x: int(x) - 1, readline().split())
    Dh, Dw = map(lambda x: int(x) - 1, readline().split())
    S = [readline()[:-1] for _ in range(H)]

    t = [[INF] * W for _ in range(H)]
    for h in range(H):
        th = t[h]
        Sh = S[h]
        for w in range(W):
            if Sh[w] == '#':
                th[w] = -1

    t[Ch][Cw] = 0
    q = deque([(Ch, Cw)])
    while q:
        warpq = []
        while q:
            h, w = q.popleft()
            a = t[h][w]
            warpq.append((h, w))
            if h - 1 >= 0 and t[h - 1][w] > a:
                q.append((h - 1, w))
                t[h - 1][w] = a
            if h + 1 < H and t[h + 1][w] > a:
                q.append((h + 1, w))
                t[h + 1][w] = a
            if w - 1 >= 0 and t[h][w - 1] > a:
                q.append((h, w - 1))
                t[h][w - 1] = a
            if w + 1 < W and t[h][w + 1] > a:
                q.append((h, w + 1))
                t[h][w + 1] = a

        if t[Dh][Dw] != INF:
            break

        for h, w in warpq:
            for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
                ti = t[i]
                for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
                    if ti[j] <= a + 1:
                        continue
                    ti[j] = a + 1
                    q.append((i, j))

    if t[Dh][Dw] == INF:
        print(-1)
    else:
        print(t[Dh][Dw])


main()


### FIXED CODE ###

from collections import deque

INF = float('inf')

H, W = map(int, input().split())
Ch, Cw = map(lambda x: int(x) - 1, input().split())
Dh, Dw = map(lambda x: int(x) - 1, input().split())
S = [input() for _ in range(H)]

t = [[INF] * W for _ in range(H)]
t[Ch][Cw] = 0
q = deque([(Ch, Cw)])

while q:
    h, w = q.popleft()
    a = t[h][w]
    if h - 1 >= 0 and S[h - 1][w] != '#' and t[h - 1][w] > a:
        q.appendleft((h - 1, w))
        t[h - 1][w] = a
    if h + 1 < H and S[h + 1][w] != '#' and t[h + 1][w] > a:
        q.appendleft((h + 1, w))
        t[h + 1][w] = a
    if w - 1 >= 0 and S[h][w - 1] != '#' and t[h][w - 1] > a:
        q.appendleft((h, w - 1))
        t[h][w - 1] = a
    if w + 1 < W and S[h][w + 1] != '#' and t[h][w + 1] > a:
        q.appendleft((h, w + 1))
        t[h][w + 1] = a

    for i in range(max(0, h - 2), min(H - 1, h + 2) + 1):
        for j in range(max(0, w - 2), min(W - 1, w + 2) + 1):
            if S[i][j] == '#':
                continue
            if t[i][j] <= a + 1:
                continue
            t[i][j] = a + 1
            q.append((i, j))

if t[Dh][Dw] == INF:
    print(-1)
else:
    print(t[Dh][Dw])
### BUGGY CODE ###

import sys
import collections
import copy
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
for j in range(N*(N-1)//2):
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
print(ans)

### FIXED CODE ###

import sys
import collections
import copy
def input(): return sys.stdin.readline().strip()
N = int(input())
sc = [[int(i) for i in input().split()] for i in range(N)]
count = [0] * N
done = [0] * N
fin = [N-1] * N
ans = 0
chk = 0
for j in range(N*(N-1)//2):
    if j >= 4000:
        chk = 1
        break
    done = [0] * N
    for i in range(N-1):
        if N-1 > count[i]:
            if done[sc[i][count[i]]-1] == 0 and done[i] == 0:
                if sc[sc[i][count[i]]-1][count[sc[i][count[i]]-1]] == i+1:
                    done[sc[i][count[i]]-1] = 1
                    done[i] = 1
                    count[sc[i][count[i]]-1] += 1
                    count[i] += 1
    if done == [0] * N:
        if count == fin:
            break
        else:
            ans = -1
            break
    ans += 1
if chk == 0:
    print(ans)
else:
    print(N*(N-1)//2)
### BUGGY CODE ###

A, B, K = map(int, input().split())

for i in range(K):
    if A >= 1:
        A -= 1
    elif B >= 1:
        B -= 1
    else:
        continue

print('{} {}' .format(A, B))

### FIXED CODE ###

A, B, K = map(int, input().split())

if A >= K:
    A -= K
elif A + B >= K:
    B -= K - A
    A = 0
else:
    A = 0
    B = 0

print('{} {}' .format(A, B))
### BUGGY CODE ###

import math
n = int(input())
count = [0]*n
for i in range(1,n+1):
    for x in range(1,int(n**0.5)+1):
        for y in range(1,int(n**0.5)+1):
            b = x + y
            c = x*x + y*y + x*y - i
            if b**2 >= 4*c:
                d = (-b + math.sqrt(b**2-4*c))/2 #zの解
                if d.is_integer() == True and d >= 1:
                    count[i-1] += 1
for i in range(n):
    print(count[i])

### FIXED CODE ###

import math
n = int(input())
count = [0]*(10**7)
for i in range(1,101):
    for j in range(1,101):
        for k in range(1,101):
            count[i*i + j*j + k*k + i*j + j*k + k*i -1] += 1
for i in range(n):
    print(count[i])
### BUGGY CODE ###

n,k=map(int,input().split())
s=list(input())
import sys
input=sys.stdin.readline
s.reverse()
if k>=n:
    print(min(s)*n)
else:
    for i in range(min(k,n)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))


### FIXED CODE ###

n,k=map(int,input().split())
s=list(input())
l=0
c=0
for i in range(n):
    if s[i]==min(s):
        c+=1
        l=max(l,c)
    else:
        c=0
import sys
input=sys.stdin.readline
s.reverse()
if (2**(k-1))*l>n:
    print(min(s)*n)
else:
    for i in range(min(k,13)):
        t=list(reversed(s))
        u=t+s
        uu=u[:n]
        for j in range(1,n+1):
            x=u[j:j+n]
            if uu>x:
                uu=x
        s=uu
    print("".join(s))
### BUGGY CODE ###

S=raw_input()
N=len(S)
mod=10**9+7

num=[ [ 0 for i in range(4) ] for j in range(N) ]		# i=0 A, i=1 B, i=2 C, i=3 ?

for i in range(N):
	if i==0:
		if S[i]=="A":  num[i][0]=1
		elif S[i]=="B":  num[i][1]=1		
		elif S[i]=="C":  num[i][2]=1
		elif S[i]=="?":  num[i][3]=1
	else:
		for j in range(4):
			num[i][j]=num[i-1][j]
			
		if S[i]=="A":  num[i][0]+=1
		elif S[i]=="B":  num[i][1]+=1		
		elif S[i]=="C":  num[i][2]+=1
		elif S[i]=="?":  num[i][3]+=1		

ans=0

for i in range(1,N):
	if S[i]=="B" or S[i]=="?":
		a=num[i-1][0]
		c=num[N-1][2]-num[i][2]
		ql=num[i-1][3]
		qr=num[N-1][3]-num[i][3]

		#ABC
		ans+=a*(3**ql)*c*(3**qr)

		#AB?
		if qr>0:
			ans+=a*qr*(3**ql)*(3**(qr-1) )

		#?BC
		if ql>0:
			ans+=(3**(ql-1) )*ql*c*(3**qr)

		#?B?
		if ql>0 and qr>0:
			ans+=ql*(3**(ql-1) )*qr*(3**(qr-1) )

print ans%mod



### FIXED CODE ###

S=raw_input()

M=10**9+7

all=1
abc=0
ab=0
a=0

for x in S:
	if x=="A":
		a+=all
	if x=="B":
		ab+=a
	if x=="C":
		abc+=ab

	if x=="?":
		abc=abc*3+ab
		ab=ab*3+a
		a= a*3+all
		all*=3

	abc%=M
	ab%=M
	a%=M
	all%=M


print abc%M
### BUGGY CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数
"""
import math
from fractions import gcd  # for Ver.3.4 or lower.
from functools import reduce
def GCD(*numbers):
    return reduce(gcd, numbers)
    #return reduce(math.gcd, numbers)

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    maxValue = 0
    for i in range(N) : 
        if i == 0 : sub_a_list = a_list[1:]
        elif i == N - 1 : sub_a_list = a_list[:N-1]
        else : sub_a_list = a_list[0 : i ] + a_list[i + 1 :] 
        rst = GCD(*sub_a_list)
        if maxValue < rst : maxValue = rst
    print(maxValue)
main()


### FIXED CODE ###

"""
問題文

N個の整数 A1,A2,...,ANが黒板に書かれています。
あなたはこの中から整数を 1つ選んで、1 以上 109以下の好きな整数に書き換えます。
元の整数と同じ整数に書き換えても構いません。書き換えた後のN個の整数の最大公約数の最大値を求めてください。

制約
入力は全て整数である。
2≤N≤105
1≤Ai≤109
"""

"""
3 5 7
最大公約数: 1
最大の最大公約数: 1

8 4 6
最大公約数: 2
最大の最大公約数: 4
『aとbとcの最大公約数』　＝　『aとbの最大公約数』と『c』　の最大公約数

A1 , A2 , A3 ... An

gcd(A1 , A2 , A3 ... An-1) * N
= gcd * N * N
= gcd * N^2

gcd(A1 , A2 , A3 ... An-1)
gcd(A1 , A2 , A3 ... An-2 , An) = gcd(A1 , A2 , A3 ... An-2) , An
"""
def gcd(a, b):  # a>b
    a, b = max(a, b), min(a, b)
    if b == 0:
        return a
    else:
        return gcd(b, a % b)

from functools import reduce
def GCD(numbers):
    if len(numbers) == 0 : return 0
    if len(numbers) == 1 : return numbers[0]
    if len(numbers) == 2 : 
        return gcd(numbers[0] , numbers[1])
    else : 
        value = GCD(numbers[:len(numbers)-1])
        result = gcd(value , numbers[len(numbers) - 1])
        return result

def main() : 
    N = int(input())
    a_list = input().split(" ")
    a_list = [int(i) for i in a_list]
    R = [0 for i in range(N - 1)]
    L = [0 for i in range(N - 1)]
    R[0] = a_list[0]
    L[0] = a_list[-1]

    for i in range(1 , N-1) : 
        R[i] = gcd(R[i - 1] , a_list[i])
    
    for j in range(1 , N-1) : 
        L[j] = gcd(L[j - 1] , a_list[- j - 1])
    
    maxValue = 0
    for i in range(N - 2) : 
        value = gcd(R[i] , L[N - i - 3])
        if value > maxValue : maxValue = value
    print(max(maxValue , R[-1] , L[-1]))
main()
### BUGGY CODE ###

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

#TLEの対策.配列ではなく変数を使う.
p,q=0,1

for i in range(1,n+1):
    #最新のp,q以前の値は捨てて良い.つまり配列を使用する必要なし.
    p,q=q,(p+q)%(10**9+7)*(not i in a) #n*Trueは1, n*Falseは0を表す.
print(q)

### FIXED CODE ###

n,m=map(int,input().split())
#TLEの対策1. a in listと比べて a in setはめちゃんこ速い!!
a=set([int(input()) for _ in range(m)])

#TLEの対策2.配列ではなく変数を使う(対策1と比べると対して効果なし).
p,q=0,1

for i in range(1,n+1):
    #最新のp,q以前の値は捨てて良い.つまり配列を使用する必要なし.
    p,q=q,(p+q)%(10**9+7)*(not i in a) #n*Trueは1, n*Falseは0を表す.
print(q)
### BUGGY CODE ###

N = int(input())
a = list(map(int, input().split()))
ans = 0

for k in range(min(a), max(a) + 1):
	ans = max(ans, a.count(k) + a.count(k + 1) + a.count(k - 1))
print(ans)


### FIXED CODE ###

from bisect import bisect_left, bisect_right

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

ans = 1
for i in range(N):
    X = a[i]
    res = bisect_right(a, X+1) - bisect_left(a, X-1)
    ans = max(res, ans)

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

n = int(input())
l = list(input())

if "R" not in l or "W" not in l:
    print(0)
    exit()

cnt = 0
for i in range(n):
    if l[i] == "W":
        if "R" not in l[i:]:
            break
        else:
            l1 = list(reversed(l))
            k = n-1 - l1.index("R")
            l[i], l[k] = l[k], l[i]
            cnt += 1
print(cnt)

### FIXED CODE ###

n = int(input())
l = list(input())

if "R" not in l or "W" not in l:
    print(0)
    exit()

cnt = 0

i = 0
k = n-1

while i < k:
    if l[i] == "W" and l[k] == "R":
        l[i], l[k] = l[k], l[i]
        cnt += 1
    if l[i] == "R":
        i += 1
    if l[k] == "W":
        k -= 1
print(cnt)
### BUGGY CODE ###

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

max = 1000
for i in range(2**(N-1)):
    possess = 1000
    for j in range(N-1):
        if (i >> j) & 1:
            stock = possess // A[j]
            possess = possess % A[j] + A[j+1] * stock
    if possess > max:
        max = possess

print(max)

### FIXED CODE ###

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

possess = 1000

for i in range(N-1):
    if A[i] < A[i+1]:
        stock = possess//A[i]
        possess = possess % A[i] + A[i+1] * stock


print(possess)
### BUGGY CODE ###


h, w, m = map(int, input().split())

h_b_list = [0 for i in range(h)]
w_b_list = [0 for i in range(w)]

targets = []
for i in range(m):
  bh, bw = map(int, input().split())
  targets.append([bh, bw])
  h_b_list[bh-1] += 1
  w_b_list[bw-1] += 1
  
h_max = max(h_b_list)
w_max = max(w_b_list)

h_cans = []
w_cans = []
for i in range(h):
  if h_b_list[i] == h_max:
    h_cans.append(i)
    
for i in range(w):
  if w_b_list[i] == w_max:
    w_cans.append(i)

for hi in h_cans:
  for wi in w_cans:
    if [hi+1, wi+1] not in targets:
      print(h_max+w_max)
      exit()
else:
  print(h_max+w_max-1)



### FIXED CODE ###


h, w, m = map(int, input().split())

h_b_list = [0 for i in range(h)]
w_b_list = [0 for i in range(w)]

targets = set()
for i in range(m):
  bh, bw = map(int, input().split())
  targets.add((bh, bw))
  h_b_list[bh-1] += 1
  w_b_list[bw-1] += 1
  
h_max = max(h_b_list)
w_max = max(w_b_list)

h_cans = []
w_cans = []
for i in range(h):
  if h_b_list[i] == h_max:
    h_cans.append(i)
    
for i in range(w):
  if w_b_list[i] == w_max:
    w_cans.append(i)

for hi in h_cans:
  for wi in w_cans:
    if (hi+1, wi+1) not in targets:
      print(h_max+w_max)
      exit()
else:
  print(h_max+w_max-1)
### BUGGY CODE ###

N, M = map(int, input().split())
A = list(map(int, input().split()))
#print([bin(val) for val in A])

A.sort()
#print(A)

def binsearch(threshold, lst):
    left, right = -1, len(lst)
    while right - left > 1:
        mid = (right + left) // 2
        if lst[mid] >= threshold:
            right = mid
        else:
            left = mid
    return right

if N > 1:
    cnt = 0
    while cnt < M:
        while A[-1] >= A[-2] and cnt < M:
            A[-1] //= 2
            cnt += 1
        indx = binsearch(A[-1], A)
        A.insert(indx, A.pop(-1))
        #print(cnt, A)
    print(sum(A))
else:
    print(A[0] // 2**M)



### FIXED CODE ###

import heapq

N, M = map(int, input().split())
A = list(map(lambda x:-int(x), input().split()))
#print([bin(val) for val in A])

heapq.heapify(A)
#print(A)

for _ in range(M):
    temp = -heapq.heappop(A) // 2
    heapq.heappush(A, -temp)
    #print(A)
print(-sum(A))
### BUGGY CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

def val(s):
    global n
    for i in range(n):
        for j in range(n):
            if s[i][j] != s[j][i]:
                return False
    return True

res = 0
for a in range(n):
    for b in range(n):
        ns = plusa(s,a)
        ns = plusb(ns,b)
        if val(ns):
            res += 1

print(res)

### FIXED CODE ###

n = int(input())
s = []
for _ in range(n):
    s.append(input())
st=list(map(''.join,zip(*s)))

def plusa(s,a):
    ns = []
    for ss in s:
        ns.append(ss[a:]+ss[:a])
    return ns

def plusb(s,b):
    global n
    ns = []
    for i in range(n-b):
        ns.append(s[b+i])
    for i in range(b):
        ns.append(s[i])
    return ns

res = 0
for i in range(n):
    if plusa(st,i) == plusb(s,i):
        res += n

print(res)
### BUGGY CODE ###

X = int(input())
a = []
b = 0
flag = True
for i in range(1,int(X**(1/5))+1):
  if(X%i== 0):
    a.append(i)
while(flag):
  for i in range(len(a)): 
    if(pow(b+a[i],5)-pow(b,5) == X):
      print("%d %d"%(b+a[i],b))
      flag = False
      break
  b -= 1
  if(-pow(b,5) > X):
    b = int(X**(1/5))

### FIXED CODE ###

X = int(input())
a = []
b = 0
flag = True
num = 120
if(X <= 120):
  num = X
for i in range(1,num+1):
  if(X%i== 0):
    a.append(i)
while(flag):
  for i in range(len(a)): 
    if(pow(b+a[i],5)-pow(b,5) == X):
      print("%d %d"%(b+a[i],b))
      flag = False
      break
  b -= 1
  if(b < -119):
    b = 119
### BUGGY CODE ###

s = list(input())
count = 0
abc = 0
while True:
  for i in range(len(s)):
    #print(i, abc)
    if s[i] == 'A':
      abc = 1
    elif s[i] == 'B':
      if abc == 1:
        abc = 2
      else:
        abc = 0
    elif s[i] == 'C':
      if abc == 2:
        abc = 0
        count += 1
        s[i-2:i+1] = ['B', 'C', 'A']
        #print(s)
        #print(2)
        break        
  else:
    #print(1)
    break
    
print(count)

### FIXED CODE ###

s = list(input())
count = 0
abc = 0

a_series = 0

for i in range(len(s)):
  #print(i, abc)
  if s[i] == 'A':
    if abc != 1:
      a_series = 0
    a_series += 1
    abc = 1
  elif s[i] == 'B':
    if abc == 1:
      abc = 2
    else:
      abc = 0
      a_series = 0
  elif s[i] == 'C':
    if abc == 2:
      abc = 1
      count += a_series
    else:
      abc = 0
      a_series = 0
      
print(count)
### BUGGY CODE ###

def main():
  s=input()
  q=int(input())
  rev=0
  for _ in range(q):
    query=input().split()
    if(query[0]=='1'):
      rev=1-rev
    elif((int(query[1])+rev)%2==1):
      s=query[2]+s
    else:
      s=s+query[2]
  if rev==1:
    return s[::-1]
  return s
print(main())

### FIXED CODE ###

import array
def main():
  n=2*10**5
  s=input()
  q=int(input())
  rev=0
  l=n-1
  r=n+len(s)
  s=array.array('b',[0]*n+[ord(c) for c in s]+[0]*n)
  for _ in range(q):
    query=input().split()
    if(query[0]=='1'):
      rev=1-rev
    elif((int(query[1])+rev)%2==1):
      s[l]=ord(query[2])
      l-=1
    else:
      s[r]=ord(query[2])
      r+=1
  s=[chr(c) for c in s if c!=0]
  if rev==1:
    return ''.join(s[::-1])
  return ''.join(s)
print(main())
### BUGGY CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n

    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]

    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)

        if x == y:
            return

        if self.parents[x] > self.parents[y]:
            x, y = y, x

        self.parents[x] += self.parents[y]
        self.parents[y] = x

    def size(self, x):
        return -self.parents[self.find(x)]

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]

    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]

    def group_count(self):
        return len(self.roots())

    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}

    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())

nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]

uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)

uf_list = list(uf.all_group_members().values())

ans = 0

for i in range(len(uf_list)):
    l = len(uf_list[i])
    if ans < l:
        ans = l
print(ans)


### FIXED CODE ###

class UnionFind():
    def __init__(self, n):
        self.n = n
        self.parents = [-1] * n
 
    def find(self, x):
        if self.parents[x] < 0:
            return x
        else:
            self.parents[x] = self.find(self.parents[x])
            return self.parents[x]
 
    def union(self, x, y):
        x = self.find(x)
        y = self.find(y)
 
        if x == y:
            return
 
        if self.parents[x] > self.parents[y]:
            x, y = y, x
 
        self.parents[x] += self.parents[y]
        self.parents[y] = x
 
    def size(self, x):
        return -self.parents[self.find(x)]
 
    def same(self, x, y):
        return self.find(x) == self.find(y)
 
    def members(self, x):
        root = self.find(x)
        return [i for i in range(self.n) if self.find(i) == root]
 
    def roots(self):
        return [i for i, x in enumerate(self.parents) if x < 0]
 
    def group_count(self):
        return len(self.roots())
 
    def all_group_members(self):
        return {r: self.members(r) for r in self.roots()}
 
    def __str__(self):
        return '\n'.join('{}: {}'.format(r, self.members(r)) for r in self.roots())
 
nm = list(map(int, input().split()))
n = nm[0]
m = nm[1]
 
ans = 1
 
uf = UnionFind(n)
for i in range(m):
    friends = list(map(int, input().split()))
    uf.union(friends[0]-1,friends[1]-1)
    if ans < uf.size(friends[1]-1):
        ans = uf.size(friends[1]-1)
print(ans)