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

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
parent = []
q = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in q.keys():
        parent.append(a)
        q[a] = 0
    q[a] += b
parent.sort()
cnt = 0
for p in parent:
    cnt += q[p]
    if cnt >= k:
        print(p)
        break


### FIXED CODE ###

import sys
input = sys.stdin.readline
n,k = map(int,input().split())
inf = 10**10
parent = [inf]*n
q = {}
for i in range(n):
    a,b = map(int,input().split())
    if a not in q.keys():
        parent[i] = a
        q[a] = 0
    q[a] += b
parent.sort()
cnt = 0
for p in parent:
    cnt += q[p]
    if cnt >= k:
        print(p)
        break
### BUGGY CODE ###

from collections import deque

H, W, K = map(int, input().split())
A = [input() for h in range(H)]

for h in range(H):
  for w in range(W):
    if A[h][w] == 'S':
      sx, sy = h, w

INF = 1000
dist = [[INF for w in range(W)] for h in range(H)]
dist[sx][sy] = 0


dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
start = []
d = deque([[sx, sy]])
while d:
  x, y = d.popleft()
  for dx, dy in dxy:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and dist[xx][yy]==INF:
      if A[xx][yy] == '.':
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
        if dist[xx][yy] <= K:
          start.append([xx, yy])

ans = min(-(-(H-1-sx)//K)+1, -(-sx//K)+1, -(-(W-1-sy)//K)+1, -(-sy//K)+1)
for x, y in start:
  ans = min(ans, -(-(W-1 - y)//K) + 1) # 右
  ans = min(ans, -(-y//K) + 1) # 左
  ans = min(ans, -(-(H-1 - x)//K) + 1) # 下
  ans = min(ans, -(-x//K) + 1) # 上

print(ans)

### FIXED CODE ###

from collections import deque

H, W, K = map(int, input().split())
A = [input() for h in range(H)]

for h in range(H):
  for w in range(W):
    if A[h][w] == 'S':
      sx, sy = h, w

INF = 1000
dist = [[INF for w in range(W)] for h in range(H)]
dist[sx][sy] = 0


dxy = [[1, 0], [0, 1], [-1, 0], [0, -1]]
start = []
d = deque([[sx, sy]])
while d:
  x, y = d.popleft()
  for dx, dy in dxy:
    xx = x + dx; yy = y + dy
    if 0<=xx<H and 0<=yy<W and dist[xx][yy]==INF:
      if A[xx][yy] == '.':
        dist[xx][yy] = dist[x][y] + 1
        d.append([xx, yy])
        if dist[xx][yy] <= K:
          start.append([xx, yy])

ans = min(-(-(H-1-sx)//K)+1, -(-sx//K)+1, -(-(W-1-sy)//K)+1, -(-sy//K)+1)
for x, y in start:
  ans = min(ans, -(-(W-1 - y)//K) + 1) # 右
  ans = min(ans, -(-y//K) + 1) # 左
  ans = min(ans, -(-(H-1 - x)//K) + 1) # 下
  ans = min(ans, -(-x//K) + 1) # 上

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

def main():
  _range = range
  h, w = map(int, input().split())
  s = [input() + '#' for _ in _range(h)]
  s.append('#' * (w + 1))
  t = [[-1] * w for _ in _range(h + 1)]
  tstart = [-1] * (w + 1)
  for i in _range(h + 1):
    ystart = -1
    si = s[i]
    ti = t[i]
    for j in _range(w + 1):
      tj = tstart[j]
      if si[j] == '#':
        if ystart != -1:
          n = j - ystart
          for k in _range(ystart, j):
            ti[k] += n
          ystart = -1
        if tj != -1:
          n = i - tj
          for k in _range(tj, i):
            t[k][j] += n
          tstart[j] = -1
      else:
        if ystart == -1:
          ystart = j
        if tj == -1:
          tstart[j] = i
  print(max(map(max, t)))
main()

### FIXED CODE ###

h, w = map(int, input().split())
s = [input() + '#' for _ in range(h)]
s.append('#' * w)

yoko = [[0] * w for _ in range(h)]
for i in range(h):
  if s[i][0] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, w + 1):
    if s[i][j] == '#':
      if start != -1:
        for k in range(start, j):
          yoko[i][k] = j - start
        start = -1
    else:
      if start == -1:
        start = j

tate = [[0] * w for _ in range(h)]
for i in range(w):
  if s[0][i] == '.':
    start = 0
  else:
    start = -1
  for j in range(1, h + 1):
    if s[j][i] == '#':
      if start != -1:
        for k in range(start, j):
          tate[k][i] = j - start
        start = -1
    else:
      if start == -1:
        start = j
result = 0
for i in range(h):
  for j in range(w):
    t = yoko[i][j] + tate[i][j] - 1
    if t > result:
      result = t

print(result)
### BUGGY CODE ###

N = int(input())

for x in range(1,N+1):
  cnt = 0
  for i in range(1,100):
    for j in range(1,100):
      for k in range(1,100):
        if (i+j+k)**2-(i*j+i*k+j*k) == x:
          cnt += 1
  
  print(cnt)

### FIXED CODE ###

N = int(input())

ans = [0]*10050

for i in range(1,105):
  for j in range(1,105):
    for k in range(1,105):
      v = (i+j+k)**2-(i*j+i*k+j*k)
      if v < len(ans):
        ans[v] += 1
  
for x in range(1,N+1):
  print(ans[x])
### BUGGY CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()

    tmp = 1
    for i in range(k):
        tmp *= a[i]

    prev = tmp

    for i in range(k, n):
        crnt = (prev // a[i - k]) * a[i]

        print("Yes" if crnt > prev else "No")
        prev = crnt


if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
import re
import math
import collections
import decimal
import bisect
import itertools
import fractions
import functools
import copy
import heapq
import decimal
import statistics
import queue

# import numpy as np

sys.setrecursionlimit(10 ** 9)
INF = 10 ** 16
MOD = 10 ** 9 + 7
# MOD = 998244353

ni = lambda: int(sys.stdin.readline())
ns = lambda: map(int, sys.stdin.readline().split())
na = lambda: list(map(int, sys.stdin.readline().split()))


# ===CODE===

def main():
    n, k = ns()
    a = na()

    # tmp = 1
    # for i in range(k):
    #     tmp *= a[i]
    #
    # prev = tmp

    for i in range(k, n):
        # crnt = (prev // a[i - k]) * a[i]

        print("Yes" if a[i] > a[i-k] else "No")
        # prev = crnt


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

S = input().split(" ")
N = int(S[0])
M = int(S[1])


def C(m, n):
    t = m
    s1 = 1
    while t > (m - n):
        s1 = s1 * t
        t = t - 1

    s2 = 1

    t = n
    while t >= 1:
        s2 = s2 * t
        t = t - 1

    return int(s1 / s2)


def A(m, n):
    s = 1
    t = m

    while t > m - n:
        s = s * t
        t = t - 1

    return s


def calculate(maxValue, minValue):
    if maxValue > minValue + 1:
        return 0

    if maxValue == minValue:
        S = A(maxValue,maxValue)
        return  2 * S * S

    return A(maxValue,maxValue) * A(minValue,minValue)

result = calculate(max(N,M),min(N,M))

print(result % 1000000007)

### FIXED CODE ###

S = input().split(" ")
N = int(S[0])
M = int(S[1])


def C(m, n):
    t = m
    s1 = 1
    while t > (m - n):
        s1 = s1 * t
        t = t - 1

    s2 = 1

    t = n
    while t >= 1:
        s2 = s2 * t
        t = t - 1

    return int(s1 / s2)


def A(m, n):
    s = 1
    t = m

    while t > m - n:
        s = (s * t) % 1000000007
        t = t - 1

    return s


def calculate(maxValue, minValue):
    if maxValue > minValue + 1:
        return 0

    if maxValue == minValue:
        S = A(maxValue,maxValue)
        return  2 * S * S

    return A(maxValue,maxValue) * A(minValue,minValue)

result = calculate(max(N,M),min(N,M))

print(result % 1000000007)
### BUGGY CODE ###

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

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a % b)
    
def mod_combination(N, K, M):
    def mod_permutation(n, k, mod):
        ret = 1
        for i in range(n, n-k, -1):
            ret *= i
            ret %= mod
        return ret

    def mod_inv(k, mod):
        return (pow(k,mod-2,mod))
    
    def mod_inv_permutation(n, k, mod):
        return mod_inv(mod_permutation(n, k, mod), mod)

    return (mod_permutation(N,K,M) * mod_inv_permutation(K, K, M))%M

g = gcd(k, gcd(a, b))
a //= g
b //= g
k //= g

if a < b:
    tmp = a
    a = b
    b = tmp

mod = 998244353
ans = 0
for x in range(max(-int(-(k-b*n)//a),0), k//a+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        
        ans += mod_combination(n, x, mod) * mod_combination(n, y, mod)
        ans %= mod
    
print(ans)

### FIXED CODE ###

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

mod = 998244353
fact = [1] + [0] * n
inv_fact = [0] * (n+1)
for i in range(n):
    fact[i+1] = (fact[i] * (i+1)) % mod

for i in range(n+1):
    inv_fact[i] = pow(fact[i],mod-2,mod)
    
def cb(n, k, mod):
    return (fact[n] * inv_fact[k] * inv_fact[n-k]) % mod

ans = 0
for x in range(n+1):
    if (k-x*a) % b == 0:
        y = (k-x*a)//b
        if y >= 0:
            if x > n or y > n:
                pass
            else:
                ans += cb(n, x, mod) * cb(n, y, mod)
                ans %= mod
    
print(ans)
### BUGGY CODE ###

N = int(input())
a_li = list(map(int, input().split()))
# y = X - x
# |x - y| = |x - (X - x)|
#         = |-X + 2x|
total = sum(a_li)
ans = 10 ** 18
for i in range(1, N):
    ans = min(ans, abs(sum(a_li[:i]) * 2 - total))
print(ans)


### FIXED CODE ###

from itertools import accumulate

N = int(input())
a_li = list(map(int, input().split()))
# y = X - x
# |x - y| = |x - (X - x)|
#         = |-X + 2x|
total = sum(a_li)
acc = list(accumulate(a_li))
ans = 10 ** 18
for i in range(N - 1):
    ans = min(ans, abs(acc[i] * 2 - total))
print(ans)
### BUGGY CODE ###

from itertools import accumulate
from collections import Counter


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

s = 0
for j in range(n):
    l = list(accumulate(a[j:]))
    c = Counter(l)
    s += c[0]

print(s)

### FIXED CODE ###

from itertools import accumulate
from collections import Counter


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

l = [0] + list(accumulate(a))
c = Counter(l)


s = 0
for key, value in c.items():
    s = s + value * (value - 1) // 2

print(s)
### BUGGY CODE ###

 # import sys  sys.exit()を使う時に必要

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    # N = int(input())
    X, Y, Z, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()] 
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()] 
    # S = [input() for _ in range(N)]  縦持ち／行数N
    # t = [0] * N  　　ti xi yi 縦持ち/行数N
    # x = [0] * N
    # y = [0] * N
    # for i in range(N):
    #   t[i], x[i], y[i] = map(int, input().split())
  else:
    #A = [1,10,100]
    #B = [2,20,200]
    #C = [1,10,100]
    A = [4,6]
    B = [1,5]
    C = [3,8]
    X = len(A)
    Y = len(B)
    Z = len(C)
    # K = 5
    K = 8

  ans = []
  # Processing
  A.sort(reverse=True)
  B.sort(reverse=True)
  C.sort(reverse=True)
      
  for i in A:
    if i >= A[min(K,X)-1]:
      for j in B:
        if j >= B[min(K,Y)-1] :
          for k in C:
            if k >= C[min(K,Z)-1]:
              ans.append(i+j+k)
            else:
              break
        else:
          break
    else:
      break
    
  ans.sort(reverse=True)
  if 'get_ipython' in globals(): 
    print(ans)

  for i in range(0,K):
    print(ans[i])      

main()

### FIXED CODE ###

def main():
  if 'get_ipython' not in globals():  
    # For Subsession
    X, Y, Z, K = (int(i) for i in input().split())
    A = [int(i) for i in input().split()] 
    B = [int(i) for i in input().split()]
    C = [int(i) for i in input().split()] 
  else:
    A = [1,10,100]
    B = [2,20,200]
    C = [1,10,100]
    #A = [4,6]
    #B = [1,5]
    #C = [3,8]
    X = len(A)
    Y = len(B)
    Z = len(C)
    K = 5
    #K = 8

  # Processing
  AB = []
  A.sort(reverse=True)
  B.sort(reverse=True)
  for i in A[0:K]:
    for j in B[0:K]:
      AB.append(i+j)
  
  AB.sort(reverse=True)
  
  ABC = []
  C.sort(reverse=True)
  
  for i in AB[0:K]:
    for j in C[0:K]:
      ABC.append(i+j)  
  
  ABC.sort(reverse=True)

  for i in ABC[0:K]:
    print(i)      

main()
### BUGGY CODE ###

from sys import stdin
R,G,B,N=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
for r in range(0,N//R+1):
    for g in range(0,N-(R*r)+1):
        for b in range(0,N-(R*r)-(G*g)+1):
            ball = R*r + G*g + B*b
            if ball == N:
                ans+=1
print(ans)

### FIXED CODE ###

from sys import stdin
R,G,B,N=[int(x) for x in stdin.readline().rstrip().split()]
ans=0
for r in range(0,N//R+1):
    for g in range(0,(N-(R*r))//G+1):
        if (N - R*r - G*g) % B == 0:
            ans+=1
print(ans)
### BUGGY CODE ###

# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

edges = [[] for i in range(n)]
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] < c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.appendleft((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)

### FIXED CODE ###

# 最大でも3Nしか頂点には回らない
import sys
from collections import deque
input = sys.stdin.readline
n, m = map(int, input().split())

edges = [[] for i in range(n)]
for i in range(m):
    u,v = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append(v)

dist = [[False]*3 for i in range(n)]
cnt = [[0]*3 for i in range(n)]
s, t = map(int, input().split())
s -= 1
t -= 1
q = deque()
# now, dist(mod3), cnt
q.append((s, 0, 0))
while q:
    now, d, c = q.popleft()
    if dist[now][d] and cnt[now][d] <= c:
        continue
    dist[now][d] = True
    cnt[now][d] = c
    next_d = (d+1)%3
    next_c = c+1
    for to in edges[now]:
        if not dist[to][next_d] or cnt[to][next_d] > c:
            q.append((to, next_d,next_c))
if dist[t][0]:
    print(cnt[t][0]//3)
else:
    print(-1)
### BUGGY CODE ###

import sys
input=sys.stdin.readline
import collections
import bisect

def main():
    _,M=map(int,input().split())
    A = list(map(int, input().split()))
    A.sort()
    while M>0:
        a = A.pop()
        if a == 0:
            print(0)
            return
        if A:
            b = A.pop()
            while a >= b:
                a //= 2
                M -= 1
            bisect.insort(A, b)
        else:
            a //= 2**M
            M = 0
        bisect.insort(A, a)
    print(sum(A))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
input=sys.stdin.readline
import heapq

def main():
    _,M=map(int,input().split())
    A = []
    for a in list(map(int, input().split())):
        heapq.heappush(A, -a)
    while M>0:
        a = -heapq.heappop(A)
        a //= 2
        M -= 1
        heapq.heappush(A, -a)
    print(-sum(A))

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

N = int(input())

# 最初の符号
print(1, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2 + 1)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid


### FIXED CODE ###

N = int(input())

# 最初の符号
print(0, flush=True)
first = input()

if first == 'Vacant':
    exit()

if first == 'Male':
    first = 1
else:
    first = -1

notHas = 1
has = N - 1

while has - notHas > 1:
    mid = (notHas + has) // 2
    print(mid, flush=True)
    ret = input()

    if ret == 'Vacant':
        exit()

    if ret == 'Male':
        ret = 1
    else:
        ret = -1

    trueValue = first * (-1)**(mid % 2)
    if ret == trueValue:
        notHas = mid
    else:
        has = mid

print(notHas, flush=True)
ret = input()

if ret == 'Vacant':
    exit()

print(has, flush=True)
input()
exit()
### BUGGY CODE ###

N,M = map(int,input().split())
H=list(map(int,input().split()))
ABmap=[[0 for i in range(N)] for i in range(N)]
count=0
for i in range(N):
    ABmap[i][i]=H[i]
for i in range(M):
    A,B=map(lambda x:x-1,map(int,input().split()))
    ABmap[A][B]=H[B]
    ABmap[B][A]=H[A]
        
for i in range(N):
    #print(ABmap[i])
    #print(ABmap.count(H[i]))
    if max(ABmap[i])==H[i] and ABmap[i].count(H[i])==1:
        count+=1
print(count)
        
    

### FIXED CODE ###

N,M = map(int,input().split())
H=list(map(int,input().split()))
ABmap=[[] for i in range(N)]
count=0
for i in range(M):
    A,B=map(lambda x:x-1,map(int,input().split()))
    ABmap[A].append(H[B])
    ABmap[B].append(H[A])
        
for i in range(N):
    if len(ABmap[i])==0:
        count+=1
    elif max(ABmap[i])<H[i]:
        count+=1
   # print(ABmap[i])
print(count)
### BUGGY CODE ###

N = int(input())
res = 10**10 + 1
for A in range(1, N + 1):
    if N % A == 0:
        B = N // A
        a = len(str(A))
        b = len(str(B))
        if a > b:
            num = a
        else:
            num = b
        if res > num:
            res = num
print(res)


### FIXED CODE ###

import math
N = int(input())
ans = float('Inf')
sq = int(math.sqrt(N)) + 1
for i in range(1, sq):
    if N % i == 0:
        a = len(str(i))
        b = len(str(N // i))
        if a > b:
            num = a
        else:
            num = b
        if ans > num:
            ans = num
print(ans)
### BUGGY CODE ###

import math

N = int(input())

a = []
s = 0
for _ in range(N):
    a_i = int(input())
    a.append(a_i)
    s += a_i

# Calculate counts of (R >= s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            if j - a[i - 1] < 0:
                dp[i][j] = dp[i - 1][j] * 2
            else:
                dp[i][j] = dp[i - 1][j] * 2 + dp[i - 1][j - a[i - 1]]

c0 = 0
for j in range(math.ceil(s / 2), s + 1):
    c0 += dp[N][j]

# Calculate counts of (R == s / 2 and G == s / 2)
dp = [[0 for _ in range(s + 1)] for _ in range(N + 1)]

for i in range(N + 1):
    for j in range(s + 1):
        if i == 0:
            dp[i][j] = 1 if j == 0 else 0
        else:
            if j - a[i - 1] < 0:
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i - 1][j] + dp[i - 1][j - a[i - 1]]

c1 = 0
if s % 2 == 0:
    c1 = dp[N][s // 2]

ans = (3 ** N - 3 * c0 + 3 * c1) % 998244353
print(ans)

### FIXED CODE ###

import math
import numpy as np

N = int(input())
a = np.array([int(input()) for _ in range(N)])
s = np.sum(a)

# Counts of (R >= s / 2)
dp0 = np.zeros((N + 1, s + 1))
dp0[0, 0] = 1
# Counts of (R == s / 2 and G == s / 2)
dp1 = np.zeros((N + 1, s // 2 + 1))
dp1[0, 0] = 1

mod = 998244353
for i, x in enumerate(a):
    dp0[i + 1, :] += dp0[i, :] * 2 % mod
    dp0[i + 1, x:] += dp0[i, :-x] % mod
    dp1[i + 1, :] += dp1[i, :] % mod
    dp1[i + 1, x:] += dp1[i, :-x] % mod

c0 = int(np.sum(dp0[N][math.ceil(s / 2):]))
c1 = int(dp1[N][s // 2]) if s % 2 == 0 else 0

ans = (3 ** N - 3 * c0 + 3 * c1) % mod
print(ans)
### BUGGY CODE ###

N, M, Q = map( int, input().split())
NN = [ [ 0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    for i in range(R,N+1):
        NN[L][i] += 1

ANS =  [ [ 0 for _ in range(N+1)] for _ in range(N+1)]
for i in range(1,N+1):
    ANS[i][N] = NN[i][N]
for j in range(1,N+1):
    for i in range(N-1,0,-1):
        ANS[i][j] = ANS[i+1][j] + NN[i][j]
for _ in range(Q):
    p, q = map(int, input().split())
    print(ANS[p][q])

### FIXED CODE ###

N, M, Q = map( int, input().split())
NN = [ [0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L, R = map( int, input().split())
    NN[L][R] += 1

for i in range(1,N+1):
    for j in range(1,N+1):
        NN[i][j] += NN[i][j-1]+NN[i-1][j]-NN[i-1][j-1]
for _ in range(Q):
    p, q = map( int, input().split())
    print(NN[q][q]-NN[q][p-1]-NN[p-1][q]+NN[p-1][p-1])
### BUGGY CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

from collections import defaultdict
import bisect


def solve():
    n, m, q = map(int, input().split())
    d = defaultdict(list)
    for i in range(m):
        l, r = map(int, input().split())
        bisect.insort_left(d[l], r)
    table = [[0 for i in range(n + 1)] for j in range(n + 1)]
    dk = [p for p in d.keys()]
    dk.sort()
    for i in range(1, n + 1):
        ri = bisect.bisect_left(dk, i)
        dk = dk[ri:]
        if not dk:
            break
        for j in range(1, n + 1):
            tans = 0
            for k in [p for p in dk if p <= j]:
                tans += bisect.bisect_right(d[k], j)
            table[i][j] = tans
    for i in range(q):
        l, r = map(int, input().split())
        print(table[l][r])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

#!/usr/bin/env python
# -*- coding: utf-8 -*-

import bisect
import array


def solve():
    n, m, q = map(int, input().split())
    nl = [[0 for i in range(n + 1)] for j in range(n + 1)]
    for e in [input().split() for _ in range(m)]:
        l, r = int(e[0]), int(e[1])
        nl[l][r] += 1
    table = [array.array("i", [0] * (n + 2)) for j in range(n + 2)]
    ran = array.array("i", range(n + 1))
    for i in ran:
        for j in ran:
            table[i][j + 1] = table[i][j] + nl[i][j]

    for i, e in enumerate([input().split() for _ in range(q)]):
        l, r = int(e[0]), int(e[1])
        ans = 0
        for j in range(l, r + 1):
            ans += table[j][r + 1] - table[j][l]
        print(ans)


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

class Okojo:
    def __init__(self, line):
        self.line = line
        self.l = []
        self.r = []
        self.get_lr()

    def get_lr(self):
        for i in range(len(self.line)):
            if self.line[i] == 'L':
                self.l.append(i)
            else:
                self.r.append(i)

    def get_next(self, state):
        nex = [0] * len(self.line)
        for i in range(len(self.l)):
            nex[self.l[i] - 1] += state[self.l[i]]
        for i in range(len(self.r)):
            nex[self.r[i] + 1] += state[self.r[i]]
        return nex


def resolve():
    line = input()

    okojo = Okojo(line)

    now = [1] * len(line)
    before1 = now
    for i in range(10 ** 100):
        before2 = before1
        before1 = now
        now = okojo.get_next(before1)
        if before1 == now:
            break
        elif before2 == now:
            if i % 2 == 0:
                now = before1
            break

    print(*now)
    
resolve()

### FIXED CODE ###

def resolve():
    line = input()
    result = [0] * len(line)

    r_odd = 0
    r_even = 0
    for i in range(len(line)):
        if line[i] == 'L':
            if i % 2 == 0:
                result[i] += r_even
                result[i-1] += r_odd
            else:
                result[i] += r_odd
                result[i-1] += r_even
            r_odd = 0
            r_even = 0
        elif line[i] == 'R':
            if i % 2 == 0:
                r_even += 1
            else:
                r_odd += 1
    l_odd = 0
    l_even = 0
    for i in range(len(line)-1, -1, -1):
        if line[i] == 'R':
            if i % 2 == 0:
                result[i] += l_even
                result[i+1] += l_odd
            else:
                result[i] += l_odd
                result[i+1] += l_even
            l_odd = 0
            l_even = 0
        elif line[i] == 'L':
            if i % 2 == 0:
                l_even += 1
            else:
                l_odd += 1

    print(*result)
    
resolve()