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

s = input()
t = input()

#dp[i+1][j+1]:Sのi文字目までとTのj文字目まででのLCSの長さ

dp = [["" for j in range(len(t)+1)] for i in range(len(s)+1)]

for i in range(len(s)):
    for j in range(len(t)):
        if s[i] == t[j]:
            dp[i+1][j+1] = max(dp[i][j]+s[i], dp[i+1][j], dp[i][j+1], key=len)
        else:
            dp[i+1][j+1] = max(dp[i+1][j], dp[i][j+1], key=len)

print(dp[len(s)][len(t)])

### FIXED CODE ###

s = input()
t = input()

#dp[i+1][j+1]:Sのi文字目までとTのj文字目まででのLCSの長さ

dp = [[0 for j in range(len(t)+1)] for i in range(len(s)+1)]

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


#復元
res = ""
i = len(s)
j = len(t)

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:
        res = s[i-1] + res
        i -= 1
        j -= 1

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

from copy import deepcopy

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

a = list(map(int, input().split()))
a_ = deepcopy(a)
ans = 1000000
for index in range(len(a)):
    temp = max(a) - min(a)
    a[index] = a[index] + k
    if ans > temp:
        ans = temp

for index in reversed(range(len(a))):
    # print(a_, temp, max(a_), min(a_))
    temp = (max(a_) - min(a_))
    # print(temp)
    a_[index] -= k
    if ans > temp:
        ans = temp

print(ans)


### FIXED CODE ###

from copy import deepcopy

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

a = list(map(int, input().split()))
a = sorted(a)
max_ = max(a)
min_ = min(a)
a_ = deepcopy(a)
ans = 100000000000
for index in range(len(a)):
    # temp = max(a) - min(a)
    # print(max_,min_)
    temp = max_ - min_
    max_ = min_ + k
    if index != len(a)-1:
        min_ = a[index+1]
    a[index] = a[index] + k
    # print(temp)
    if ans > temp:
        ans = temp

max_ = max(a_)
min_ = min(a_)

for index in reversed(range(len(a))):
    # print(a_, temp, max(a_), min(a_))
    # temp = (max(a_) - min(a_))
    # print(max_,min_)
    temp = max_-min_
    min_ = max_ -k
    if index != 0:
        max_ = a_[index-1]
    # print(temp)
    # a_[index] -= k
    if ans > temp:
        ans = temp

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

# -*- coding: utf-8 -*-
N = int(input())
array = [int(input()) for i in range(N)]

for i in range(N):
  backup = array.pop(i)
  print(max(array))
  array.insert(i, backup)


### FIXED CODE ###

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

N = int(input())
array = [int(input()) for i in range(N)]

array_sorted = sorted(array, reverse=True)
max_index = array.index(array_sorted[0])
max_value = array_sorted[0]
second_value = array_sorted[1]

for i in range(N):
  if array[i] == max_value:
    print(second_value)
  else:
    print(max_value)
### BUGGY CODE ###

h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1

hq=[(0,nx-1,ny-1)]
while hq:
    c,x,y=heappop(hq)
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!="#":
        heappush(hq,(c,x-1,y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!="#":
        heappush(hq,(c,x,y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!="#":
        heappush(hq,(c,x+1,y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!="#":
        heappush(hq,(c,x,y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]=="."and w*i + j not in seen:
                heappush(hq,(c+1,i,j))

print(-1)

### FIXED CODE ###

import sys
input=sys.stdin.buffer.readline
inputs=sys.stdin.buffer.readlines
sys.setrecursionlimit(10**9)
h,w=map(int,input().split())
nx,ny=map(int,input().split())
gx,gy=map(int,input().split())
maze=[input()for i in range(h)]
from heapq import heapify, heappop, heappush
seen=set()
gx-=1;gy-=1
SIZE=h*w
hq=[(nx-1)*w+ny-1]
while hq:
    d=heappop(hq)
    c,d=divmod(d,SIZE)
    x,y=divmod(d,w)
    if w*x +y in seen:continue
    seen.add(w*x +y)
    if x==gx and y==gy:print(c);exit()
    if x and w*(x-1)+y not in seen and maze[x-1 ][y]!=35:
        heappush(hq,(c*SIZE+w*(x-1)+y))
    if y and w*x+y-1 not in seen and maze[x][y-1]!=35:
        heappush(hq,(c*SIZE+w*x+y-1))
    if x+1<h  and w*(x+1)+y not in seen and maze[x+1][y]!=35:
        heappush(hq,(c*SIZE+w*(x+1)+y))
    if y+1<w  and w*x+y+1 not in seen and maze[x][y+1]!=35:
        heappush(hq,(c*SIZE+w*x+y+1))
    for i in range(max(0,x-2),min(h,x+3)):
        for j in range(max(0,y-2),min(w,y+3)):
            if i==x and j==y:continue
            if maze[i][j]==46 and w*i + j not in seen:
                heappush(hq,(c+1)*SIZE+w*i+j)

print(-1)
### BUGGY CODE ###

from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    cnter = defaultdict(int)

    for start in range(N-1):
        deq = deque()
        deq.append(start)
        n_step = [float('inf')] * N
        n_step[start] = 0
        visited = [False] * N

        while len(deq) > 0:
            fr = deq.popleft()
            visited[fr] = True

            if fr == X-1:
                if not visited[Y-1] or n_step[Y-1] > n_step[X-1]+1:
                    n_step[Y-1] = n_step[X-1]+1
                    deq.append(Y-1)
                    visited[Y-1] = True

            if fr == Y-1:
                if not visited[X-1] or n_step[X-1] > n_step[Y-1]+1:
                    n_step[X-1] = n_step[Y-1]+1
                    deq.append(X-1)
                    visited[X-1] = True
                    
            if fr != N-1:
                if not visited[fr+1] or n_step[fr+1] > n_step[fr]+1:
                    deq.append(fr+1)
                    n_step[fr+1] = n_step[fr]+1
                    visited[fr+1] = True

            if fr != 0:
                if not visited[fr-1] or n_step[fr-1] > n_step[fr]+1:
                    deq.append(fr-1)
                    n_step[fr-1] = n_step[fr]+1
                    visited[fr-1] = True
        
        for i in range(start,N):
            if n_step[i] == float('inf'):
                continue
            cnter[n_step[i]] += 1
            
    for i in range(1,N):
        print(cnter[i])

if __name__ == '__main__':
    solve()

### FIXED CODE ###

from collections import defaultdict, deque
def solve():
    N, X, Y = map(int, input().split())
    X -= 1
    Y -= 1
    cnter = defaultdict(int)

    for i in range(N):
        for j in range(i,N):
            n_step = min(abs(j-i), abs(X-i)+1+abs(Y-j), abs(Y-i)+1+abs(j-X))
            cnter[n_step] += 1
    
    for i in range(1,N):
        print(cnter[i])


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

a,b = (int(i) for i in input().split())
ans = 0
for i in range(a,b+1):
  ans ^= i
print(ans)

### FIXED CODE ###

a,b = (int(i) for i in input().split())
ans = 0
if a % 2 == 0:
  temp = (b - a + 1) % 4 
  for i in range(b-temp+1,b+1):
    ans ^= i
else:
  temp = (b - a) % 4 
  ans ^= a
  for i in range(b-temp+1,b+1):
    ans ^= i
print(ans)
### BUGGY CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

ans_dict = {}
ans_keys = []
value_dict = {1: 0}
value_keys = [1]
for i in range(n):
    if i in ans_keys:
        print(ans_dict[i])
    else:
        buff = a_list[:i]
        buff.extend(a_list[i+1:])
        c = Counter(buff)

        tmp_ans = 0
        for value in c.values():
            if value in value_keys:
                tmp_ans += value_dict[value]
            else:
                tmp = (value * (value - 1))/2
                tmp_ans += tmp
                value_dict[value] = tmp
                value_keys.append(value)
        ans_dict[i] = tmp_ans
        ans_keys.append(i)
        print(int(tmp_ans))




### FIXED CODE ###

from collections import Counter

n = int(input())

a_list = list(map(int, input().split()))

c = Counter(a_list)

all_count = 0
for value in c.values():
    if value == 1:
        continue
    else:
        tmp = int((value * (value - 1))/2)
        all_count += tmp

for i in a_list:
    print(all_count - c[i] + 1)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

INF = 10 ** 8 + 1
n, m = map(int, input().split())
key = []
for i in range(m):
    a, b = map(int, input().split())
    c = list(map(int, input().split()))
    bt = 0
    for e in c:
        bt |= 1 << (e - 1)
    key.append((bt, a))

dp = [INF for _ in range(1 << n)]
dp[0] = 0

for i in range(1 << n):
    for j in range(m):
        state = i | key[j][0]
        cost = dp[i] + key[j][1]
        dp[state] = min(dp[state], cost)

if dp[-1] == INF:
    ans = -1
else:
    ans = dp[-1]

print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline


def main():

    INF = 10 ** 7
    n, m = map(int, input().split())
    state_num = 1 << n
    key = []
    for i in range(m):
        a, b = map(int, input().split())
        c = list(map(int, input().split()))
        bt = 0
        for e in c:
            bt |= 1 << (e - 1)
        key.append((bt, a))

    dp = [INF for _ in range(state_num)]
    dp[0] = 0

    for i in range(state_num):
        for j in range(m):
            ks, kc = key[j]
            state = i | ks
            cost = dp[i] + kc
            dp[state] = min(dp[state], cost)

    ans = dp[-1]
    if ans == INF:
        ans = -1
    print(ans)


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

from collections import Counter
teisuu1=10**6
N=int(input())
A=list(map(int,input().split()))
count_A=Counter(A)
dp=[True]*(teisuu1+1)
s=list(set(A))
for i in s:
  temp=i*2
  while temp<=max(s):
    dp[temp]=False
    temp+=i
ans=0
for i in A:
  if count_A[i]==1 and dp[i]==True:
    ans+=1
print(ans)


### FIXED CODE ###

N=int(input())
A=list(map(int,input().split()))
dp=[0]*(10**6+1)
ans=0
for i in A:
  if dp[i]==0:
    for j in range(i,10**6+1,i):
      dp[j]+=1
  else:
    dp[i]+=1
for i in A:
  if dp[i]==1:
    ans+=1
print(ans)
### BUGGY CODE ###

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

if n == 0:
  print(0)
elif n % k==0:
  print(0)
else:
  while n > abs(n - k):
    n = abs(n - k)
  print(n)
    


### FIXED CODE ###

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

if n == 0:
  print(0)
elif n % k==0:
  print(0)
elif n >k:
  while n > abs(n - k):
    n = min(abs(n - k),n % k)
  print(n)
else:
  while n > abs(n - k):
    n = abs(n - k)
  print(n)
### BUGGY CODE ###

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

ans = 0
for i in range(N-1):
  for j in range(i+1,N):
    l = 0
    while(i+l < j and j+l < N and S[i+l] == S[j+l]):
      l += 1
    ans = max(l,ans)
print(ans)

### FIXED CODE ###

def z_algo(S):
  N = len(S)
  A = [0]*N
  i = 1; j = 0
  A[0] = l = len(S)
  while i < l:
    while i+j < l and S[j] == S[i+j]:
      j += 1
    if not j:
      i += 1
      continue
    A[i] = j
    k = 1
    while l-i > k < j - A[k]:
      A[i+k] = A[k]
      k += 1
    i += k; j -= k
  return A

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

ans = 0
for i in range(N):
  SS = S[i:]
  Z = z_algo(SS)
  #print(Z)
  for j in range(1,len(SS)):
    if Z[j] > j:
      l = j
    else:
      l = Z[j]
    ans = max(l,ans)
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
jobs = []
taken = [0] * (M+1)
jappend = jobs.append
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jappend((B*(-1),A))
heapq.heapify(jobs)
for i in range(len(jobs)):
    temp = heapq.heappop(jobs)
    if taken[(M-temp[1]+1)//2:M-temp[1]+1].count(0) > 0:
        searching = M - temp[1]
    else:
        if temp[1] == M:
            searching = 0
        elif taken[0:(M-temp[1]+1)//2].count(0) > 0:
            searching = ((M-temp[1]+1)//2) - 1
        else:
            continue
    for i in range(searching+1):
        if taken[searching-i] == 0:
            taken[searching-i] = temp[0]
            break
print(sum(taken)*(-1))

### FIXED CODE ###

import sys
input = sys.stdin.readline

import heapq
N,M = (int(x) for x in input().split())
jobs = [[] for i in range(M)]
count = 0
h = []
for i in range(N):
    A,B = (int(x) for x in input().split())
    if A <= M:
        jobs[A-1].append(B*(-1))
heapq.heapify(h)
for i in range(M):
    if jobs[i]:
        for job in jobs[i]:
            heapq.heappush(h,job)
    if h:
        count -= heapq.heappop(h)
print(count)
### BUGGY CODE ###

N, W = map(int, input().split())
dp = [0] * (W + 1)

for i in range(N):
    w, v = map(int, input().split())
    for j in range(W, w-1, -1):
        tmp = dp[j-w] + v
        if tmp > dp[j]:
            dp[j] = tmp
print(dp[-1])

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, W = map(int, input().split())
dp = [0] * (W + 1)
def dp_opt(n, w):
    for _ in range(N):
        w, v = map(int, input().split())
        for j in range(W, w-1, -1):
            tmp = dp[j-w] + v
            if tmp > dp[j]:
                dp[j] = tmp
    print(dp[-1])
dp_opt(N,W)
### BUGGY CODE ###

def main():
    length = int(input())
    numbers = list(map(int, input().split()))
    numbers.sort()
    max_digit = len(bin(numbers[-1])[2:])
    count = [[0, 0] for _ in range(60)]
    for n in numbers:
        bin_n = bin(n)[2:].zfill(max_digit)
        for i in range(max_digit):
            count[max_digit - i - 1][int(bin_n[i])] += 1
    answer = 0
    mod = 10 ** 9 + 7
    for i, c in enumerate(count):
        answer = (answer + c[0] * c[1] * pow(2, i)) % mod
    print(answer)


if __name__ == '__main__':
    main()



### FIXED CODE ###

import numpy as np


def main():
    length = int(input())
    numbers = np.array(list(map(int, input().split())))
    mod = 10 ** 9 + 7
    answer = 0
    for d in range(60):
        count_one = np.count_nonzero((numbers >> d) & 1)
        answer = (answer + pow(2, d) * count_one * (length - count_one)) % mod
    print(answer)


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

def main():
    x,y = map(int,input().split())
    tmp = [1]
    i = 2
    ans = 0
    # if x == y:
    #     ans += 1
    while x >= i:
        if x % i == 0:
            tmp.append(i)
            while x % i == 0:

                x //= i
        i += 1
    for i,a in enumerate(tmp):
        if y % a == 0:
            tmp[i] = 1
        else:
            tmp[i] = 0
    print(sum(tmp))


if __name__=='__main__':
    main()


### FIXED CODE ###

def main():
    x,y = map(int,input().split())
    tmp = [1]
    i = 2
    ans = 0
    # if x == y:
    #     ans += 1
    # a = factorization(x)
    # print(a)
    tempx = x

    for i in range(2, int(-(-x**0.5//1))+1):
        if tempx % i == 0:
            tmp.append(i)
            while tempx % i == 0:

                tempx //= i
    if tempx!=1:
        tmp.append(tempx)
    # print(tmp)

    for i,a in enumerate(tmp):
        if y % a == 0:
            tmp[i] = 1
        else:
            tmp[i] = 0
    print(sum(tmp))


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

N = int(input())
A = list(map(int,input().split()))
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  Flag = True
  temp = A[j]
  i = 2
  if Adic[temp] >= 2:
    continue
  while i*i <= temp:
    #print(i,temp)
    if temp%i == 0:
      #print(i,temp//i,temp)
      if i in Aset or temp//i in Aset:
        Flag = False
        #print(i,temp//i,"X")
        break
    i += 1
  if not Flag:
    continue
  ans += 1
print(ans)

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
MAX = max(A) #Aの中の最大値
Adic={}
for i in range(N):
  if A[i] not in Adic:
    Adic[A[i]] = 1
  else:
    Adic[A[i]] += 1
Aset = set(A)
if 1 in Aset: #1がある場合
  if Adic[1] == 1:
    print(1)
  else:
    print(0)
  exit()
ans = 0
for j in range(N):
  temp = A[j]
  if Adic[temp] >= 2: #同じ数が複数ある場合には削除
    if temp in Aset:
      Aset.remove(temp)
  fmax = MAX//temp
  #print(fmax,temp)
  for i in range(2,fmax+10): #fmaxまで見る
    now = temp*i
    if now in Aset:
      Aset.remove(now)
#print(Aset)
print(len(Aset))
### BUGGY CODE ###


N = int(input())

s_li = []
c = 0
for i in range(N) :
    s = ''.join(sorted(list(input())))
    con = s_li.count(s)
    if (con >= 1) :
        c += con
    s_li.append(s)

print(c)

### FIXED CODE ###

import statistics as stat
import collections as cl

N = int(input())

s_li = []
s_dic = {}
c = 0
for i in range(N) :
    s = ''.join(sorted(list(input())))
    # con = s_li.count(s)
    # if (con >= 1) :
    #     c += con
    # s_li.append(s)
    if (s in s_dic) :
        c += s_dic[s]
        s_dic[s] += 1
    else :
        s_dic[s] = 1

print(c)
### BUGGY CODE ###

N = int(input())
n = [i + 1 for i in range(N)]
p = [i + 1 for i in range(N)]
p.append(1)
del(p[0])
ans = 0
for i in range(N):
    ans = ans + (n[i] % p[i])
print(ans)

### FIXED CODE ###

N = int(input())
print((N + 1) * N // 2 - N)
### BUGGY CODE ###

S = input()
Q = int(input())
L = [list(input().split()) for i in range(Q)]

ans = S
hanten = 0
for l in L:
    if len(l) == 1:
        hanten += 1
    elif (l[1] == '1' and hanten % 2 == 0) or (l[1] == '2' and hanten % 2 == 1):
        t = [l[2], ans]
        ans = ''.join(t)
    else:
        t = [ans, l[2]]
        ans = ''.join(t) 
if hanten % 2 == 1:
    ans = ''.join(list(reversed(ans)))
print(ans)

### FIXED CODE ###

from collections import deque

S = input()
Q = int(input())
L = [list(input().split()) for i in range(Q)]

hanten = 0
t = deque([S])

for l in L:
    if len(l) == 1:
        hanten += 1
    elif (l[1] == '1' and hanten % 2 == 0) or (l[1] == '2' and hanten % 2 == 1):
        t.appendleft(l[2])
    else:
        t.append(l[2])

ans = ''.join(t)
if hanten % 2 == 1:
    ans = ''.join(list(reversed(ans)))
print(ans)
### BUGGY CODE ###

n = int(input())
*a, = map(int,input().split())
box = [0]*n
cnt=0
ans=[]
for i in range(n,0,-1):
    sum = 0
    for j in range(i,n+1,i):
        sum+=box[j-1]
    if sum%2!=a[i-1]:
        ans.insert(0,i)
        cnt+=1
        box[i-1]+=1

if cnt!=0:
    print(cnt)
    print(*ans)
else:
    print(0)

### FIXED CODE ###

n = int(input())
*a, = map(int,input().split())
box = [0]*n
for i in range(n,0,-1):
    sum_box = 0
    for j in range(i,n+1,i):
        sum_box+=box[j-1]
    if sum_box%2!=a[i-1]:
        box[i-1]+=1

print(sum(box))
if sum(box):
    ans = []
    for i, x in enumerate(box):
        if x:
            ans.append(i+1)
    print(*ans)
### BUGGY CODE ###

n,q=map(int,input().split())
s=input()
listA=[] 
while True:
    try:
        listA.append(list(map(int,input().split())))

    except:
        break;
        
l = list(s)
li=[0]*n

for i in range(n-1):
  if l[i]=="A" and l[i+1]=="C":
    li[i]+=1
    
#print(li)   
 
    
ans=0
for j in range(q):
  a=listA[j][0]-1
  b=listA[j][1]-1
  #print(a,b)
  for k in range(a,b):
    if li[k]==1:
      ans+=1
  print(ans)
  ans=0



### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
t=[0]*(N+1)
for i in range(N):
  t[i + 1] = t[i] + (1 if S[i : i + 2] == 'AC' else 0)
for i in range(Q):
  l, r = map(int, input().split())
  print(t[r-1] - t[l-1])
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
Q = int(input())
B = [0]*Q
C = [0]*Q
for i in range(Q):
    B[i], C[i] = map(int,input().split())
for i in range(Q):
    if B[i] not in A:
        print(sum(A))
        continue
    for j in range(N):
        if A[j] == B[i]:
            A[j] = C[i]
    print(sum(A))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N = int(input())
A = list(map(int,input().split()))
Q = int(input())
cnt = [0]*100005
s = sum(A)
for i in A:
    cnt[i] += 1
for i in range(Q):
    B, C = map(int,input().split())
    s += (C-B)*cnt[B]
    print(s)
    cnt[C] += cnt[B]
    cnt[B] = 0
### BUGGY CODE ###

N = int(input())
ret = 0
for i in range(1, N):
    ret += i
# 1 2 3 4 5 6 7 8 9 10 11 12 13
# 2 3 4 5 6 7 8 9 10 11 12 13 1
print(ret)


### FIXED CODE ###

N = int(input())
ret = (1 + N) * N // 2 - N 
# 1 2 3 4 5 6 7 8 9 10 11 12 13
# 2 3 4 5 6 7 8 9 10 11 12 13 1
print(ret)
### BUGGY CODE ###

n,m=map(int,input().split())
a=[]
for i in range(m):
  a.append(int(input()))
dp=[1]
if 1 in a:
  dp.append(0)
else:
  dp.append(1)
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append(dp[-1]+dp[-2])
print(dp[-1]%1000000007)

### FIXED CODE ###

n,m=map(int,input().split())
a=set([int(input()) for i in range(m)])
mod=1000000007
dp=[1,1]
if 1 in a:
  dp[1]=0
for i in range(2,n+1):
  if i in a:
    dp.append(0)
  else:
    dp.append((dp[-1]+dp[-2])%mod)
print(dp[-1]%mod)
### BUGGY CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]

for i in range(m):
	a,b=map(int,input().split(" "))
	l.append(a)
	l.append(b)
	if b==n:
		bone.append(a) #nと定期便がある島を記録	
def cat_snuke():
	count = 0
	for i in l:
		if i==1:
			for j in bone:
				if l[count+1] == j:
					print("POSSIBLE")
					return 0
		count=count+1
	print("IMPOSSIBLE")
		
cat_snuke()

### FIXED CODE ###

n,m=map(int,input().split(" "))
l=[]
bone=[]
for i in range(m):
		a,b=input().split(" ")
		if a=="1":l.append(b)
		if b==str(n):bone.append(a)

ans=list(set(l) & set(bone))
if len(ans)!=0:
	print("POSSIBLE")
else:			
	print("IMPOSSIBLE")
### BUGGY CODE ###

n, m = map(int, input().split())
a = [int(input()) for _ in range(m)]
m = 10**9+7

dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in a:
  dp[1] = 0

for i in range(2, n+1):
  dp[i] = 0 if i in a else (dp[i-2] + dp[i-1]) % m

print(dp[-1])


### FIXED CODE ###

n, m = map(int, input().split())
a = set(int(input()) for _ in range(m))
m = 10**9+7

dp = [0 for _ in range(n+1)]
dp[0] = 1
dp[1] = 1
if 1 in a:
  dp[1] = 0

for i in range(2, n+1):
  dp[i] = 0 if i in a else (dp[i-2] + dp[i-1]) % m

print(dp[-1])
### BUGGY CODE ###

def get_subgraph(node):
  subgraph = [node]
  for i, j in edges:
    if node == i:
      subgraph.extend(get_subgraph(j))
  return subgraph

n, q = map(int, input().split())
edges = []
for i in range(n-1):
  e, f = map(int, input().split())
  edges.append((e, f))

tasks = []
for i in range(q):
  p, x = map(int, input().split())
  tasks.append((p, x))

counter = list(map(int, list('0'*n)))

subgraphs = []
for i in range(1, n+1):
  subgraphs.append(get_subgraph(i))

for p, x in tasks:
  for i in subgraphs[p-1]:
    counter[i-1] += x
print(' '.join(map(str, counter)))


### FIXED CODE ###

from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

N, Q = map(int, input().split())
G = defaultdict(list)
for i in range(N - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1  # 0-indexed
    G[a].append(b)
    G[b].append(a)

# print('G', G)

V = [0] * N
for _ in range(Q):
    p, x = map(int, input().split())
    p = p - 1  # 0-indexed
    V[p] += x


def dfs(v, p):
    if p != -1:
        V[v] += V[p]
    for idx in G[v]:
        if idx == p:
            continue
        dfs(idx, v)


dfs(0, -1)

# print('V', V)

print(' '.join(map(str, V)))
### BUGGY CODE ###

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

for _ in range(q):
  l,r = map(int, input().split())
  print(s[l-1:r].count('AC'))

### FIXED CODE ###

N,Q=map(int,input().split())
S=input()
count=[0]*N
for i in range(1,N):
    count[i]+=count[i-1]
    if S[i-1:i+1]=="AC":count[i]+=1
for i in range(Q):
    l,r=map(int,input().split())
    print(count[r-1]-count[l-1])