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

from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            col[v] = c
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)


### FIXED CODE ###

from collections import deque
N = int(input())
X = [[] for _ in range(N)]
for i in range(N):
    s = input()
    for j in range(N):
        if s[j] == "1":
            X[i].append(j)

def bipartite(n, E):
    col = [-1] * n
    f = 0
    for i in range(n):
        if col[i] >= 0: continue
        que = deque([[i, 0]])
        while que:
            v, c = que.popleft()
            if col[v] == -1:
                col[v] = c
            elif col[v] == c:
                continue
            else:
                f = 1
                break
            for ne in E[v]:
                if col[ne] == c:
                    f = 1
                    break
                if col[ne] < 0:
                    que.append([ne, 1-c])

            if f:
                break
        if f:
            break
    return 1-f

def BFS(n, E, i0=0):
    Q = deque([i0])
    D = [-1] * n
    D[i0] = 0
    while Q:
        x = Q.popleft()
        for c in E[x]:
            if D[c] == -1:
                D[c] = D[x] + 1
                Q.append(c)
    return D

if bipartite(N, X):
    print(max([max(BFS(N, X, i)) for i in range(N)])+1)
else:
    print(-1)
### BUGGY CODE ###

INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1
		while self.n < size:
			self.n *= 2
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)//2
			self.node[x] = min(self.node[2*x+1], self.node[2*x+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b = map(int, input().split())
qs = [a] + list(map(int, input().split()))
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
for i in range(q):
	x, y = qs[i], qs[i+1]
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff

N = dp_l.n
print(total_diff + min(dp_l.node[i+N-1] + i for i in range(1, n+1)))


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
INF = 10**12

class Rmin():
	def __init__(self, size):
		#the number of nodes is 2n-1
		self.n = 1 << (size.bit_length())
		self.node = [INF] * (2*self.n-1)

	def Access(self, x):
		return self.node[x+self.n-1]

	def Update(self, x, val):
		x += self.n-1
		self.node[x] = val
		while x > 0:
			x = (x-1)>>1
			self.node[x] = min(self.node[(x<<1)+1], self.node[(x<<1)+2])
		return

	#[l, r)
	def Get(self, l, r):
		L, R = l+self.n, r+self.n
		s = INF
		while L<R:
			if R & 1:
				R -= 1
				s = min(s, self.node[R-1])
			if L & 1:
				s = min(s, self.node[L-1])
				L += 1
			L >>= 1
			R >>= 1
		return s

n, q, a, b, *qs = map(int, read().split())
dp_l, dp_r = Rmin(n+1), Rmin(n+1)
dp_l.Update(b, -b)
dp_r.Update(b, b)

total_diff = 0
x = a
for y in qs:
	diff = abs(y - x)
	l_min = dp_l.Get(1, y)
	r_min = dp_r.Get(y, n+1)
	res = min(l_min + y, r_min - y)
	dp_l.Update(x, res - diff - x)
	dp_r.Update(x, res - diff + x)
	total_diff += diff
	x = y

N = dp_l.n
print(total_diff + min((l+r)>>1 for l, r in zip(dp_l.node[N:], dp_r.node[N:])))
### BUGGY CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]

A.sort()

for B, C in BC:
    for i in range(B):
        if A[i] < C:
            A[i] = C
        else:
            break
    A.sort()

print(sum(A))

### FIXED CODE ###

from sys import stdin
import math
import fractions
from collections import deque

INF = 10 ** 10

N, M = [int(x) for x in stdin.readline().rstrip().split()]
A = [int(x) for x in stdin.readline().rstrip().split()]
BC = [list(map(int, stdin.readline().rstrip().split())) for _ in range(M)]
A.sort()
BC.sort(key=lambda x: (x[1]), reverse=True)

i = 0
A_len = len(A)

for B, C in BC: # O(10^5)
    for _ in range(B):
        if A[i] < C:
            A[i] = C
            i += 1
            if i > A_len - 1:
                print(sum(A))
                exit()
        else:
            print(sum(A))
            exit()

print(sum(A))
### BUGGY CODE ###

# coding: utf-8
# Your code here!
import math
line = list(map(int,input().split()))

A,B,N =line[0],line[1],line[2]

ans = (N+1)//B
if ans ==0:
    print(math.floor(A*N/B)-A*math.floor(N/B))
else:
    start = (math.floor(A*N/B)-A*math.floor(N/B))
    #kouho =[0 for j in range(ans)]
    for i in range(1,ans+1):
        x= i*B-1
        start = max((math.floor(A*x/B)-A*math.floor(x/B)),start)
    print(start)

### FIXED CODE ###

# coding: utf-8
# Your code here!
def main():
    import sys
    line = sys.stdin.readline
    A,B,N = map(int,input().split())
    if B>N:
        ans = A*N//B
    else:
        ans = A*(B-1)//B
    print(ans)

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

s = input()
q = int(input())
f = ""
b = ""
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            f+=que[2]
        else:
            b+=que[2]

if forward:
    ff = ""
    for i in reversed(range(len(f))):
        ff += f[i]
    
    print(ff+s+b)
else:
    bb = ""
    for i in reversed(range(len(b))):
        bb += b[i]
    ss = ""
    for i in reversed(range(len(s))):
        ss += s[i]
    print(bb+ss+f)

### FIXED CODE ###

from collections import deque
s = input()
q = int(input())
f = ""
b = ""
forward = True
for _ in range(q):
    que = list(input().split())
    if int(que[0]) == 1:
        if forward:
            forward = False
        else:
            forward = True
    else:
        if (int(que[1]) == 1 and forward) or (int(que[1]) == 2 and not forward):
            f+=que[2]
        else:
            b+=que[2]

if forward:
    print(f[::-1]+s+b)
else:

    print(b[::-1]+s[::-1]+f)
### BUGGY CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].add(v)
    ns[v].add(u)
dp = [[(-1,0,0)]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
for i0 in range(10, -1, -1):
    for i,v,d,c in qs:
        if i0<=d:
            dp[0][v] = (i,c,d)
    for i in range(1,11):
        for u in range(n):
            if dp[i-1][u][0]>dp[i][u][0]:
                ind0, c0, d0 = dp[i-1][u]
            else:
                ind0, c0, d0 = dp[i][u]
            for v in ns[u]:
                ind,c,d = dp[i-1][v]
                if ind>ind0 and d>0 and i0<=i+d:
                    ind0, c0, d0 = ind, c, d-1
            dp[i][u] = (ind0, c0, d0)
#     print(dp[10])
write("\n".join(map(str, (dp[10][u][1] for u in range(n)))))

### FIXED CODE ###

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")

n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(list)
for _ in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    ns[u].append(v)
    ns[v].append(u)
    
dp = [[-1]*n for _ in range(11)]
q = int(input())
qs = [None]*q
for i in range(q):
    v,d,c = tuple(map(int, input().split()))
    v -= 1
    qs[i] = (i,v,d,c)
    dp[d][v] = i
from itertools import product
for i,u in product(range(10,0,-1), range(n)):
    if dp[i][u]>=0:
        dp[i-1][u] = max(dp[i-1][u], dp[i][u])
        for v in ns[u]:
            dp[i-1][v] = max(dp[i-1][v], dp[i][u])

write("\n".join(map(str, ((qs[dp[0][u]][3] if dp[0][u]>=0 else 0) for u in range(n)))))
### BUGGY CODE ###

 
N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (10**5 + 1)
A = [int(input()) for _ in range(M)] 
if (N-1 in A) == False:
    dp[N], dp[N-1] = 1, 1
else:
    dp[N] = 1

for i in range(N-2, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod

print(dp[0])

### FIXED CODE ###

N, M = map(int, input().split())
mod = 1000000007
dp = [0] * (N+2)
A = set([int(input()) for _ in range(M)]) 
dp[-2] = 1

for i in range(N-1, -1, -1):
    if (i in A) == False:
        dp[i] = (dp[i + 1] + dp[i + 2]) % mod 

print(dp[0])
### BUGGY CODE ###

N = int(input())
A = [int(i) for i in input().split()]
for i in range(N):
    A[i] *= 2
import numpy as np
mat = [[0] * N for _ in range(N)]
for i in range(N):
    j = i + 1
    if j == N:
        j = 0
    mat[i][i] = 1
    mat[i][j] = 1
AB = np.array(mat)
inv_A = np.linalg.inv(AB)
ans = list(np.dot(inv_A,A))
for i in range(N):
    ans[i] = int(ans[i])
print(*ans)

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
b=[sum(a)-2*sum(a[1:n-1:2])]
for i in range(1,n):
  b.append(2*a[i-1]-b[-1])
print(*b)
### BUGGY CODE ###

N = int(input())
from collections import Counter
from heapq import heappush, heappop, heappushpop, heapify, heapreplace, merge
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      cb[q] -= 1
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      ca[q] -= 1
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    ca[p] -= 1
    cb[q] -= 1
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)


### FIXED CODE ###

N = int(input())
from collections import Counter
A = list(map(int, input().split()))
B = list(map(int, input().split()))
ca = Counter(A)
cb = Counter(B)
mod = 10**6
cnts = [set() for _ in range(N+1)]
for i in range(1,N+1):
  if ca[i]+cb[i]>N:
    print('No')
    exit()
  if ca[i]+cb[i]>0:
    cnts[ca[i]+cb[i]].add(i)

def get_any(counts,r):
  for k in counts.keys():
    if counts[k]>0 and k!=r:
      return k

def update_cnt(cnt_,r):
  cnt_[r] -= 1
  if cnt_[r]==0:
    del cnt_[r]

lis = [[] for _ in range(N+1)]
for i in range(N,0,-1):
  if len(cnts[i])==2:
    p,q = cnts[i]
    for j in range(ca[p]):
      lis[p].append(q)
    for j in range(ca[q]):
      lis[q].append(p)
    break
  elif len(cnts[i])==1:
    p, = cnts[i]
    for j in range(ca[p]):
      q = get_any(cb,p)
      update_cnt(cb,q)
      lis[p].append(q)
    for j in range(cb[p]):
      q = get_any(ca,p)
      update_cnt(ca,q)
      lis[q].append(p)
    break
  else:
    p = get_any(ca,-1)
    q = get_any(cb,p)
    lis[p].append(q)
    cnts[ca[p]+cb[p]].remove(p)
    cnts[ca[q]+cb[q]].remove(q)
    update_cnt(ca,p)
    update_cnt(cb,q)
    cnts[ca[p]+cb[p]].add(p)
    cnts[ca[q]+cb[q]].add(q)
ans = []
for i in range(1,N+1):
  for b in lis[i]:
    ans.append(b)
print('Yes')
print(*ans)
### BUGGY CODE ###

n,q = map(int,input().split())
s = list(input())
p = [tuple(map(str,input().split())) for i in range(q)]

#s[x]が左へ抜けるか O(q)
def judge_left(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return True
        if x == n:
            return False
    return False

#s[x]が右へ抜けるか O(q)
def judge_right(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return False
        if x == n:
            return True
    return False

#どこまで左で抜けるか
ok = -1
ng = n
while ng-ok > 1:
    mid = (ng+ok)//2
    if judge_left(mid):
        ok = mid
    else:
        ng = mid
left = ok+1

#どこまで右で抜けるか
ok = n
ng = -1
while ok-ng >1:
    mid = (ok+ng)//2
    if judge_right(mid):
        ok = mid
    else:
        ng = mid
right = n-ok

print(max(n-left-right,0))

### FIXED CODE ###

n,q = map(int,input().split())
s = list(input())
p = [tuple(map(str,input().split())) for i in range(q)]

#s[x]が左へ抜けるか O(q)
def judge_left(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return True
        if x == n:
            return False
    return False

#s[x]が右へ抜けるか O(q)
def judge_right(x):
    for i in range(q):
        if p[i][0] == s[x]:
            if p[i][1] == 'L':
                x -= 1
            else:
                x += 1
        if x == -1:
            return False
        if x == n:
            return True
    return False

#どこまで左で抜けるか
ok = -1
ng = n
while ng-ok > 1:
    mid = (ng+ok)//2
    if judge_left(mid):
        ok = mid
    else:
        ng = mid
left = ok+1

#どこまで右で抜けるか
ok = n
ng = -1
while ok-ng >1:
    mid = (ok+ng)//2
    if judge_right(mid):
        ok = mid
    else:
        ng = mid
right = n-ok

print(max(n-left-right,0))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    c = [-1]
    INF = 10**9+7
    for _ in range(N):
        a = int(input())
        if c[-1] == a:
            continue
        c.append(a)
    
    c.pop(0)
    d,M = len(c),max(c)    
    _c = list(set(c))
    
    dp = [1 for _ in range(d+1)]
    c_dp = [[0 for _ in range(d+1)] for _ in range(M+1)]
    for i in range(d):
        for j in _c:
            if c[i] != j:
                c_dp[j][i+1] = c_dp[j][i]
            else:
                dp[i+1] = (c_dp[j][i] + dp[i])%INF
                c_dp[j][i+1] = dp[i+1]
                
    print(dp[-1])
    
if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N = int(input())
    c = [-1]
    INF = 10**9+7
    for _ in range(N):
        a = int(input())
        if c[-1] == a-1:
            continue
        c.append(a-1)
    
    c.pop(0)
    d,M = len(c),max(c)
    dp = [1 for _ in range(d+1)]
    c_dp = [0 for _ in range(M+1)]
    for i in range(d):
        now = c[i]
        dp[i+1] = (dp[i] + c_dp[now])%INF
        c_dp[now] = dp[i+1]
                
    print(dp[-1])
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline
from itertools import product

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dic = {}
    for p in product(range(n+1),repeat=3):
        dic['{}-{}-{}'.format(*p)] = .0
    n = float(n)
    def exp(i,j,k):
        if i + j + k == 0:
            return 0
        key = '{}-{}-{}'.format(i,j,k)
        if key in dic and dic[key] > 0:
            return dic[key]
        ans = n
        if i > 0:
            ans += i * exp(i-1,j,k)
        if j > 0:
            ans += j * exp(i+1,j-1,k)
        if k > 0:
            ans += k * exp(i,j+1,k-1)
        ans /= (i+j+k)
        dic[key] = ans
        return ans

    ans = exp(a[1],a[2],a[3])
    print(ans)

if __name__ == '__main__':
    main()

### FIXED CODE ###

from collections import Counter
import sys
input = sys.stdin.buffer.readline

def main():
    n = int(input())
    a = Counter(map(int, input().split()))
    dp = [[[.0] * (n+1) for _ in range(n+1)] for _ in range(n+1)]
    for k in range(a[3]+1):
        for j in range(a[2]+a[3]-k+1):
            for i in range(n-j-k+1):
                if i + j + k == 0:
                    continue
                tmp = n
                if i > 0:
                    tmp += i * dp[i-1][j][k]
                if j > 0:
                    tmp += j * dp[i+1][j-1][k]
                if k > 0:
                    tmp += k * dp[i][j+1][k-1]
                dp[i][j][k] = tmp / (i+j+k)
    print(dp[a[1]][a[2]][a[3]])

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

#import copy
def main():
    n,q = map(int,input().split()) 
    s=list(input())
    cnt=[0 for _ in range(n+2)]
    for i in range(n-1):
        if s[i]=="A" and s[i+1]=="C":
            cnt[i]=1            
    for _ in range(q):
        l,r = map(int,input().split())
        print(sum(cnt[l-1:r-1]))
main()

### FIXED CODE ###

#import copy
def main():
    # x,y = map(int,input().split())           x=1,y=2
    # a = input().split()                      a=['1','2','3',...,'n']
    # a = list(map(int,input().split()))       a=[1,2,3,4,5,...,n]
    # li = input().split('T')	              FFFTFTTFF => li=['FFF', 'F', '', 'FF']
    # 複数行の「1 2 3 4」型の入力を一配列に
    # x = sorted([list(map(int, input().split())) for _ in range(n)])
    # ソート x.sort(key=lambda y:y[1])
    # [chr(i) for i in range(97, 97+26)] 英語小文字リスト
    # [chr(i) for i in range(65, 65+26)] 英語大文字リスト
    # ord(c) chr(2) alphabet <=> number
    n,q = map(int,input().split()) 
    s=input()
    cnt=[0 for _ in range(n+1)]
    for i in range(n):
        cnt[i+1]=cnt[i]+(1 if s[i:i+2]=="AC" else 0)
    for _ in range(q):
        l,r = map(int,input().split())
        print(cnt[r-1]-cnt[l-1])
main()
### BUGGY CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

res = 0
for i in range(N):
	indB = bisect.bisect_right(B,A[i])
	for j in range(indB,N):
		indC = bisect.bisect_right(C,B[j])
		ansC = N - indC
		res += ansC

print(res)

### FIXED CODE ###

import bisect
N = int(input())
A = sorted(list(map(int, input().split())))
B = sorted(list(map(int, input().split())))
C = sorted(list(map(int, input().split())))

res = 0
for j in range(N):
	indA = bisect.bisect_left(A,B[j])
	ansA = indA
	indC = bisect.bisect_right(C,B[j])
	ansC = N - indC
	res += ansA * ansC

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

n = int(input())
power = 1
for i in range(1, n+1):
  power *= i
print(power%(10**9+7))

### FIXED CODE ###

n = int(input())
power = 1
for i in range(1, n+1):
  power = (power*i)%(10**9+7)
print(power)
### BUGGY CODE ###

L,R = map(int,input().split())

minv = 2019
for i in range(L,R):
  for j in range(i+1,R+1):
    x = i % 2019
    y = j % 2019
    val = (x * y) % 2019
    if minv > val:
      minv = val
    
print(minv)

### FIXED CODE ###

L,R = map(int,input().split())

if R - L > 2019:
  print(0)
else:
  minv = 2018 * 2018
  for i in range(L,R):
    for j in range(i+1,R+1):
      x = i % 2019
      y = j % 2019
      val = (x * y) % 2019
      if minv > val:
        minv = val
  print(minv)
### BUGGY CODE ###

MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))


### FIXED CODE ###

# coding: utf-8
MOD = int(1e9 + 7)

def f(N, M, s, t):
    dp = [[0] * (M + 1) for _ in range(N + 1)]
    cums = [[0] * (M + 1) for _ in range(N + 1)]

    for i in range(1, N + 1):
        for j in range(1, M + 1):
            dp[i][j] = 0 if s[i-1] != t[j-1] else (cums[i-1][j-1] + 1) % MOD
            cums[i][j] = cums[i-1][j] + cums[i][j-1] - cums[i-1][j-1] + dp[i][j]
    return((cums[N][M] + 1) % MOD)

n, m = map(int, input().split())
s = list(map(int, input().split()))
t = list(map(int, input().split()))
print(f(n, m, s, t))
### BUGGY CODE ###

N = int(input())
A = [int(input()) for _ in range(N)]
As = set(A)

ans = 0
for a in As:
    if A.count(a) % 2 == 0:
        pass
    else:
        ans += 1

print(ans)

### FIXED CODE ###

'''
全量のリストを用いると検索対象が大きくなってしまうため、ディクショナリで都度追加/削除する
'''

N = int(input())

A = {}

for _ in range(N):
    tmp = int(input())
    if tmp in A:
        del A[tmp]
    else:
        A[tmp] = 1

print(len(A))
### BUGGY CODE ###

n,k=map(int,input().split())
*p,=map(int,input().split())
px=[]
for i in p:
	s=(i*(i+1))/2
	s1=s/i
	px.append(s1)
ans=[]
for i in range(n-k+1):
	x=sum(px[i:i+k])
	ans.append(x)
print(max(ans))

### FIXED CODE ###

n,k=map(int,input().split())
*p,=map(int,input().split())
px=[(i+1)/2 for i in p]
px_sum=[0]
for j in range(len(px)):
	px_sum.append(px_sum[j]+px[j])
ans=0
for i in range(n-k+1):
	a=px_sum[i+k]-px_sum[i]
	ans=max(a,ans)
print(ans)
### BUGGY CODE ###

def solve(A, B):
    M = A * B
    cnt = 0

    x, y = A, B
    while y - x >= 1:
        x += 1
        y = M // x if M % x else M // x - 1
        cnt += 1
    cnt += y - 1

    x, y = B, A
    while y - x >= 1:
        x += 1
        y = M // x if M % x else M // x - 1
        cnt += 1
    cnt += y - 1

    return cnt


Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]

for A, B in Query:
    print(solve(A, B))


### FIXED CODE ###

def solve(A, B):
    from math import sqrt
    M = A * B
    cnt = 0

    x, y = A, B
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - A
    cnt += y - 1

    x, y = B, A
    if y - x >= 1:
        z = int(sqrt(M))
        x = z
        y = M // x if M % x else M // x - 1
        cnt += z - B
    cnt += y - 1

    return cnt


Q = int(input())
Query = [tuple(map(int, input().split())) for _ in range(Q)]

for A, B in Query:
    print(solve(A, B))