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

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
S.insert(0,-10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
T.insert(0,-10**11)
Ds = {i:0 for i in range(1,A+1)}
Ds[A+1] = 10**11
Ds[0] = 10**11
for i in range(1,A+1):
    ind = bisect_right(T,S[i])
    Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(1,B+1)}
Dt[B+1] = 10**11
Dt[0] = 10**11
for j in range(1,B+1):
    ind = bisect_right(S,T[j])
    Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))
    

### FIXED CODE ###

from bisect import bisect_right
A,B,Q = map(int,input().split())
S = [int(input()) for _ in range(A)]
S.append(10**11)
S.insert(0,-10**11)
T = [int(input()) for _ in range(B)]
T.append(10**11)
T.insert(0,-10**11)
Ds = {i:0 for i in range(1,A+1)}
Ds[A+1] = 10**11
Ds[0] = 10**11
for i in range(1,A+1):
    ind = bisect_right(T,S[i])
    Ds[i] = min(T[ind]-S[i],S[i]-T[ind-1])
Dt = {j:0 for j in range(1,B+1)}
Dt[B+1] = 10**11
Dt[0] = 10**11
for j in range(1,B+1):
    ind = bisect_right(S,T[j])
    Dt[j] = min(S[ind]-T[j],T[j]-S[ind-1])
for _ in range(Q):
    x = int(input())
    inds = bisect_right(S,x)
    cnts = min(S[inds]-x+Ds[inds],x-S[inds-1]+Ds[inds-1])
    indt = bisect_right(T,x)
    cntt = min(T[indt]-x+Dt[indt],x-T[indt-1]+Dt[indt-1])
    print(min(cnts,cntt))
### BUGGY CODE ###

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

hen = [[0,0]]*n
for i in range(n-1) :
    hen[i] = list(map(int,input().split()))

xlist = [0]*n
for k in range(q) :
    p,x = map(int,input().split())
    xlist[p-1] += x

y = [0]*n
for i in range(n) :
    y[i] += xlist[i]
    
    r = i
    while True :
        for j in range(n) :
            if hen[j][1] - 1 == r :
                r = hen[j][0] - 1
                y[i] += xlist[r]
                break
        if j == n-1 :
            break

c = str(y[0])
for i in range(1,n) :
    c += ' ' + str(y[i])

print(c)


### FIXED CODE ###

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

hen = [[0,0]]*(n-1)
for i in range(n-1) :
    hen[i] = list(map(int,input().split()))

xlist = [0]*n
for k in range(q) :
    p,x = map(int,input().split())
    xlist[p-1] += x

#---

hen = sorted(hen, key=lambda x:x[1])
hen = sorted(hen, key=lambda x:x[0])

for i in range(n-1) :
    xlist[hen[i][1]-1] += xlist[hen[i][0]-1]

y = xlist.copy()

c = str(y[0])
for i in range(1,n) :
    c += ' ' + str(y[i])

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

def func(n):
    cnt = 0
    for x in range(1, 34):
        if(x**2+x >= n):
            break
        for y in range(1, 34):
            z = 1
            if(x**2+y**2+z**2+x*y+y*z+z*x > n):
                break
            while(x**2+y**2+z**2+x*y+y*z+z*x <= n):
                if(x**2+y**2+z**2+x*y+y*z+z*x == n):
                    cnt += 1
                    break
                z += 1
    return cnt

N = int(input())
    
for i in range(1, N+1):
    print(func(i))


### FIXED CODE ###

def func(n):
    cnt = 0
    a = int(n**0.5)
    for x in range(1, a+1):
        for y in range(x, a+1):
            z = y
            while(x**2+y**2+z**2+x*y+y*z+z*x <= n):
                if(x**2+y**2+z**2+x*y+y*z+z*x == n):
                    if(x == y == z):
                        cnt += 1
                    elif(x != y and y != z and z != x):
                        cnt += 6
                    else:
                        cnt += 3    
                    break
                z += 1
    return cnt

N = int(input())
    
for i in range(1, N+1):
    print(func(i))
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def inp_str():
    '''
    一行の文字をlistで取得
    '''
    return list(input())[:-1]


s = inp_str()
t = inp_str()
n = len(s)
m = len(t)
value = [[0]*(m+1) for i in range(n+1)]
ans = [[""]*(m+1) for i in range(n+1)]

for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
            ans[i + 1][j + 1] = "".join([ans[i][j], s[i]])
        elif value[i][j + 1] > value[i + 1][j]: #UP
            ans[i + 1][j + 1] = ans[i][j + 1]
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            ans[i + 1][j + 1] = ans[i + 1][j]
            value[i + 1][j + 1] = value[i + 1][j]

print(ans[n][m])


### FIXED CODE ###

import sys
input = sys.stdin.readline

s = list(input())
t = list(input())
n = len(s)-1
m = len(t)-1
value = [[0]*(m+1) for i in range(n+1)]


for i in range(n):
    for j in range(m):
        if s[i] == t[j]:
            value[i + 1][j + 1] = value[i][j] + 1
        elif value[i][j + 1] > value[i + 1][j]: #UP
            value[i + 1][j + 1] = value[i][j + 1]
        else:  # LEFT
            value[i + 1][j + 1] = value[i + 1][j]
i = n-1
j = m-1
ans=""
while i >= 0 and j >= 0:
    if s[i] == t[j]:
        ans = s[i] + ans
        i -= 1
        j -= 1
    elif value[i][j + 1] > value[i + 1][j]:
        i -= 1
    else:
        j -= 1
print(ans)
### BUGGY CODE ###

N = int(input())
D = [int(i) for i in input().split()]
D.sort()
M = int(input())
T = [int(i) for i in input().split()]
T.sort()
cnt = [0]*M
s = 0
for n in range(N):
    d = D[n]
    for m in range(s,M):
        if T[m] == d:
            T[m] = 0
            s = m
            cnt[m] += 1
            break

if sum(cnt) == M:
    print('YES')
else:
    print('NO')


### FIXED CODE ###

from collections import Counter
N = int(input())
D = [int(i) for i in input().split()]
M = int(input())
T = [int(i) for i in input().split()]

cD = Counter(D)

for t in T:
    if cD.get(t,0) == 0:
        print('NO')
        exit()
    else:
        cD[t] -= 1

print("YES")
### BUGGY CODE ###

a, b = map(int,input().split())

def cf(x1,x2):
  cf=[]
  for i in range(2,min(x1,x2)+1):
    if x1 % i == 0 and x2 % i == 0:
      cf.append(i)
  return cf

List = cf(a, b)
import fractions

def check(x1, x2):
  if fractions.gcd(x1, x2) == 1:
    return 1
  else:
    return 0


Answer = []
for i in range(len(List)):
  if i == 0:
    Answer.append(List[i])
  else:
    checker = 1
    for j in range(len(Answer)):
      checker *= check(Answer[j],List[i])
    if checker == 1:
      Answer.append(List[i])

print(len(Answer)+1)



### FIXED CODE ###

import fractions
A,B = map(int,input().split())
x = fractions.gcd(A,B)
pf = {}
for i in range(2,int(x**0.5)+2):
  while x%i == 0:
    pf[i] = pf.get(i,0) +1
    x //= i
if x > 1:
  pf[x] = 1
print(len(pf)+1)
### BUGGY CODE ###

import queue
import sys

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

        for i in range(H):
            S[i] = ["#"] + S[i] + ["#"]
        S = [["#"] * (W + 2)] + S + [["#"] * (W + 2)]

        already = set()
        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                for n in range(1, H + 1):
                    for m in range(1, W + 1):
                        if S[n][m] == "#" or (i, j) == (n, m) or (i, j, n, m) in already:
                            continue
                        v = self.min_move(S, (i, j), (n, m))
                        already.add((i, j, n, m))
                        already.add((n, m, i, j))
                        ans = max(ans, v)
        print(ans)

    def min_move(self, map, start, goal):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        while q:
            pos, cnt = q.get()
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) == goal:
                    return cnt + 1
                if map[i][j] == ".":
                    q.put(((i, j), cnt + 1))


# Run main
if __name__ == '__main__':
    Solution().main()


### FIXED CODE ###

import queue
import sys

input = sys.stdin.readline


class Solution:
    def main(self):
        H, W = map(int, input().split())
        S = [list(input().rstrip()) for _ in range(H)]

        for i in range(H):
            S[i] = ["#"] + S[i] + ["#"]
        S = [["#"] * (W + 2)] + S + [["#"] * (W + 2)]

        ans = 0
        for i in range(1, H + 1):
            for j in range(1, W + 1):
                if S[i][j] == "#":
                    continue
                v = self.min_move(S, (i, j))
                ans = max(ans, v)
        print(ans)

    def min_move(self, map, start):
        moving_range = ((1, 0), (-1, 0), (0, 1), (0, -1))

        q = queue.Queue()
        q.put((start, 0))

        already = {start}
        ret = 0
        while not q.empty():
            pos, cnt = q.get()
            ret = max(ret, cnt)
            for move in moving_range:
                i, j = pos[0] + move[0], pos[1] + move[1]
                if (i, j) not in already and map[i][j] == ".":
                    q.put(((i, j), cnt + 1))
                    already.add((i, j))

        return ret


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

N, M = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
hash = {}
hash[0] = 1
i = 0
for a in A:
    i = (i+a) % M
    if i in list(hash.keys()):
        hash[i] += 1
    else:
        hash[i] = 1
for h in list(hash.keys()):
    ans += hash[h] * (hash[h]-1) // 2

print(ans)

### FIXED CODE ###

from collections import defaultdict
N, M = map(int, input().split())
A = list(map(int, input().split()))

ans = 0
hash = defaultdict(int)
hash[0] = 1
i = 0
for a in A:
    i = (i+a) % M
    hash[i] += 1
for h in list(hash.keys()):
    ans += hash[h] * (hash[h]-1) // 2

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

N = int(input())
inlist = []
for i in range(N):
  inputst = input()
  inputstlist = list(inputst)
  inputstlist.sort()
  inlist.append(inputstlist)
inlist.sort()
count=0
i=0
while i<N:
  skip=0
  for j in range(i+1,N):
    flag1=0
    for k in range(10):
      if inlist[i][k]==inlist[j][k]:
        pass
      else:
        flag1=1
        break
    if flag1==0:
      count+=1
      skip+=1
    else:
      if skip>=1:
        i=i+skip
        count+=int(((skip-1)+1)*(skip-1)/2)
      break
  i+=1
print(count)      


### FIXED CODE ###

N = int(input())
inlist = []
for i in range(N):
  inputst = input()
  inputstlist = list(inputst)
  inputstlist.sort()
  inlist.append(inputstlist)
inlist.sort()
count=0
i=0
while i<N:
  skip=0
  for j in range(i+1,N):
    flag1=0
    for k in range(10):
      if inlist[i][k]!=inlist[j][k]:
        flag1=1
        break
    if flag1==0:#一致
      count+=1
      skip+=1
    else:#不一致
      break
  if skip>=1:
    i=i+skip
    count+=int(((skip-1)+1)*(skip-1)/2)
  else:
    i+=1
print(count)
### BUGGY CODE ###

# AGC033A - Darker and Darker (PyPy 400ms)
def bfs() -> None:
    dxy = [(1, 0), (-1, 0), (0, 1), (0, -1)]
    cur, q = 0, []
    # append default blacks to a queue
    q = [(x, y) for x in range(H) for y in range(W) if B[x][y] == 0]
    while q:  # append new blacks until all whites become black
        next_q = []
        for x, y in q:
            for dx, dy in dxy:
                nx, ny = x + dx, y + dy
                if 0 <= nx < H and 0 <= ny < W and B[nx][ny] == -1:
                    B[nx][ny] = cur + 1
                    next_q.append((nx, ny))
        q = next_q
        cur += 1
    return cur - 1


def main():
    global H, W, B
    H, W, *A = open(0).read().split()
    H, W = int(H), int(W)
    # default blacks: 0, whites: -1
    B = [[0 if i == "#" else -1 for i in a] for a in A]
    ans = bfs()
    print(ans)


if __name__ == "__main__":
    main()

### FIXED CODE ###

# AGC033A - Darker and Darker
from scipy.ndimage import distance_transform_cdt as dist


def main():
    """
    distance_transform_cdt(matric="taxicab"):
        0 0 0    1 1 1
        0 1 0 -> 1 0 1
        0 0 0    1 1 1
    """
    h, w = tuple(map(int, input().rstrip().split()))
    A = list(list(input()) for _ in range(h))
    B = [[1 if i == "." else 0 for i in a] for a in A]
    D = dist(B, metric="taxicab")
    print(D.max())


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

X = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    return divisors

def f(a, b):
  return a**5 - b**5

divs = make_divisors(X)
ans = 0
for div in divs:
  a = -div-120
  b = -120
  while f(a, b) < X and a < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
  a = -120
  b = -div-120
  while f(a, b) > X and b < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
    
print(ans[0], ans[1])

### FIXED CODE ###

X = int(input())

def make_divisors(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.sort()
    save = -1
    for i in range(len(divisors)):
        if divisors[i] >= 200:
            save = i
            break
    if save > 0:
        divisors = divisors[:save]
    return divisors

def f(a, b):
  return a**5 - b**5

divs = make_divisors(X)
ans = 0
for div in divs:
  a = -div-120
  b = -120
  while f(a, b) < X and a < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
  a = -120
  b = -div-120
  while f(a, b) > X and b < 2:
    a += 1
    b += 1
  if f(a, b) == X:
    ans = (a, b)
    
print(ans[0], ans[1])
### BUGGY CODE ###

from math import ceil

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

m = 10**6+100
n_map = {}
v_a = []
nn_map = {}
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
    if i in nn_map:
        continue
    for j in range(2, ceil(m / i) + 1):
        nn_map[i * j] = True

v_a = [k for k, v in n_map.items() if v == 1]

v_a.sort()
vv_a = []

for i in v_a:
    if i in nn_map:
        continue
    vv_a.append(i)

print(len(vv_a))

### FIXED CODE ###

from math import ceil

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

m = 10 ** 6
n_map = {}
v_a = []
for i in a:
    if i not in n_map:
        n_map[i] = 1
    else:
        n_map[i] += 1
v_a = [(k,v) for k, v in n_map.items()]

v_a.sort(key=lambda x: x[0])
res = 0
nn_map = {}
for i, v in v_a:
    if i in nn_map:
        continue
    for j in range(1, ceil(m / i) + 1):
        nn_map[i * j] = True
    if v == 1:
        res += 1
print(res)
### BUGGY CODE ###

import sys
N = int(input())
C = [0]
#c = [int(sys.stdin.readline()) for i in range(N)]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
#C = C+c
dp = [0] * (N + 2)
color = [[]for i in range((2*(10**5)+2))]
dp[0] = 1
dp[1] = 1
color[C[1]].append(1)
for i in range(2, N+1):
    dp[i] = dp[i - 1] + sum([dp[col - 1] for col in color[C[i]]])
    color[C[i]].append(i)
    dp[i] %= (10 ** 9 + 7)
# print(dp)
print(dp[N])


### FIXED CODE ###

import sys
N = int(input())
C = [0]
n = N
for i in range(1, n + 1):
    c = int(sys.stdin.readline())
    if c == C[-1]:
        N -= 1
    else:
        C.append(c)
dp = [0] * (N + 2)
dp[0] = 1
dp[1] = 1
cumsum = [0] * (2 * (10 ** 5) + 2)
cumsum[C[1]] = 1
for i in range(2, N+1):
    dp[i] = dp[i - 1] + cumsum[C[i]]
    cumsum[C[i]] += dp[i-1]
    dp[i] %= (10 ** 9 + 7)
print(dp[N])
### BUGGY CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = [[X[k],k] for k in range(N)]
Z = Y.copy()
Z.sort()

A = [0 for k in range(N)]

for k in range(N):
    A[Z[k][1]] = (Z[:Y[k][1]]+Z[Y[k][1]+1:])[N//2-1][0]

for x in A:
    print(x)

### FIXED CODE ###

N = int(input())
X = list(map(int, input().split()))
Y = [[X[k],k] for k in range(N)]
Y.sort()
A = [0 for k in range(N)]

for k in range(N):
    if k >= N//2:
        A[Y[k][1]] = Y[N//2-1][0]
    else:
        A[Y[k][1]] = Y[N//2][0]

for x in A:
    print(x)
### BUGGY CODE ###

N=int(input())
S=[ord(c) for c in input()]
def zalgo(S):
    a=[0]*len(S)
    c=0
    for i in range(1,len(S)):
        if i+a[i-c]<c+a[c]:
            a[i]=a[i-c]
        else:
            j=max(0,c+a[c]-i)
            while i+j<len(S) and S[j]==S[i+j]:
                j+=1
            a[i]=min(i,j)
    a[0]=len(S)
    return a
r=0
for i in range(N):
    a=zalgo(S[i:])
    m=max(a[1:]) if len(a)>1 else 0
    r=max(r,m)
print(r)

### FIXED CODE ###

N=int(input())
S=input()
l,u=0,N
while l+1<u:
    m=(l+u)//2
    s=set()
    for i in range(N-m*2+1):
        s.add(S[i:i+m])
        if S[i+m:i+m*2] in s:
            l=m
            break
    if l!=m:
        u=m
print(l)
### BUGGY CODE ###

N = int(input())
S = list(input())
f=0
ijk = list()
for i in range(N):
    for j in range(N):
        for k in range(N):
            if(k>j>i):
                if(k == j+(j-i)):
                    pass
                elif(i == j-(j-k)):
                    pass
                else:
                    ijk.append([i+1,j+1,k+1])
# print(S)
# print(ijk)

for i in range(len(ijk)):
    if(S[ijk[i][0]-1]== S[ijk[i][1]-1]):pass
    elif(S[ijk[i][0]-1]== S[ijk[i][2]-1]):pass
    elif(S[ijk[i][1]-1]== S[ijk[i][2]-1]):pass
    else:f+=1
print(f)

### FIXED CODE ###

n=int(input())
s=input()
r=g=b=0
for i in s:
  if i=="R":r+=1
  elif i=="G":g+=1
  else:b+=1

ans=r*g*b
for i in range(n):
  for j in range(i+1,n):
    k_ = j+(j-i)
    if(k_ >=n):
      break
    ans -= int(s[i]!= s[j] and s[i] != s[k_] and s[j] != s[k_])

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

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

ans=1
for i in A:
    ans*=i
if ans>10**18:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

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

import sys
ans = 1
for i in range(n):
    ans *= A[i]
    if ans > 10 ** 18:
        for j in range(i,n):
            if A[j]==0:
                print(0)
                sys.exit()
        ans=-1
        break

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

N,Q = map(int, input().split())
S = list(input())
lr = [list(map(int,input().split())) for i in range(Q)]
bef = ''
pos = []
for idx,val in enumerate(S):
    if val == 'C' and bef == 'A':
        pos.append((idx -1) * 10 + idx)
    bef = val

cnt = 0
for i in range(Q):
    min_v = (lr[i][0] - 1) * 10 + lr[i][0]
    max_v = (lr[i][1] - 2) * 10 + (lr[i][1] - 1)
    for p in pos:
        if p >= min_v and p <= max_v:
            cnt += 1
    print(cnt)
    cnt = 0



### FIXED CODE ###

N,Q = map(int, input().split())
S = input()
lrs = [list(map(int, input().split())) for i in range(Q)]

total = []
total.append(0)
for i in range(1, N):
    if S[i - 1] == 'A' and S[i] == 'C':
        total.append(1)
    else:
        total.append(0)
totsum = 0
for idx, val in enumerate(total):
    totsum += val
    total[idx] = totsum

for lr in lrs:
    print(total[lr[1] - 1] - total[lr[0] - 1])
### BUGGY CODE ###

N=int(input())
A=list(map(int,input().split()))
Q=int(input())
List=[i for i in range(10**5+1)]
for i in range(Q):
    B,C=map(int,input().split())
    List[B]=C
    for i in  range(1,len(List)):
        index=i
        while index!=List[index]:
            index=List[index]
            if index==i:
                break
            # print(index)
            # print(List)
        List[i]=index
    ChangedA=[List[a] for a in A]
    print(sum(ChangedA))

### FIXED CODE ###

import numpy as np
N=int(input())
A=list(map(int,input().split()))
SUM=sum(A)
Q=int(input())
List=np.array([0 for _ in range(10**5+1)])
for a in A:
    List[a]+=1
for q in range(Q):
    B,C=map(int,input().split())
    SUM-=B*List[B]
    SUM+=C*List[B]
    List[C]+=List[B]
    List[B]=0
    print(SUM)
### BUGGY CODE ###

def divisor_enumetarion(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.remove(n)
    return divisors
    
n,k=map(int,input().split())


dp=[0]*k


ans=0
for i in range(k,0,-1):
    toori=(k//i)**n

    dp[i-1]+=toori

    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]

    ans+=dp[i-1]*i
#    print(dp)
#    print(i,dp[i-1])
print(ans%(10**9+7))

### FIXED CODE ###

def divisor_enumetarion(n):
    divisors = []
    for i in range(1, int(n**0.5)+1):
        if n % i == 0:
            divisors.append(i)
            if i != n // i:
                divisors.append(n//i)
    divisors.remove(n)
    return divisors
    
n,k=map(int,input().split())

dp=[0]*k
mod=10**9+7

ans=0
for i in range(k,0,-1):
    toori=pow(k//i,n,mod)

    dp[i-1]+=toori

    x=divisor_enumetarion(i)
    for j in x:
        dp[j-1]-=dp[i-1]%mod

    ans+=(dp[i-1]*i)%mod
#    print(dp)
#    print(i,dp[i-1])
print(ans%mod)

#gcdがiの時だけを考え通りを引いて1を足す
### BUGGY CODE ###

s=input()

l=[0]
ans=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]=="L" and s[i+1]=="R":
        l.append(i+1)
       
n=len(l)+1
l.append(len(s))
#print(set(s[l[0]:l[1]]))

for i in range(n-1):
    #print(s[l[i]:l[i+1]])
    for j in range(len(s[l[i]:l[i+1]])-1):
        p=len(s[l[i]:l[i+1]])
        if set(s[l[i]:l[i+1]])=={"L"}:
            ans[l[i]]=p
            break
        if set(s[l[i]:l[i+1]])=={"R"}:
            ans[l[i+1]-1]=p
            break
        if s[l[i]:l[i+1]][j]=="R" and s[l[i]:l[i+1]][j+1]=="L":
            if j%2==1:
                ans[l[i]+j]=p//2
                ans[l[i]+j+1]=p-p//2
                break
            else:
                ans[l[i]+j]=p-p//2
                ans[l[i]+j+1]=p//2
                break
print(*ans)


            
  


### FIXED CODE ###

s=input()

l=[0]
ans=[0]*(len(s))
for i in range(len(s)-1):
    if s[i]=="L" and s[i+1]=="R":
        l.append(i+1)
       
n=len(l)+1
l.append(len(s))
#print(set(s[l[0]:l[1]]))

for i in range(n-1):
    #print(s[l[i]:l[i+1]])
    for j in range(len(s[l[i]:l[i+1]])-1):
        p=len(s[l[i]:l[i+1]])
        if s[l[i]]=="L":
            ans[l[i]]=p
            break
        if s[l[i+1]-1]=="R":
            ans[l[i+1]-1]=p
            break
        if s[l[i]:l[i+1]][j]=="R" and s[l[i]:l[i+1]][j+1]=="L":
            if j%2==1:
                ans[l[i]+j]=p//2
                ans[l[i]+j+1]=p-p//2
                break
            else:
                ans[l[i]+j]=p-p//2
                ans[l[i]+j+1]=p//2
                break
print(*ans)
### BUGGY CODE ###

N = int(input())
students = input().split()
turns = [str(students.index(str(x)) + 1) for x in range(1, N + 1) ]
print(' '.join(turns))

### FIXED CODE ###

# coding: utf-8
N = int(input())
student_list = [0] * (N + 1)
turn_list = [int(x) for x in input().split()]

for i, s in enumerate(turn_list):
    student_list[s] = i + 1
student_list.pop(0)
for s in student_list:
    print(str(s), end=' ')
print()
### BUGGY CODE ###

H,W,D=map(int,input().split())
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  s,k=L[A-1]
  ans=0
  for j in range((B-A)//D):
    a,b=L[A-1+(j+1)*D]
    ans+=abs(a-s)+abs(b-k)
    s=a
    k=b
  print(ans)

### FIXED CODE ###

import sys
input=sys.stdin.readline
H,W,D=map(int,input().split())
cost=[[0 for _ in range((H*W)//D+1)] for i in range(D)]
L=[0]*(H*W)
for i in range(H):
  L1=list(map(int,input().split()))
  for j in range(W):
    L[L1[j]-1]=[i,j]
    if L1[j]%D!=0:
      cost[L1[j]%D][L1[j]//D]=[i,j,0]
    else:
      cost[L1[j]%D][(L1[j]//D)-1]=[i,j,0]
for i in range(D):
  for j in range(1,len(cost[i])):
    if cost[i][j]!=0:
      cost[i][j][2]=cost[i][j-1][2]+abs(cost[i][j][0]-cost[i][j-1][0])+abs(cost[i][j][1]-cost[i][j-1][1])
Q=int(input())
for i in range(Q):
  A,B=map(int,input().split())
  c=A%D
  a=A//D
  b=B//D
  if c==0:
    a,b=a-1,b-1
  print(cost[c][b][2]-cost[c][a][2])