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

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

def f(i):
    total = 0
    for j in range(N):
        total += A[(i + j) % N] * (1 if j % 2 == 0 else -1)
    return total

B = [f(i) for i in range(N)]

print(' '.join(map(str, B)))

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[0] // 2

# 2 * A[0] = B[0] + B[1]
# 2 * A[1] = B[1] + B[2]
# 2 * A[2] = B[2] + B[0]

# 2 * A[2] - 2 * A[1] = B[0] - B[1]
# 2 * A[0] - 2 * A[2] = B[1] - B[2]
# 2 * A[1] - 2 * A[0] = B[0] - B[2]

# A[0] - A[2] + A[1] = B[1]

# B[i] = A[i] + A[i - 1] - A[i + 1]

# A[0] = B[0] // 2 + B[1] // 2
# A[1] = B[1] // 2 + B[2] // 2
# A[2] = B[2] // 2 + B[3] // 2
# A[3] = B[3] // 2 + B[4] // 2
# A[4] = B[4] // 2 + B[0] // 2

# A[0] - A[1] = B[0] - B[2]
# A[1] - A[2] = B[1] - B[3]
# A[2] - A[3] = B[2] - B[4]
# A[3] - A[4] = B[3] - B[0]
# A[4] - A[0] - B[4] - B[1]

# A[0] - A[1] + A[2] - A[3] + A[4] = B[0]
# A[1] - A[2] + A[3] - A[4] + A[0] = B[1]
# A[2] - A[3] + A[4] - A[0] + A[1] = B[2]
# A[3] - A[4] + A[0] - A[1] + A[2] = B[3]


### FIXED CODE ###

from functools import lru_cache
N = int(input())
A = list(map(int, input().split()))

@lru_cache(maxsize=N)
def f(i):
    if i >= 2:
        return f(i - 2) + 2 * A[i - 1] - 2 * A[i - 2]
    total = 0
    for j in range(N):
        if j % 2 == 0:
            total += A[(i + j) % N]
        else:
            total -= A[(i + j) % N]
    return total

B = (f(i) for i in range(N))

print(*B)
### BUGGY CODE ###

import bisect
import sys
from itertools import accumulate
input = sys.stdin.readline
def hsnum(ls,x):
    n = len(ls)
    num = 0
    for i in range(n):
        y = x-ls[i]
        num += n-bisect.bisect_left(ls,y)
    return num
n,m = map(int, input().split())
a = list(map(int, input().split()))
a.sort()
suma = [0]+list(accumulate(a))
lx = 0
rx = 10**10+2
error = 0
while lx < rx:
    mx = (lx+rx)//2
    if hsnum(a,mx) < m:
        rx = mx
    elif hsnum(a,mx) > m:
        if hsnum(a,mx+1) < m:
            error = hsnum(a,mx)-m
            lx = mx
            break
        lx = mx + 1
    else:
        lx = mx
        break
maxsum = lx
ans = 0
for i in range(n):
    rema = maxsum - a[i]
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*a[i]
    ans += suma[n]-suma[j]
print(ans-error*lx)

### FIXED CODE ###

def main():
  import bisect
  import sys
  from itertools import accumulate
  input = sys.stdin.readline
  def hsnum(x):
    num = 0
    for i in a:
      y = x-i
      num += n-bisect.bisect_left(a,y)
    return num
  n,m = map(int, input().split())
  a = list(map(int, input().split()))
  a.sort()
  suma = [0]+list(accumulate(a))
  lx = 0
  rx = 2*10**5+2
  error = 0
  while lx+1 < rx:
    mx = (lx+rx)//2
    if hsnum(mx) < m:
      rx = mx
    elif hsnum(mx) > m:
      lx = mx + 1
    else:
      lx = mx
      break
  if hsnum(lx)<m:
    lx -= 1
  error = hsnum(lx)-m
  ans = 0
  for i in a:
    rema = lx - i
    j = bisect.bisect_left(a,rema)
    ans += (n-j)*i-suma[j]
  ans += suma[n]*n
  print(ans-error*lx)
if __name__ == "__main__":
    main()
### BUGGY CODE ###

from collections import deque

H, W = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map_list = []
for i in range(H):
    str_input = input()
    map_list.append(list(str_input))

walk = [[1,0], [-1,0], [0,1], [0,-1]] #　下　上　右　左
warp = [[2,-2], [2,-1], [2,0], [2,1],[2,2], [1,-2], [1,-1], [1,1],[1,2], [0,-2], [0,2], [-1,-2],[-1,-1], [-1,1], [-1,2],[-2,-2], [-2,-1], [-2,0], [-2,1],[-2,2]]

dist = [[10**12 for _ in range(W)] for i in range(H)] #10^3より大きい値

d = deque()
d.append([sy-1, sx-1])
dist[sy-1][sx-1] = 0

#BFS実行部分
while d:
    y,x = d.popleft()
    for dy,dx in walk:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x]:
            dist[new_y][new_x] = dist[y][x]
            d.appendleft([new_y, new_x]) #コスト低い方を優先して取り出すために先頭に追加
    for dy, dx in warp:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x] + 1:
            dist[new_y][new_x] = dist[y][x] + 1
            d.append([new_y, new_x]) #コストが高いので優先順位低い　最高尾に追加

#print(dist)
ans = dist[gy-1][gx-1]
if ans == 10**12:
    ans = -1
print(ans)


### FIXED CODE ###

from collections import deque

H, W = map(int, input().split())
sy, sx = map(int, input().split())
gy, gx = map(int, input().split())
map_list = []
for i in range(H):
    str_input = input()
    map_list.append(list(str_input))

walk = [[1,0], [-1,0], [0,1], [0,-1]] #　下　上　右　左
warp = [[2,-2], [2,-1], [2,0], [2,1],[2,2], [1,-2], [1,-1], [1,1],[1,2], [0,-2], [0,2], [-1,-2],[-1,-1], [-1,1], [-1,2],[-2,-2], [-2,-1], [-2,0], [-2,1],[-2,2]]

dist = [[10**12 for _ in range(W)] for i in range(H)] #10^3より大きい値

d = deque()
d.append([sy-1, sx-1])
dist[sy-1][sx-1] = 0

#BFS実行部分
while d:
    y,x = d.popleft()
    for dy,dx in walk:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x]:
            dist[new_y][new_x] = dist[y][x]
            d.appendleft([new_y, new_x]) #コスト低い方を優先して取り出すために先頭に追加
    for dy, dx in warp:
        new_x = x + dx
        new_y = y + dy
        if 0 <= new_y < H and 0 <= new_x < W and map_list[new_y][new_x] == '.' and dist[new_y][new_x] > dist[y][x] + 1:
            dist[new_y][new_x] = dist[y][x] + 1
            d.append([new_y, new_x]) #コストが高いので優先順位低い　最高尾に追加

#print(dist)
ans = dist[gy-1][gx-1]
if ans == 10**12:
    ans = -1
print(ans)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
l = []
r = []
for i in range(n):
    l += [i+a[i]]
    r += [i-a[i]]
ans = 0
for i in range(n):
    ans+=r.count(l[i])
print(ans)


### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
l = {}
r = {}
for i in range(n):
    p = i+a[i]
    q = i-a[i]
    if p < n:
        if p in l:
            l[p] = l[p]+1
        else:
            l[p] = 1
    if q > 0:
        if q in r:
            r[q] = r[q]+1
        else:
            r[q] = 1
ans = 0
for i in l:
    if i in r:
        ans+= l[i]*r[i]
print(ans)
### BUGGY CODE ###

n = int(input())

for i in range(1, n+1):
  count = 0
  for x in range(1, i):
    for y in range(1, x+1):
      for z in range(1, y+1):
        if (x+y)**2 + (y+z)**2 + (z+x)**2 == 2*i:
          if x == y and y == z and z == x:
          	count += 1
          else:
            count += 3
            
  print(count)

### FIXED CODE ###

import sys
input = sys.stdin.readline

n = int(input())
dp = [0]*(n+1)

for x in range(1, 100):
  for y in range(1, 100):
    for z in range(1, 100):
      tmp = x*x + y*y + z*z + x*y + y*z + z*x
      if tmp <= n:
        dp[tmp] += 1

for i in range(1, n+1):
  print(dp[i])
### BUGGY CODE ###

import collections
n = int(input())
log = []
arr = []
ans = 0
for _ in range(n):
  S = sorted(list(input()))
  if S not in log:
    log.append(S)
    arr.append(1)
  else:
    i = log.index(S)
    ans += arr[i]
    arr[i] += 1
    
print(ans)
  



### FIXED CODE ###


n = int(input())
arr = {}
ans = 0
for _ in range(n):
  S = sorted(list(input()))
  s = ''.join(S)
  if s in arr:
    ans += arr[s]
    arr[s] += 1
  else:
    arr[s] = 1
print(ans)
### BUGGY CODE ###

N,C = map(int,input().split())
XV = [[int(i) for i in input().split()] for _ in range(N)]
ans = 0

Sum_left = [[0]*(N+1) for _ in range(N+1)]

for j in range(N):
    if j == 0:
        Sum_left[0][j+1] = Sum_left[0][j] + XV[j][1] - XV[j][0]
    else:
        Sum_left[0][j+1] = Sum_left[0][j] + XV[j][1] - (XV[j][0] - XV[j-1][0])
    ans = max(ans,Sum_left[0][j+1])

for i in range(N):
    if i == 0:
        Sum_left[i+1][0] = Sum_left[i][0] + XV[-i-1][1] - 2 * (C - XV[-i-1][0])
    else:
        Sum_left[i+1][0] = Sum_left[i][0] + XV[-i-1][1] - 2 * (XV[-i][0] - XV[-i-1][0])

for i in range(1,N):
    if Sum_left[i][0] < 0:
        continue
    for j in range(1,N+1-i):
        if Sum_left[0][j] < 0:
            continue
        Sum_left[i][j] = Sum_left[i][0] + Sum_left[0][j]
        ans = max(ans,Sum_left[i][j])



Sum_right = [[0]*(N+1) for _ in range(N+1)]

for j in range(N):
    if j == 0:
        Sum_right[0][j+1] = Sum_right[0][j] + XV[-1-j][1] - (C-XV[-1-j][0])
    else:
        Sum_right[0][j+1] = Sum_right[0][j] + XV[-1-j][1] - (XV[-j][0] - XV[-1-j][0])
    ans = max(ans,Sum_right[0][j+1])

for i in range(N):
    if i == 0:
        Sum_right[i+1][0] = Sum_right[i][0] + XV[i][1] - 2 * XV[i][0]
    else:
        Sum_right[i+1][0] = Sum_right[i][0] + XV[i][1] - 2 * (XV[i][0] - XV[i-1][0])

for i in range(1,N):
    if Sum_right[i][0] < 0:
        continue
    for j in range(1,N+1-i):
        if Sum_right[0][j] < 0:
            continue
        Sum_right[i][j] = Sum_right[i][0] + Sum_right[0][j]
        ans = max(ans,Sum_right[i][j])

print(ans)

### FIXED CODE ###

N,C = map(int,input().split())
XV = [[0,0]] + [[int(i) for i in input().split()] for _ in range(N)] + [[C,0]]

Sum_left = [0] * (N+1)
Sum_right = [0] * (N+1)
for i in range(N):
    Sum_left[i+1] = Sum_left[i] + XV[i+1][1]
    Sum_right[i+1] = Sum_right[i] + XV[N-i][1]

Sum_right_maxA = [0] * (N+1)
Sum_right_maxB = [0] * (N+1)
for i in range(1,N+1):
    Sum_right_maxA[i] = max(Sum_right_maxA[i-1], Sum_right[i] - 2 * (C - XV[N+1-i][0]))
    Sum_right_maxB[i] = max(Sum_right_maxB[i-1], Sum_right[i] - (C - XV[N+1-i][0]))

ans = 0
for i in range(N+1):
    ans = max(ans, Sum_left[i] + Sum_right_maxA[N-i] - XV[i][0], Sum_left[i] + Sum_right_maxB[N-i] - 2*XV[i][0])
print(ans)
### BUGGY CODE ###

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

ans = 0
for i in range(n):
  if(ls[i] == min(ls[:i+1])):
    ans += 1

print(ans)

### FIXED CODE ###

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

# 初期化
cnt = 1
min = p[0]
# カウント処理
for i in range(1, n):
  if(p[i] <= min):
    cnt += 1
    min = p[i]

print(cnt)
### BUGGY CODE ###

n,w=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print(max(dp[n]))

### FIXED CODE ###

n,w=map(int,input().split())
WV=[list(map(int,input().split())) for i in range(n)]
#WV[i][0]が重さ、WV[i][1]が価値
#配るDP
dp=[[0 for i in range(w+1)] for i in range(n+1)]
#dp[i][j]はi回目(0,n-1)に重さjまで入るmax value
for i in range(n):
    for j in range(w+1):
        if WV[i][0]+j<=w and i <=n-1:
            dp[i+1][j+WV[i][0]]=max(dp[i][j+WV[i][0]], dp[i][j]+WV[i][1])
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
        else:
            dp[i+1][j]=max(dp[i][j],dp[i+1][j])
print(max(dp[n]))
### BUGGY CODE ###

n=int(input())
outp=[]
for i in range(n):
  a=int(input())
  if(a in outp):outp.remove(a)
  else:outp.append(a)
print(len(outp))

### FIXED CODE ###

n=int(input())
outp=set()
for i in range(n):
  a=int(input())
  if(a in outp):outp.remove(a)
  else:outp.add(a)
print(len(outp))
### BUGGY CODE ###

import sys
import itertools
input = sys.stdin.readline
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,w,R = map(int,input().split())
r = list(map(int,input().split()))
d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
for i in range(R):
    r[i] -= 1
d = warshall_floyd(d)

res = float("inf")
for v in itertools.permutations(r,R):
    sumd = 0
    for j in range(1,R):
        sumd += d[v[j-1]][v[j]]
    res = min(res,sumd)
print(res)

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
def warshall_floyd(d):
    #d[i][j]: iからjへの最短距離
    for k in range(n):
        for i in range(n):
            for j in range(n):
                d[i][j] = min(d[i][j],d[i][k] + d[k][j])
    return d

n,w,R = map(int,input().split())
r = list(map(int,input().split()))
d = [[float("inf") for i in range(n)] for i in range(n)] 
#d[u][v] : 辺uvのコスト(存在しないときはinf)
for i in range(w):
    x,y,z = map(int,input().split())
    d[x-1][y-1] = z
    d[y-1][x-1] = z
for i in range(n):
    d[i][i] = 0 #自身のところに行くコストは０
for i in range(R):
    r[i] -= 1
d = warshall_floyd(d)

res = float("inf")
for v in itertools.permutations(r,R):
    sumd = 0
    for j in range(1,R):
        sumd += d[v[j-1]][v[j]]
    res = min(res,sumd)
print(res)
### BUGGY CODE ###

f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  cnt=0
  for p in range(l,r+1,2):
    if f[p] and like[p]:
      cnt+=1
  print(cnt)

### FIXED CODE ###

f=[True]*(10**5+1)
like=[False]*(10**5+1)
f[0]=False
f[1]=False
import math
for i in range(2,len(f)):
  fact=True
  for j in range(2,int(math.sqrt(i))+1):
    if i%j==0:
      fact=False
      break
  
  if fact:
    f[i]=True
    if i*2-1<len(like):
      like[i*2-1]=True
    for p in range(i*2,len(f),i):
      f[p]=False

sums=[0]*(10**5+1)
cur=0
for i in range(len(sums)):
  if f[i] and like[i]:
    sums[i]=cur+1
    cur+=1
  else:
    sums[i]=cur

Q=int(input())
for i in range(Q):
  l,r=map(int,input().split())
  if l>0:
    print(sums[r]-sums[l-1])
  else:
    print(sums[r])
### BUGGY CODE ###

def apc001_c():
    import sys
    n = int(input())

    rt = 0
    print(rt)
    sys.stdout.flush()
    rt_name = str(input())
    if rt_name == 'Vacant': return

    lf = n-1
    print(lf)
    sys.stdout.flush()
    lf_name = str(input())
    if lf_name == 'Vacant': return

    while rt - lf >= 2:
        x = (rt + lf) // 2
        print(x)
        sys.stdout.flush()
        s = str(input())
        if s == rt_name: rt = x
        elif s == lf_name: lf = x
        else: return

if __name__ == '__main__':
    apc001_c()

### FIXED CODE ###

def apc001_c():
    import sys
    n = int(input())

    def ask(x:int):
        print(x)
        sys.stdout.flush()
        res = str(input())
        return res

    lower = 0
    seat_low = ask(lower)
    if seat_low == 'Vacant': return

    upper = n-1
    seat_up = ask(upper)
    if seat_up == 'Vacant': return

    while upper - lower > 1:
        x = (upper + lower) // 2
        s = ask(x)
        if s == 'Vacant': return
        if x % 2 == 0:
            if s == seat_low: lower = x
            else: upper = x
        else:
            if s == seat_up: lower = x
            else: upper = x

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

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

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = [None]*(n1+1)
    R = [None]*(n2+1)
    for i in range(n1):
        L[i] = A[left + i]
    for i in range(n2):
        R[i] = A[mid + i]
    L[n1] = float('inf')
    R[n2] = float('inf')
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

    print(" ".join(map(str, S)))
    print(cnt)


### FIXED CODE ###

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

def merge(A, left, mid, right):
    global cnt
    n1 = mid - left
    n2 = right - mid
    L = A[left:left+n1]
    R = A[mid:mid+n2]
    L.append(float('inf'))
    R.append(float('inf'))
    
    i = 0
    j = 0
    for k in range(left, right):
        cnt += 1
        if L[i] <= R[j]:
            A[k] = L[i]
            i += 1
        else:
            A[k] = R[j]
            j += 1

def mergeSort(A, left, right):
    if left + 1 < right:
        mid = (left + right) // 2
        mergeSort(A, left, mid)
        mergeSort(A, mid, right)
        merge(A, left, mid, right)
    
if __name__ == '__main__':

    n = int(input())
    S = [int(s) for s in input().split(" ")]
    cnt = 0

    mergeSort(S, 0, n)

    print(" ".join(map(str, S)))
    print(cnt)
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
k = 1
p = 0

for i in range(n):
    k = 1
    for j in range(n):
        if i == j:
            pass
        elif a[i] % a[j] == 0:
            k = 0
        else:
            pass

        if j == n - 1:
            if k == 1:
                p += 1

print(p)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
m = max(a)
flag = [True]*(m+1)
c = [0]*(m+1)
b = list(sorted(a))
for i in b:
    x = i + i
    while x <= m:
        flag[x] = False
        x += i
    c[i] += 1
ans = 0
x = 0
l = []
ans = 0
for i in a:
    if flag[i] and c[i] <= 1:
        ans += 1
print(ans)
### BUGGY CODE ###

import sys
input = sys.stdin.readline

def main():
    MOD = 10**9+7
    N,K = map(int,input().split())
     
    def modpow(a,n,mod):
        res = 1
        while n > 0:
            if n & 1:
                res = res * a % mod
            a = a * a % mod
            n >>= 1
        return res
     
    def modinv(a,mod):
        return modpow(a,mod - 2,mod)
 
    def cnk(a,b):
        ret = 1
        for i in range(b):
            ret *= (a-i)
            ret %= MOD
            ret = ret * modinv(i+1,MOD) % MOD
        return ret
     
     
    for i in range(1,K+1):
        if i == 1:
            print(N-K+1)
        else:
            print(cnk(N-K+1,i)*cnk(K-1,i-1)%(MOD))
if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input = sys.stdin.readline

def main():
    N,K = map(int,input().split())
     
    def modpow(a,n,mod):
        res = 1
        while n > 0:
            if n & 1:
                res = res * a % mod
            a = a * a % mod
            n >>= 1
        return res
     
    def modinv(a,mod):
        return modpow(a,mod - 2,mod)
     
    def cnk(a,b):
        MOD = 10**9+7
        ret = 1
        for i in range(b):
            ret *= (a-i)
            ret %= MOD
            ret = ret * modinv(i+1,MOD) % MOD
        return ret
     
     
    for i in range(1,K+1):
        if i > N - K +1:
            print(0)
        elif i == 1:
            print(N-K+1)
        else:
            print(cnk(N-K+1,i)*cnk(K-1,i-1)%(10**9+7))
if __name__ == '__main__':
    main()
### BUGGY CODE ###

import collections
s = input()
mod = 2019
mod_lst = [0]*mod
mod_lst[0] +=1
tmp = 0
t = 1
for i in reversed(s):
    x = int(i) * t
    y = (x % mod + tmp) % mod
    mod_lst[y] += 1
    tmp = y
    t = t*10


count = 0
for j in mod_lst:
    a = j*(j-1)//2
    count += a
print(count)

### FIXED CODE ###

s = input()
mod = 2019
mod_lst = [0]*mod
mod_lst[0] =1
x = 0
t = 1
for i in reversed(s):
    x += int(i) * t
    y = x % mod
    t *= 10
    t %= mod
    mod_lst[y] += 1


count = 0
for j in mod_lst:
    a = j*(j-1)//2
    count += a
print(count)
### BUGGY CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))

check = [False] * N
used = [False] * N


def dfs(u):
    if used[u]:
        return
    used[u] = True
    for w, c in G[u]:
        dfs(w)


def dfs2(u, dest):
    dfs(u)
    check[u] = used[dest]


dist = [INF] * N
for i in range(N):
    used = [False] * N
    dfs2(i, N - 1)

dist[0] = 0
for i in range(N):
    update = False
    for e in range(N):
        if not check[e]:
            continue
        for w, c in G[e]:
            if not check[w]:
                continue
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                update = True

    if not update:
        break
    if i == N - 1:
        print(-1)
        exit()

print(max(0, -dist[N - 1]))




### FIXED CODE ###

import sys
sys.setrecursionlimit((10 ** 6))
input = sys.stdin.readline
N, M, P = map(int, input().split())
INF = float('inf')
G = [[] for i in range(N)]
for i in range(M):
    a, b, c = map(int, input().split())
    a, b, c = a - 1, b - 1, c - P
    G[a].append((b, -c))
dist = [INF] * N
dist[0] = 0
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c

ans = -dist[N - 1]
is_negative = [False] * N
for i in range(N):
    for e in range(N):
        for w, c in G[e]:
            if dist[e] != INF and dist[w] > dist[e] + c:
                dist[w] = dist[e] + c
                is_negative[w] = True

            if is_negative[e]:
                is_negative[w] = True

if is_negative[N - 1]:
    print(-1)
else:
    print(max(ans, 0))
### BUGGY CODE ###

N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)

### FIXED CODE ###

N,M=map(int,input().split())
S=list(input())
S=S[::-1]
ans=[]
P=0
for i in range(1,N+1):
    if P==N:
        break
    for j in range(M+1):
        if P+(M-j)<=N and S[P+(M-j)]=="0":
            ans.append(M-j)
            P+=M-j
            if M-j==0:
                print(-1)
                exit()
            break
ans=ans[::-1]
if 0 in ans:
    print(-1)
else:
    print(*ans)
### BUGGY CODE ###

import sys

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import fractions
from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=None)
def calc_gcd(a, b):
    return fractions.gcd(a, b)

def gcd_list(numbers):
    if len(numbers) == 0: return None
    elif len(numbers) == 1: return numbers[0]
    else: return reduce(calc_gcd, numbers)

left_gcd = [gcd_list(A_li[:i]) for i in range(len(A_li))]
right_gcd = [gcd_list(list(reversed(A_li[i+1:]))) for i in range(len(A_li))]

print(max([right_gcd[0]]+[calc_gcd(left_gcd[i], right_gcd[i]) for i in range(1,len(A_li)-1)]+[left_gcd[N-1]]))


### FIXED CODE ###

import sys
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def II(): return int(sys.stdin.readline())

N = II()
A_li = LI()

import fractions
from functools import reduce
from functools import lru_cache

@lru_cache(maxsize=None)
def calc_gcd(a, b):
    return fractions.gcd(a, b)

def gcd_list(numbers):
    if len(numbers) == 0: return None
    elif len(numbers) == 1: return numbers[0]
    else: return reduce(calc_gcd, numbers)

left_gcd = [None,A_li[0]]
prev_gcd = A_li[0]
for i in range(1,N-1):
    prev_gcd = calc_gcd(prev_gcd, A_li[i])
    left_gcd.append(prev_gcd)

right_gcd = [None, A_li[N-1]]
prev_gcd = A_li[N-1]
for i in range(1,N-1):
    prev_gcd = calc_gcd(prev_gcd, A_li[N-1-i])
    right_gcd.append(prev_gcd)
right_gcd.reverse()

print(max([right_gcd[0]]+[calc_gcd(left_gcd[i], right_gcd[i]) for i in range(1,len(A_li)-1)]+[left_gcd[N-1]]))