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

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

N,D,A = LI()

def check(M):
    M_ = [[a,b] for a,b in M]
    count = 0
    for i in range(N):
        if M_[i][1] > 0:
            bomb = (M_[i][1]+A-1)//A
            count += bomb
            damage = bomb * A
            for j in range(i,N):
                if M_[j][0] <= M_[i][0] + 2*D:
                    M_[j][1] = max(0,M_[j][1] - damage)
                else:
                    break
    return count

def main():
    M = []
    for i in range(N):
        M.append(LI())
    M.sort(key = lambda x: x[0])

    print(check(M))

if __name__ == "__main__":
    main()


### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

def main():
    N,D,A = map(int,readline().split())
    m = map(int,read().split())
    X,H = zip(*sorted(zip(m,m)))
    
    over = [-1]*N
    tmp=0
    for i in range(N):
      while(tmp<N and X[i]+D*2>=X[tmp]):
        tmp += 1
      over[i] = tmp
    reset = [0]*N
    
    ans = 0
    dam = 0
    for i in range(N):
      if i>0:
        reset[i] += reset[i-1]
      hp = H[i]-dam+reset[i]
      if hp > 0:
        bomb = (hp+A-1)//A
        ans += bomb
        dam += bomb * A
        if(over[i]<N):
          reset[over[i]] += bomb * A

    print(ans)

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

a,b,x =map(int,input().split())
c=0

for i in range(a,b+1):
  if i % x ==0:
    c+=1

print(c)

  



### FIXED CODE ###

a,b,x = map(int, input().split())
 
print(b//x-(a-1)//x)
### BUGGY CODE ###

# soundhound2018_summer_qual_d
import networkx as nx
n, m, s, t = map(int, input().split())


Gy = nx.Graph()   # Yen
# Gy.add_nodes_from(range(1, n+1))

Gs = nx.Graph()   # Snuuk
# Gs.add_nodes_from(range(1, n+1))


for _ in range(m):
    u, v, a, b = map(int, input().split())
    Gy.add_edge(u, v, weight=a)
    Gs.add_edge(u, v, weight=b)

shortest_length_from_s = nx.shortest_path_length(Gy, source=s, weight='weight')
shortest_length_to_t = nx.shortest_path_length(Gs, target=t, weight='weight')


dist = [-1]
for i in range(1, n+1):
    dist.append(shortest_length_from_s[i]+shortest_length_to_t[i])
# print(dist)

for i in range(1, n+1):
    print(10**15-min(dist[i:]))


### FIXED CODE ###

import numpy as np
from heapq import heappush, heappop

n, m, s, t = map(int, input().split())
G = [[] for _ in range(n+1)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    G[u].append((v, a, b))
    G[v].append((u, a, b))


def dijkstra(start, mode):
    INF = 10 ** 15
    dist = [INF] * (n+1)
    dist[start] = 0
    q = [(0, start)]
    while q:
        d, v = heappop(q)
        if dist[v] < d:
            continue
        for w, *a in G[v]:
            d1 = d + a[mode]
            if dist[w] > d1:
                dist[w] = d1
                heappush(q, (d1, w))
    return dist


d1 = np.array(dijkstra(s, 0))
d2 = np.array(dijkstra(t, 1))

# print(d1)


d = []
for i in range(n+1):
    d.append(d1[i]+d2[i])


ans = []
B = 10**15
for i in range(n):
    B = min(B, d[n-i])
    ans.append(B)
ans = ans[::-1]

for i in range(n):
    print(10**15-ans[i])
### BUGGY CODE ###

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

id_range = range(N + 1)

for m in range(M):
  L, R = map(int, input().split())
  id_range = set(id_range) & set(range(L, R + 1, 1))
  
print(len(set(range(1, N + 1, 1)) & id_range))

### FIXED CODE ###

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

L = list(range(M))
R = list(range(M))

for m in range(M):
  L[m], R[m] = map(int, input().split())

L_max = max(L)
R_min = min(R)

print(R_min - L_max + 1 if L_max <= R_min else 0)
### BUGGY CODE ###

L = int(input())
V = [0]*10**7
for x in range(1,10**7):
    V[x] = (x*0.0001)**2 *(L-2*(x*0.0001))
print(max(V))

### FIXED CODE ###

L = int(input())
x = L/3

 
print(x**2 *(L-2*x))
### BUGGY CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]+["end"]
TT=[j*t for j in range(M)]+["end"]
p,q=0,0
ans=N*s
for k in range(N*s):
    if SS[p]==k:
        if TT[q]==k:
            if S[p]!=T[q]:
                ans=-1
        p+=1
    if TT[q]==k:
        q+=1
print(ans)

### FIXED CODE ###

from fractions import gcd
N,M=map(int,input().split())
S=input()
T=input()
s=(M//gcd(N,M))
t=(N//gcd(N,M))
SS=[i*s for i in range(N)]
TT=[j*t for j in range(M)]
p,q=0,0
ans=N*s
while True:
    if SS[p]==TT[q]:
        if S[p]!=T[q]:ans=-1
        p+=1
        q+=1
    elif SS[p]>TT[q]:
        q+=1
    else:
        p+=1
    if p==N or q==M:
        break
print(ans)
### BUGGY CODE ###

N, C = map(int, input().split())
x = []
v = []
for i in range(N):
    x_i, v_i = map(int, input().split())
    x.append(x_i)
    v.append(v_i)

v_1 = [sum(v[:i]) for i in range(1, N+1)]
v_n = [sum(v[i:]) for i in range(N-1, -1, -1)]

c = 0
for i in range(N):
    c_t = v_1[i] - x[i]
    if c_t > c:
        c = c_t
    for j in range(i+1, N):
        c_t = v_1[i] + v_n[N-j-1] - (2 * x[i] + (C - x[j]))
        if c_t > c:
            c = c_t
for i in range(N-1, -1, -1):
    c_t = v_n[N-i-1] - (C - x[i])
    if c_t > c:
        c = c_t
    for j in range(i-1, -1, -1):
        c_t = v_1[j] + v_n[N-i-1] - (x[j] + 2*(C - x[i]))
        if c_t > c:
            c = c_t

print(c)

### FIXED CODE ###

N, C = map(int, input().split())
x = [0]
v = [0]
for i in range(N):
    x_i, v_i = map(int, input().split())
    x.append(x_i)
    v.append(v_i)
fw = [0] * (N+1)
bw = [0] * (N+1)
for i in range(N):
    fw[i+1] = fw[i] + v[i+1]
    bw[i+1] = bw[i] + v[N-i]

for i in range(N):
    fw[i+1] -= x[i+1]
    bw[i+1] -= C - x[N-i]
m_fw = [0] * (N+1)
m_bw = [0] * (N+1)
for i in range(N):
    m_fw[i+1] = max(m_fw[i], fw[i+1])
    m_bw[i+1] = max(m_bw[i], bw[i+1])
c = 0
for i in range(N+1):
    if i == 0:
        l = 0
    else:
        l = C - x[-i]
    c = max(c, bw[i]+m_fw[N-i]-l, fw[i]+m_bw[N-i]-x[i])
print(c)
### BUGGY CODE ###

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

dp=[[0]*s for _ in range(n)]    

for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=2**i%mod
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
            
print(dp[n-1][s-1]%mod)

### FIXED CODE ###

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

dp=[[0]*s for _ in range(n)]    
tmp=1
for i in range(n):
    if a[i]<=s:
        dp[i][a[i]-1]=tmp
    for j in range(s):
        if i>0:
            dp[i][j]+=dp[i-1][j]*2
            dp[i][j]%=mod
            if j+a[i]<s:
                dp[i][j+a[i]]+=dp[i-1][j]
                dp[i][j+a[i]]%=mod
    tmp*=2
    tmp%=mod
            
print(dp[n-1][s-1])
### BUGGY CODE ###

mod=1000000007
n,k=map(int, input().split())
lst=list(map(int, input().split()))
lst=sorted(lst)
p=1
if lst[-1]==0 and k%2!=0:
    print(0)
elif lst[-1]<0 and k%2!=0:
    for i in range(n-1,n-k-1,-1):
        #print(p)
        p*=lst[i]
    #print(p)
    print(p%mod)
else:
    j=n-1
    if k%2!=0:
        p*=lst[j]
        k-=1
        j-=1
    k=k//2
    i=0
    for x in range(k):
        if lst[i]*lst[i+1]>lst[j]*lst[j-1]:
            p*=(lst[i]*lst[i+1])
            i+=2
        else:
            p*=(lst[j]*lst[j-1])
            j-=2
    #print(p)
    print(p%mod)

### FIXED CODE ###

mod=1000000007
n,k=map(int, input().split())
lst=list(map(int, input().split()))
lst=sorted(lst)
p=1
if lst[-1]==0 and k%2!=0:
    print(0)
elif lst[-1]<0 and k%2!=0:
    for i in range(n-1,n-k-1,-1):
        #print(p)
        p=(p%mod*lst[i]%mod)%mod
    #print(p)
    print(p%mod)
else:
    j=n-1
    if k%2!=0:
        p*=lst[j]
        k-=1
        j-=1
    k=k//2
    i=0
    for x in range(k):
        if lst[i]*lst[i+1]>lst[j]*lst[j-1]:
            p=(p%mod*lst[i]%mod*lst[i+1]%mod)%mod
            i+=2
        else:
            p=(p%mod*lst[j]%mod*lst[j-1]%mod)%mod
            j-=2
    #print(p)
    print(p%mod)
### BUGGY CODE ###

a,b,x = map(int,input().split())
answer = 0
flag = 0
for i in range(a,b+1) :
    if i % x == 0 :
        answer += 1
        p = i
        flag += 1
        break
if flag == 1 :
    q = b-p
else :
    q = b-a
answer += q//x
print(answer)


### FIXED CODE ###

a,b,x = map(int,input().split())
B = b//x
A = (a-1)//x
print(B-A)
### BUGGY CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for _ in range(q)]
for i in range(n):
  pt = k
  pl = a.count(i+1)
  if pl > 0:
    pt = pt - q + pl
  else:
    pt -= q
  if pt > 0:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

n,k,q = map(int,input().split())
a = [int(input()) for _ in range(q)]
pt = [k-q for _ in range(n)]
for i in a:
  pt[i-1] += 1
for i in pt:
  if i > 0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import bisect
n = int(input())
a = [int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  if a[i] <= min(tmp):
    tmp.insert(0,a[i])
  else:
    index=bisect.bisect_left(tmp,a[i])
    tmp[index-1] =a[i]
print(len(tmp))

### FIXED CODE ###

import bisect
n = int(input())
a = [- int(input()) for i in range(n)]
tmp = [a[0]]
for i in range(1,n):
  idx=bisect.bisect_right(tmp,a[i])
  if idx==len(tmp):
    tmp.append(a[i])
  else:
    tmp[idx] =a[i]
print(len(tmp))
### BUGGY CODE ###

import sys

def IL():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = IL()
	h_i = IL()
	dp = [0] * N
	dp[0] = 0
	for i in range(1, N):
		dp[i] = min([abs(h_i[i] - h_i[i-j]) + dp[i-j] for j in range(1, min(i, K)+1)])
		
	print(dp[-1])


if __name__ == "__main__":
	main()

### FIXED CODE ###

import sys
import numpy as np

def LI():
	return list(map(int, sys.stdin.readline().rstrip().split()))

def main():
	N, K = LI()
	h_i = np.array(LI())
	dp = np.full(N, 10**10, dtype=int)
	dp[0] = 0
	for i in range(1, N):
		dp[i:i+K] = np.fmin(dp[i:i+K], dp[i-1] + np.abs(h_i[i:i+K] - h_i[i-1]))
		
	return dp[-1]


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

n,a,b=map(int,input().split())
count=0

if a==0:
  print('0')
  exit()
else:
  while n>=a:
    n=n-a
    count+=1
    if n>=b:
      n=n-b
    elif n<b:
      n=0

ball=a*count+n

print(ball)

### FIXED CODE ###

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

kosuu=n//(a+b)
amari=n%(a+b)

if a>amari:
  print(a*kosuu+amari)
else:
  print(a*kosuu+a)
### BUGGY CODE ###

R, C, K = map(int, input().split())

I = [[0 for j in range(C)] for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp = [[[0 for k in range(4)]
       for j in range(C)] for i in range(R)]
for i in range(R):
    for j in range(C):
        for k in range(4):
            if i < R-1:
                if k <= 2:
                    dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k]+I[i][j])
                else:
                    dp[i+1][j][0] = max(dp[i+1][j][0], dp[i][j][k])
            if j < C-1:
                if k <= 2:
                    dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])
                    dp[i][j+1][k+1] = max(dp[i][j+1][k+1], dp[i][j][k]+I[i][j])
                else:
                    dp[i][j+1][k] = max(dp[i][j+1][k], dp[i][j][k])


# print(*dp, sep='\n')

ans = 0
for k in range(4):
    if k <= 2:
        ans = max(ans, dp[R-1][C-1][k]+I[R-1][C-1])
    ans = max(ans, dp[R-1][C-1][k])
print(ans)


### FIXED CODE ###

import sys
input = sys.stdin.readline

R, C, K = map(int, input().split())

I = [[0]*C for i in range(R)]
for _ in range(K):
    r, c, v = map(int, input().split())
    I[r-1][c-1] = v   # 0-indexed

dp0 = [[0 for j in range(C+1)] for i in range(R+1)]
dp1 = [[0 for j in range(C+1)] for i in range(R+1)]
dp2 = [[0 for j in range(C+1)] for i in range(R+1)]
dp3 = [[0 for j in range(C+1)] for i in range(R+1)]
for i in range(R):
    for j in range(C):
        dp3[i][j] = max(dp3[i][j], dp2[i][j]+I[i][j])
        dp2[i][j] = max(dp2[i][j], dp1[i][j]+I[i][j])
        dp1[i][j] = max(dp1[i][j], dp0[i][j]+I[i][j])
        dp0[i+1][j] = max(dp0[i+1][j], dp0[i][j], dp1[i]
                          [j], dp2[i][j], dp3[i][j])
        dp0[i][j+1] = max(dp0[i][j+1], dp0[i][j])
        dp1[i][j+1] = max(dp1[i][j+1], dp1[i][j])
        dp2[i][j+1] = max(dp2[i][j+1], dp2[i][j])
        dp3[i][j+1] = max(dp3[i][j+1], dp3[i][j])


# print(*dp, sep=' \n')

ans = max(dp0[R-1][C-1], dp1[R-1][C-1], dp2[R-1][C-1], dp3[R-1][C-1])
print(ans)
### BUGGY CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1].T

def drop(S):
    for i in range(W):
        col = S[i]
        S[i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:-1] == S[1:])
    for i in range(1,W):
        x[i] = x[i-1] * equal[i-1] + 1
    for i in range(W-2,-1,-1):
        x[i][equal[i]] = x[i+1][equal[i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(j):
    T = S.copy()
    T[j,0] = 0
    return simulate(T,0)

answer = 0
for i in range(H):
    x = max(calc(j) for j in range(W))
    if answer < x:
        answer = x
    H -= 1
    S = S[:,1:]
print(answer)

### FIXED CODE ###

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

import time
start = time.time()

import numpy as np

H,W,K = map(int,readline().split())
S = np.array([list(line.rstrip()) for line in readlines()]).astype(np.int8) - ord('0')

# 下から上の順に
S = S[::-1].T

def drop(S):
    for i in range(W):
        col = S[i]
        S[i] = drop_col(col)

def drop_col(col):
    x = np.zeros(H,np.int8)
    nonzero = col[col != 0]
    x[:len(nonzero)] = nonzero
    return x

def cnt_connection(S):
    # 横につながっている個数
    x = np.ones_like(S)
    equal = (S[:-1] == S[1:])
    for i in range(1,W):
        x[i] = x[i-1] * equal[i-1] + 1
    for i in range(W-2,-1,-1):
        x[i][equal[i]] = x[i+1][equal[i]]
    return x

def simulate(S,turn):
    # 落とす -> 消去、で1セット
    drop(S)
    conn = cnt_connection(S)
    remove = (conn >= K)
    before = S.sum()
    S *= (~remove)
    after = S.sum()
    if before == after:
        # 消えなかった
        return 0
    else:
        x = simulate(S,turn+1)
        return x + ((before - after) << turn)

def calc(j):
    T = S.copy()
    T[j,0] = 0
    return simulate(T,0)

answer = 0
for i in range(H):
    x = max(calc(j) for j in range(W))
    if answer < x:
        answer = x
    H -= 1
    S = S[:,1:]
    if time.time() - start > 0.9:
        break
print(answer)
### BUGGY CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
np = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  for j in range(13):
    np[j] = 0
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)


### FIXED CODE ###

s = ''.join(reversed(input()))
multiplier = 1
divisor = 10 ** 9 + 7
p = [0 for i in range(13)]
if s[0] != '?':
  p[int(s[0])] = 1
else:
  for j in range(10):
    p[j] = 1
for i in range(1, len(s)):
  multiplier = (10 * multiplier) % 13
  np = [0 for j in range(13)]
  if s[i] != '?':
    r = int(s[i]) * multiplier
    for j in range(13):
      np[(j + r) % 13] = p[j]
  else:
    for j in range(10):
      r = j * multiplier
      for k in range(13):
        np[(k + r) % 13] += p[k]
  for j in range(13):
    p[j] = np[j] % divisor
print(p[5] % divisor)
### BUGGY CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())

is_prime = [0] * (10**6+1)
is_prime[0] = False
is_prime[1] = False

for a in range(2,10**6+1):
    if is_prime[a]:
        for v in range(a*2,10**6+1,a):
            is_prime[v] = False
# def yaku(m):
#     ans = []
#     i = 1
#     while i*i <= m:
#         if m % i == 0:
#             j = m // i
#             ans.append(i)
#             if j != i:
#                 ans.append(j)
#         i += 1
#     ans = sorted(ans)
#     return ans
n = I()
ans = 0
for c in range(1,n):
    nc = n-c
    if nc == 1:
        ans += 1
        continue
    else:
        ans += 2
    i = 2
    while i*i <= nc:
        if nc%i == 0:
            if i*i == nc:
                ans += 1
            else:
                ans += 2
        i += 1
print(ans)


### FIXED CODE ###

#from statistics import median
#import collections
#aa = collections.Counter(a) # list to list || .most_common(2)で最大の2個とりだせるお a[0][0]
from math import gcd
from itertools import combinations,permutations,accumulate, product # (string,3) 3回
#from collections import deque
from collections import deque,defaultdict,Counter
import decimal
import re
import math
import bisect
import heapq
#
#
#
# pythonで無理なときは、pypyでやると正解するかも！！
#
#
# my_round_int = lambda x:np.round((x*2 + 1)//2)
# 四捨五入g
#
# インデックス系
# int min_y = max(0, i - 2), max_y = min(h - 1, i + 2);
# int min_x = max(0, j - 2), max_x = min(w - 1, j + 2);
#
#
import sys
sys.setrecursionlimit(10000000)
mod = 10**9 + 7
#mod = 9982443453
#mod = 998244353
INF = float('inf')
from sys import stdin
readline = stdin.readline
def readInts():
  return list(map(int,readline().split()))
def readTuples():
    return tuple(map(int,readline().split()))
def I():
    return int(readline())

is_prime = [1] * (10**6+1)

for a in range(2,10**6+1):
        for v in range(a,10**6+1,a):
            is_prime[v] += 1
# print(is_prime[:10])

n = I()
ans = 0
for c in range(1,n):
    nc = n-c
    ans += is_prime[nc]
print(ans)
### BUGGY CODE ###

from collections import defaultdict
import heapq


def dijkstra(N, adj_nodes, A, from_node, to_node):
    INF = 10**12
    dist = [INF for _ in range(N)]
    dist[from_node] = 0
    frontier = [(0, from_node)]
    while len(frontier) > 0:
        d, node = heapq.heappop(frontier)
        for next_node in adj_nodes[node]:
            next_d = dist[node] + A[node][next_node]
            if dist[next_node] > next_d:
                dist[next_node] = next_d
                heapq.heappush(frontier, (next_d, next_node))
    return dist[to_node]


def main():
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    edges = list()
    for i in range(N):
        for j in range(i + 1, N):
            edges.append((A[i][j], i, j))  # (cost, from, to)
    edges.sort(key=lambda e: e[0])
    adj_nodes = defaultdict(list)
    ans = 0
    for edge in edges:
        cost, from_node, to_node = edge
        d = dijkstra(N, adj_nodes, A, from_node, to_node)
        if d < cost:
            print(-1)
            return
        elif d > cost:
            ans += cost
            adj_nodes[from_node].append(to_node)
            adj_nodes[to_node].append(from_node)
    print(ans)


if __name__ == '__main__':
    main()

### FIXED CODE ###

from scipy.sparse.csgraph import floyd_warshall
import numpy as np


def main():
    INF = 10**12
    N = int(input())
    A = [list(map(int, input().split(' '))) for _ in range(N)]
    wf = floyd_warshall(A)
    for i in range(N):
        A[i][i] = INF
        wf[i][i] = INF
    ans = 0
    for i in range(N):
        for j in range(N):
            if A[i][j] != wf[i][j]:
                print(-1)
                return
            if wf[i][j] < np.min(wf[i] + wf[j]):
                ans += wf[i][j]
    print(int(ans // 2))


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

N = int(input())
A = list(map(int, input().split()))
A.sort(reverse=True)
tmp = 1
beki = []
while tmp < 2*10**9:
	tmp *= 2
	beki.append(tmp)

ans = 0
i = 0
while i < len(A)-1:
	j = i+1
	while j < len(A):
		# print(i, j, len(A), A[i], A[j])
		if A[i]+A[j] in beki:
			ans += 1
			A.pop(j)
			i += 1
			j = i+1
		else:
			j += 1
	i += 1

print(ans)


### FIXED CODE ###

import bisect

def binum(num):
	number_len = len(bin(num))-2
	f = 2**number_len -1
	return (num^f)+1

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

while len(A) > 0:
	k = A.pop()
	if len(A) == 0:
		break
	if int(k) != k:
		continue
	x = binum(k)
	if x > A[-1]:
		continue
	if A[bisect.bisect_left(A,x)] == x:
		A[bisect.bisect_left(A,x)] -= 0.5
		cnt += 1

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

import numpy as np

N, M = map(int, input().split())
a = np.array(list(map(int, input().split())))

for _ in range(M):
    a[a.argmax()] //= 2
print(sum(a))

### FIXED CODE ###

import heapq

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

q = []
for i in range(N):
    # 最も大きい値を取り出して1/2したいので、ここで反転させておき、最終的に足す時に戻す
    heapq.heappush(q, -a[i])
for i in range(M):
    l = heapq.heappop(q)
    heapq.heappush(q, -(-l//2))
print(-sum(q))
### BUGGY CODE ###

def main():
    s=[0 if i == "B" else 1 for i in input()]
    l=len(s)
    count = 0
    while True:
        p = count
        for i in range(l-1):
            if s[i] == 0 and s[i+1] == 1:
                s[i] = 1
                s[i+1] = 0
                count += 1
        if p == count:
            break
    print(count)
    
if __name__ == "__main__":
    main()

### FIXED CODE ###

def main():
    s=input()
    l=0
    man=0
    for i,v in enumerate(s):
        if v == "W":
            man += i-l
            l += 1
    print(man)
    
if __name__ == "__main__":
    main()
### BUGGY CODE ###

S = input()
ans = [1]*len(S)
for i in range(len(S)):
    if S[i] == "L":
        if S[i-1] == "R":
            continue
        else:
            ans[i] = 0
            j = 1
            count = 1
            while True:
                if S[i-j] == "R":
                    break
                j += 1
                count += 1
            if count%2 == 0:
                ans[i-j] += 1
            else:
                ans[i-j+1] += 1
    else:
        if S[i+1] == "L":
            continue
        else:
            ans[i] = 0
            j = 1
            count = 1
            while True:
                if S[i+j] == "L":
                    break
                j += 1
                count += 1
            if count%2 == 0:
                ans[i+j] += 1
            else:
                ans[i+j-1] += 1
print(*ans,sep=" ")

### FIXED CODE ###

S = input()
def runlength(str):
    res = []
    data,count = str[0],1
    for i in range(1,len(str)):
        if str[i] == data:
            count += 1
        else:
            res.append((data,count))
            data,count = str[i],1
    res.append((data,count))
    return res
ans = [0]*len(S)
ind = -1
for rl in runlength(S):
    if rl[0] == "R":
        ind += rl[1]
        ans[ind] += rl[1] - rl[1]//2
        ans[ind+1] += rl[1]//2
    else:
        ans[ind] += rl[1]//2
        ans[ind+1] += rl[1] - rl[1]//2
        ind += rl[1]
print(*ans)