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

n, m, k = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
cd = [list(map(int, input().split())) for _ in range(k)]

class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    elif(self.rnk[x] > self.rnk[y]):
      self.root[y] = x
    else:
      self.root[x] = y
      if(self.rnk[x] == self.rnk[y]):
        self.rnk[y] += 1
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x):
    return -self.root[self.Find_Root(x)]

ans = []
uf = UnionFind(n+1)
for a, b in ab:
  uf.Unite(a, b)

adlist = [set() for i in range(n+1)]
for a, b in ab:
  adlist[a].add(b)
  adlist[b].add(a)
for i in range(1, n+1):
  adlist[i].add(i)
for c, d in cd:
  adlist[c].add(d)
  adlist[d].add(c)

tmp = set([i for i in range(1, n+1)])

for i in range(1, n+1):
  adlist[i] = tmp - adlist[i] 


for i in range(1, n+1):
  if len(adlist[i]) != 0:
    a = 0 
    for j in adlist[i]:
      if uf.isSameGroup(i, j):
        a += 1 

    ans += [a]
  else:
    ans += [0]

ans = list(map(str, ans))
print(' '.join(ans))

### FIXED CODE ###

import sys
input = sys.stdin.readline
N, M, K = map(int, input().split())
class UnionFind():
  def __init__(self, n):
    self.n = n
    self.root = [-1]*(n+1)
    self.rnk = [0]*(n+1)
  def Find_Root(self, x):
    if(self.root[x] < 0):
      return x
    else:
      self.root[x] = self.Find_Root(self.root[x])
      return self.root[x]
  def Unite(self, x, y):
    x = self.Find_Root(x)
    y = self.Find_Root(y)
    if(x == y):
      return 
    if self.root[x] > self.root[y]:
      x, y = y, x
    self.root[x] += self.root[y]
    self.root[y] = x 
  def isSameGroup(self, x, y):
    return self.Find_Root(x) == self.Find_Root(y)
  def Count(self, x): # xが属するグループのサイズを返す
    return -self.root[self.Find_Root(x)]
  def Members(self, x): # xが属するグループに属する要素をリストで返す
    return [i for i in range(self.n) if self.Find_Root(i)==self.Find_Root(x)]
  def Roots(self): # 全ての根の要素をリストで返す
    return [i for i, x in enumerate(self.root) if x < 0]
  def Group_Count(self): # グループの数を返す
    return len(self.Roots())

uf = UnionFind(N+1)
roots = {i:0 for i in range(1, N+1)}
each_root = [0]*(N+1)
ad = [0]*(N+1)

for _ in range(M):
  a, b = map(int, input().split())
  uf.Unite(a, b)
  ad[a] += 1
  ad[b] += 1

for i in range(1, N+1):
  r = uf.Find_Root(i)
  roots[r] += 1
  each_root[i] = r

for _ in range(K):
  c, d = map(int, input().split())
  if each_root[c] == each_root[d]:
    ad[c] += 1
    ad[d] += 1

for i in range(1, N+1):
  print(roots[each_root[i]]-ad[i]-1, end=" ")
### BUGGY CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


K = int(input())

if K % 2 == 0:
    print(-1)
else:
    ans = 1
    num = 7
    while True:
        # print(f'num = {num}')
        # print(f'ans = {ans}')
        if num % K == 0:
            break
        num *= 10
        num += 7
        ans += 1
    print(ans)


# s[i] = s[i-1] * 10 + 7
# s[0] = 0

# min_num = 7
# max_num = 7,777,777
# left = min_num
# right = max_num

# s[i] を定数時間で計算できれば、i=0~100000の間で二分探索すれば良い?


### FIXED CODE ###

#!/usr/bin/env python3

from pprint import pprint
from collections import deque, defaultdict
import itertools
import math
import sys

sys.setrecursionlimit(10 ** 6)
INF = float('inf')


K = int(input())

# 解法1
# 数列 s は、s[1] = 7, s[i+1] = s[i] * 10 + 7 の漸化式で与えられる
# 特性方程式 α = α * 10 + 7 を考えると、α = -7/9 より、
# s[i+1] + 7/9 = 10 * (s[i] + 7/9) となる
# つまり、s[i] + 7/9 = 10^(i-1) * (7 + 7/9)
# <=> s[i] = 10^(i-1) * 70/9 - 7/9
# <=> s[i] = 7/9 * (10^i - 1)
# よって、7/9 * (10^i - 1) % K == 0 となるような最小の正の整数 i を求めれば良いことになる

# 解法2
# s[i] = s[i-1] * 10 + 7 より、s[i] % K = (s[i-1] * 10 + 7) % K
# a[i] = s[i] % K とすると、# a[i] = a[i-1] % K だから、
# a[i] を順番に計算し、a[i] == 0 となる最初の i を出力しても OK

if K % 2 == 0 or K % 5 == 0:
    print(-1)
else:
    i = 1
    a_i = 0
    while True:
        a_i = (a_i * 10 + 7) % K
        if a_i == 0:
            print(i)
            break
        i += 1
### BUGGY CODE ###

N,M=map(int,input().split())
cakes=[None]*N
for i in range(N):
  x,y,z=map(int,input().split())
  cakes[i]=[x,y,z]
  
# x,y,zをそれぞれマイナスに伸ばすかプラスに伸ばすか、2*3通りをすべて試す。
ans=0
for i in range(2**3):
  plus_or_minus=[1]*3
  for j in range(3):
    if (i>>j)&1:
      plus_or_minus[j]=1
    else:
      plus_or_minus[j]=-1
  # 買った個数に対して、プラスマイナスへの伸びが最も大きい買い方を保持
  dp=[None for j in range(M+1)]
  dp[0]=[0,0,0]
  
  for c in range(len(cakes)):
    for j in range(c+1,-1,-1):
      if j<len(dp)-1 and dp[j]!=None:
        if dp[j+1]==None:
          dp[j+1]=[None]*3
          dp[j+1][0]=dp[j][0]+cakes[c][0]
          dp[j+1][1]=dp[j][1]+cakes[c][1]
          dp[j+1][2]=dp[j][2]+cakes[c][2]
        else:
          diff=0
          for k in range(3):
            diff+=((dp[j][k]+cakes[c][k])*plus_or_minus[k])-(dp[j+1][k]*plus_or_minus[k])
          if diff>0:
            dp[j+1][0]=dp[j][0]+cakes[c][0]
            dp[j+1][1]=dp[j][1]+cakes[c][1]
            dp[j+1][2]=dp[j][2]+cakes[c][2]
  if abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])>ans:
    ans=abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])

print(ans)

### FIXED CODE ###

N,M=map(int,input().split())
cakes=[None]*N
for i in range(N):
  x,y,z=map(int,input().split())
  cakes[i]=[x,y,z]
  
# x,y,zをそれぞれマイナスに伸ばすかプラスに伸ばすか、2*3通りをすべて試す。
ans=0
for i in range(2**3):
  plus_or_minus=[1]*3
  for j in range(3):
    if (i>>j)&1:
      plus_or_minus[j]=1
    else:
      plus_or_minus[j]=-1
  # 買った個数に対して、プラスマイナスへの伸びが最も大きい買い方を保持
  dp=[None for j in range(M+1)]
  dp[0]=[0,0,0]
  
  for c in range(len(cakes)):
    for j in range(c+1,-1,-1):
      if j<len(dp)-1 and dp[j]!=None:
        if dp[j+1]==None:
          dp[j+1]=[None]*3
          dp[j+1][0]=dp[j][0]+cakes[c][0]
          dp[j+1][1]=dp[j][1]+cakes[c][1]
          dp[j+1][2]=dp[j][2]+cakes[c][2]
        else:
          diff=0
          for k in range(3):
            diff+=((dp[j][k]+cakes[c][k])*plus_or_minus[k])-(dp[j+1][k]*plus_or_minus[k])
          if diff>0:
            dp[j+1][0]=dp[j][0]+cakes[c][0]
            dp[j+1][1]=dp[j][1]+cakes[c][1]
            dp[j+1][2]=dp[j][2]+cakes[c][2]
  if abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])>ans:
    ans=abs(dp[-1][0])+abs(dp[-1][1])+abs(dp[-1][2])

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

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]
cum = []
for i in range(N+1):
    cum.append(S[:i].count('AC'))
for l, r in LR:
    print(cum[r] - cum[l])

### FIXED CODE ###

N, Q = map(int, input().split())
S = input()
LR = [list(map(int, input().split())) for _ in range(Q)]
#dp[i]はi番目までの文字で'AC'がいくつあるか
dp = [0] * (N+1)
for i in range(1, N):
    if S[i-1] == 'A' and S[i] == 'C':
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]

for l, r in LR:
    print(dp[r-1] - dp[l-1])
### BUGGY CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq

n = int(input())
a = []
b = []
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a.append([i,xy[0]])
    b.append([i,xy[1]])

a.sort(key=lambda x: x[1])
b.sort(key=lambda x: x[1])
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for i, [j, x] in enumerate(a[:-1]):
    adj[j].append([a[i+1][1]-x, a[i+1][0]])
    adj[a[i+1][0]].append([a[i+1][1]-x, j])
for i, [j, y] in enumerate(b[:-1]):
    adj[j].append([b[i+1][1]-y, b[i+1][0]])
    adj[b[i+1][0]].append([b[i+1][1]-y, j])

#print(adj)
    
# Prim's algorithm
d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
while h:
    cost, node = heapq.heappop(h)
    if visited[node] != True and cost < d[node]:
        d[node] = cost
        visited[node] = True
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]] == True:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(sum(d))
        


### FIXED CODE ###

# -*- coding: utf-8 -*-
"""
Created on Thu Sep 20 21:40:30 2018
ABC065D
@author: maezawa
i=0...n (0-origin)
"""
import heapq
import sys
input = sys.stdin.readline

n = int(input())
a = [[] for _ in range(n)]
b = [[] for _ in range(n)]
for i in range(n): # i is a name of the city (0-origin)
    xy = list(map(int, input().split()))
    a[i]=[xy[0],i]
    b[i]=[xy[1],i]

a.sort()
b.sort()
#print(a) 
#print(b)

# making adj list
adj = [[] for _ in range(n)]
for [x0, j0], [x1, j1]  in zip(a, a[1:]):
    adj[j0].append([x1-x0, j1])
    adj[j1].append([x1-x0, j0])
for [y0, j0], [y1, j1] in zip(b, b[1:]):
    adj[j0].append([y1-y0, j1])
    adj[j1].append([y1-y0, j0])

#print(adj)
    
# Prim's algorithm
#d = [10**10]*n
visited = [False]*n
h = []
s = 0
heapq.heappush(h, [0, s])
cnt = 0
totalcost = 0 
while h:
    cost, node = heapq.heappop(h)
    #if visited[node] != True and cost < d[node]:
    if visited[node] != True:        
        #d[node] = cost
        visited[node] = True
        totalcost += cost
        cnt += 1
        if cnt == n:
            break
        for edge in adj[node]:
            if visited[edge[1]]:
                continue
            heapq.heappush(h, edge)
            
#print(d)
print(totalcost)
### BUGGY CODE ###


def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp%i==0:
            cnt=0
            while temp%i==0:
                cnt+=1
                temp //= i
            arr.append([i, cnt])
    if temp!=1:
        arr.append([temp, 1])
    if arr==[]:
        arr.append([n, 1])
    return arr

n=int(input())
F = [1]
for i, j in factorization(n):
    for _ in range(j):
        F.append(i)
import itertools
ans = 9999999999999
for flags in itertools.product([0,1], repeat=len(F)):
    a = 1
    b = 1
    for i in range(len(F)):
        if flags[i]:
            a *= F[i]
        else:
            b *= F[i]
    tmp = (a-1) + (b-1)
    if tmp < ans:
        ans = tmp
print(ans)

### FIXED CODE ###

n=int(input())
ran = int(n**0.5) + 1
ans = 999999999999
for i in range(1, ran):
    j = n // i
    if j != int(n / i):
        continue
    if i * j != n:
        continue
    tmp = i + j - 2
    if tmp < ans:
        ans = tmp
print(ans)
### BUGGY CODE ###

n = int( raw_input( ) )
eles = []
for i in range( n ):
	op = raw_input( ).split( " " )
	if "insert" == op[0]:
		eles.insert( 0, op[1] )
	elif "delete" == op[0]:
		for i,val in enumerate( eles ):
			if op[1] == val:
				eles.pop( i )
				break
	elif "deleteFirst" == op[0] :
		eles.pop( 0 )
	elif "deleteLast" == op[0]:
		eles.pop( )

print( " ".join( eles ) )

### FIXED CODE ###

import sys
from collections import deque

n = int( sys.stdin.readline( ) )
que = deque( )
lines = sys.stdin.readlines()
for line in lines:
	op = line.rstrip().split( " " )
	if "insert" == op[0]:
		que.appendleft( op[1] )
	elif "delete" == op[0]:
		if op[1] in que:
			que.remove( op[1] )
	elif "deleteFirst" == op[0] :
		que.popleft( )
	elif "deleteLast" == op[0]:
		que.pop( )


print( " ".join( que ) )
### BUGGY CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
from fractions import gcd
n = int(input())
# n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7


def lcm(x, y):
    return (x * y) // gcd(x, y)

l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l // a[i]

ans %= mod
print(ans)

### FIXED CODE ###

# import bisect
# import heapq
# from copy import deepcopy
# from collections import deque
# from collections import Counter
# from itertools import accumulate
# from itertools import permutations
# import numpy as np
# import math
from fractions import gcd
n = int(input())
# n, k = map(int, input().split())
a = list(map(int, input().split()))
mod = 10**9 + 7


def lcm(x, y):
    return (x * y) // gcd(x, y)

l = 1
for i in range(n):
    l = lcm(l,a[i])

ans = 0
for i in range(n):
    ans += l // a[i]

ans %= mod
print(ans)
### BUGGY CODE ###

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

rl = []

for i in range(k-1,n):
  r = 1
  for j in range(k):
    r *= a[i-j]
    j += 1
  rl.append(r)
  i += 1

for m in range(n-k):
  if rl[m+1] > rl[m]:
    print('Yes')
  else:
    print('No')

### FIXED CODE ###

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

for i in range(k,n):
  if a[i] > a[i-k]:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import queue

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

d = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)

c = [0]*n

for i in range(q):
    p,x = map(int,input().split())
    c[p-1]+=x

ans = [0]*n
visited = [0]*n

que = queue.Queue()

que.put(0)
visited[0]=1
ans[0]+=c[0]

while not que.empty():
    x = que.get()
    for y in d[x]:
        if visited[y]==1:
            continue
        else:
            ans[y]+=ans[x]+c[y]
            visited[y]=1
            que.put(y)



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


### FIXED CODE ###

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

d = [[] for i in range(n)]
for i in range(n-1):
    a,b = map(int, input().split())
    d[a-1].append(b-1)
    d[b-1].append(a-1)

c = [0]*n

for i in range(q):
    p,x = map(int,input().split())
    c[p-1]+=x

ans = [0]*n
visited = [0]*n

que = []

que.append(0)
visited[0]=1
ans[0]+=c[0]

while que:
    x = que.pop()
    for y in d[x]:
        if visited[y]==1:
            continue
        else:
            ans[y]+=ans[x]+c[y]
            visited[y]=1
            que.append(y)



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

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]
graph = [[0] * (N+2) for i in range(N+2)]

def dist(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

graph[0][-1] = graph[-1][0] = dist(xs, ys, xt, yt)
for i, (xi, yi, ri) in enumerate(xyr, 1):
  d1 = max(0, dist(xs, ys, xi, yi) - ri)
  d2 = max(0, dist(xt, yt, xi, yi) - ri)
  graph[0][i] = graph[i][0] = d1
  graph[-1][i] = graph[i][-1] = d2
  for j, (xj, yj, rj) in enumerate(xyr, 1):
    dij = max(0, dist(xi, yi, xj, yj) - ri -rj)
    graph[i][j] = graph[j][i] = dij

INF = 10**15
d = [INF] * (N+2)
d[0] = 0
h = []
for i, di in enumerate(graph[0][1:], 1):
  heappush(h, [di, i])

while h:
  di, i = heappop(h)
  if d[i] < INF:
    continue
  d[i] = di
  if i == N+1:
    print(di)
    quit()
  for j, dj in enumerate(graph[i]):
    if d[j] < INF or j == i:
      continue
    heappush(h, [d[i]+dj, j])

### FIXED CODE ###

from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import dijkstra

xs, ys, xt, yt = map(int, input().split())
N = int(input())
xyr = [list(map(int, input().split())) for i in range(N)]

def dist(x1, y1, x2, y2):
  return ((x1-x2)**2 + (y1-y2)**2)**0.5

row = [0]
col = [1]
data = [dist(xs, ys, xt, yt)]
for i, (xi, yi, ri) in enumerate(xyr, 2):
  d1 = max(0, dist(xi, yi, xs, ys) - ri)
  d2 = max(0, dist(xi, yi, xt, yt) - ri)
  row.extend([0, 1])
  col.extend([i, i])
  data.extend([d1, d2])
  for j in range(i-1, N):
    xj, yj, rj = xyr[j]
    dij = max(0, dist(xi, yi, xj, yj) - ri - rj)
    row.append(i)
    col.append(j+2)
    data.append(dij)

graph = csr_matrix((data, (row, col)), shape=(N+2, N+2))
dist = dijkstra(graph, directed=False, indices=0)
print(dist[1])
### BUGGY CODE ###

import sys
input = sys.stdin.readline
s = int(input())
n = len(str(s))
d = 1
cnt = [0]*2019
for i in range(n+1):
    cnt[(s%d)%2019] += 1
    d *= 10


#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

print(ans)


### FIXED CODE ###

s = input()[::-1]
a = 0
cnt = [0]*2019
cnt[0] = 1
d = 1
for c in s:
    a += int(c) * d
    a %= 2019
    d *= 10
    d %= 2019
    cnt[a] += 1

#slist = [(s%(10**i))%2019 for i in range(n+1)]
#print(slist)


ans = 0
for i in range(2019):
    ans += cnt[i]*(cnt[i]-1)//2

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

b = {}
for _ in range(int(input())): s=input(); b[s]=b.get(s,0)+1
print(*sorted(k for k in b if b[k]==max(b.values())))

### FIXED CODE ###

b = {}
for _ in range(int(input())): s=input(); b[s]=b.get(s,0)+1
m = max(b.values())
print(*sorted(k for k in b if b[k]==m))
### BUGGY CODE ###

import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)]
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    graphB = [set() for i in range(N)]
    for i in range(N):
        q = collections.deque()
        q.append((0, i))
        pathi = set()
        while q:
            cost, now = q.popleft()
            if cost > 3: break
            elif cost == 3:
                pathi |= {now}
                for s in son[now]: q.append((cost + 1, s))
            else:
                for s in son[now]: q.append((cost + 1, s))
        graphB[i] = pathi
    
    q = collections.deque()
    visited = [-1] * N
    q.append((0, S-1))
    while q:
        cost, now = q.popleft()
        if visited[now] < 0:
            visited[now] = cost
            for s in graphB[now]:
                if visited[s] < 0: q.append((cost + 1, s))

    print(visited[T-1])
    return 0

if __name__ == "__main__":
    solve()

### FIXED CODE ###

import sys, collections

def solve():
    input = sys.stdin.readline
    N, M = map(int, input().split())
    son = [[] for i in range(N)] 
    for i in range(M):
        u, v = map(int, input().split())
        son[u-1].append(v-1)
    S, T = map(int, input().split())

    dist = [[-1, -1, -1] for i in range(N)]
    que = collections.deque()
    que.append((0, S-1, 0)) #k回目の移動, 場所, mod
    while que:
        cost, now, mod = que.popleft()
        if dist[now][mod] == -1:
            dist[now][mod] = cost
            if mod == 0:
                for s in son[now]:
                    if dist[s][1] == -1: que.append((cost + 1, s, 1))
            else:
                for s in son[now]:
                    if dist[s][(mod + 1) % 3] == -1: que.append((cost, s, (mod + 1) % 3))

    print(dist[T-1][0])  
    return 0

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

import math
import bisect

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

for i in range(M):
  if (A[N - 1] < A[N - 2]):
    a = A.pop(-1)
    bisect.insort(A, a)
  A[N - 1] /= 2.0
amount = 0
for a in A:
  amount += math.floor(a)
print(amount)

### FIXED CODE ###

import math
import heapq

N, M = list(map(int, input().split()))
A = list(map(lambda a: -int(a), input().split()))
A.sort()
heapq.heapify(A)

for i in range(M):
  a = heapq.heappop(A)
  a = -(-a / 2.0)
  heapq.heappush(A, a)

amount = 0
for a in A:
  amount += math.floor(-a)
print(amount)
### BUGGY CODE ###

from collections import Counter
 
N = int(input())
 
A = []
for i in range(N):
    a = input()
    a_counter = Counter(a)
    A.append(a_counter)
    
cnt = 0
for i in range(N):
    for j in range(i + 1, N):
        if A[i] == A[j]:
            cnt += 1
            
print(cnt)

### FIXED CODE ###

N = int(input())
 
D = {}
for i in range(N):
    s = ''.join(sorted(input()))
    D.setdefault(s, 0)
    D[s] += 1
    
ans = 0
for v in D.values():
    if v > 1:
        for i in range(v):
            ans += i
    
print(ans)
### BUGGY CODE ###

def C_SnukeFestival(N, A, B, C):
    a = sorted(A)
    b = sorted(B)
    c = sorted(C)

    l = N
    ans = 0
    for i in range(N):
        for j in range(N):
            for k in range(N):
                if a[i] < b[j] and b[j] < c[k]:
                    ans += 1
    return ans

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
print(C_SnukeFestival(N, A, B, C))
#間に合いそうもない

### FIXED CODE ###

def C_SnukeFestival(N, A, B, C):
    a = sorted(A)
    b = sorted(B)
    c = sorted(C)

    import bisect
    ans = 0
    for j in range(N):
        # b[j]より小さなaの要素の個数
        i = bisect.bisect_left(a, b[j])
        # b[j]より大きなcの要素の個数
        k = N - bisect.bisect_right(c, b[j])
        ans += i * k
    return ans

N = int(input())
A = [int(_) for _ in input().split()]
B = [int(_) for _ in input().split()]
C = [int(_) for _ in input().split()]
print(C_SnukeFestival(N, A, B, C))
### BUGGY CODE ###

from collections import deque
N,H=map(int,input().split())
a=deque([]);b=deque([])
for _ in range(N):
    ai,bi=map(int,input().split())
    a.append(ai)
    b.append(bi)
bb=deque([])
ma=max(a)
for _ in range(N):
    bi=max(b)
    b.remove(bi)
    if bi>ma:
        bb.append(bi)
    if sum(bb)>=H:
        print(len(bb))
        exit()
ans=(H-sum(bb))//ma+len(bb)
if (H-sum(bb))%ma==0:
    print(ans)
else:
    print(ans+1)

### FIXED CODE ###

N,H=map(int,input().split())
S=[[int(x) for x in input().split()] for _ in range(N)]
A,B=zip(*S)
A=max(A)
B=[b for b in B if b>A]
B.sort(reverse=True)
ans=0
cnt=0
for b in B:
    if H<=0:
        break
    cnt+=1
    H-=b
if H>0:
    cnt+=(H-1)//A+1
print(cnt)
### BUGGY CODE ###

from sys import stdin

def to_dict_from_str(s):
    d = {}
    for i in range( len(s) ):
        d[i] = s[i]
    return d

if __name__ == '__main__':
    S_R = stdin.readline().rstrip()
    S_L = S_R[::-1]
    S_R = to_dict_from_str( S_R )
    S_L = to_dict_from_str( S_L )

    len_s = len( S_R )
    H = {}
    for i in range( len_s ):
        H[i] = 0

    # Rの探索
    for i in range( len_s - 1 ):
        s = S_R[i]
        if s == 'R':
            count = 1
            for j in range( i+1, len_s ):
                if S_R[j] == 'L':
                    index = j
                    break
                else:
                    count += 1

            if count % 2 == 0:
                H[ j ] += 1
            else:
                H[ j - 1 ] += 1
        else:
            pass

    # Lの探索
    for i in range( len_s - 1 ):
        s = S_L[i]
        if s == 'L':
            count = 1
            for j in range( i+1, len_s ):
                if S_L[j] == 'R':
                    index = j
                    break
                else:
                    count += 1

            if count % 2 == 0:
                H[ len_s - j - 1 ] += 1
            else:
                H[ len_s - (j - 1) - 1 ] += 1
        else:
            pass

    for i in range( len_s ):
        print( "{} ".format( H[i] ), end="" )
    print()

### FIXED CODE ###

import sys
input = lambda: sys.stdin.readline().rstrip()
input_nums = lambda: list(map(int, input().split()))

def main():
    S = input()
    S = list(S) + ['R']
    ans = [0]*len(S)
    b = 'L'
    index = []
    for i, s in enumerate(S):
        if b != s:
            index.append(i)
        b = s
    # print(index)
    for i in range(0, len(index)-2, 2):
        x = index[i]
        y = index[i + 1]
        z = index[i + 2]
        # print(x, y, z)
        a = y - x
        b = z - y
        ans[y-1] = (a+b)//2
        ans[y] = (a+b)//2
        if (a+b)%2 == 1:
            if a%2 == 1:
                ans[y-1] += 1
            if b%2 == 1:
                ans[y] += 1
    print(*ans[:-1])


if __name__ == '__main__':
    main()