Harryxun/stf_run huggingface dataset:
inf = 0x10101010

def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]:
				continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
				if cost[i] < min:
					min = cost[i]
					next = i
		strt = next 
		if next == -1: break
	return cost
						



while 1:
	#  経路の情報の数n,駅の数m
	n, m = map(int, raw_input().split())
	if n == 0:
		break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]

	for i in range(n):
		a, b, c, t = map(int, raw_input().split()) # 駅 駅 time cost
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T, i) for i in range(m)]
	CS = [solve(C, i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int, raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]

### FIXED CODE ###

inf = 0x10101010
def solve(A, strt):
	cost = [inf]*m  
	visited = [False]*m
	cost[strt] = 0
	while 1:
		min = inf 
		next = -1   
		visited[strt] = True 
		for i in range(m):
			if visited[i]: continue
			if A[strt][i]:
				d = cost[strt] + A[strt][i]
				if d < cost[i]:
					cost[i] = d
			if min > cost[i]:	
				min = cost[i]
				next = i
		strt = next 
		if next == -1: break
	return cost
						
while 1:
	n,m = map(int, raw_input().split())
	if n == 0:break
	T = [[0]*m for i in range(m)]
	C = [[0]*m for i in range(m)]
	for i in range(n):
		a,b,c,t = map(int, raw_input().split()) 
		T[a-1][b-1] = T[b-1][a-1] = t 
		C[a-1][b-1] = C[b-1][a-1] = c
	TS = [solve(T,i) for i in range(m)]
	CS = [solve(C,i) for i in range(m)]
	for i in range(input()):
		a, b, q = map(int,raw_input().split())
		if q == 0:
			print CS[a-1][b-1]
		else:
			print TS[a-1][b-1]
s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = ( j * 10 ** (i) ) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] += dp[i-1][k]
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = ( val * 10 ** (i) ) % 13
            for k in range(13):
                dp[i][(k+amari)%13] += dp[i-1][k]
    
print(dp[digits-1][5]/(10**9 + 7))

### FIXED CODE ###

s = list(input())

digits = len(s)
s.reverse()
dp = [ [0] * 13 for i in range(digits)]
# dp[i][j] は i+1桁目までで13で割った余りがjのものを格納する
mod = 10 ** 9 + 7
power = 1

for i in range(digits):
    if s[i] == '?':
        for j in range(10):
            if i == 0:
                dp[i][j] += 1
            else:
                amari = (j * power) % 13
                for k in range(13):
                    dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    else:
        val = int(s[i])
        if i == 0:
            dp[i][val] += 1
        else:
            amari = (val * power)% 13
            for k in range(13):
                dp[i][(k+amari)%13] = (dp[i][(k+amari)%13] + dp[i-1][k]) % mod
    power = (power * 10) % 13
print(dp[digits-1][5])
A, B, X = map(int, input().split())
l = 0
r = 10**9+1


def keta(n):
    cnt = 0
    while n > 0:
        n //= 10
        cnt += 1
    return cnt

while r-l > 1:
    c = (l + r) // 2
    keta_c = keta(c)
    if A * c + B * keta_c <= X:
        l = c
    else:
        r = c

print(l)

### FIXED CODE ###

S = input()

day = {"SUN":7, "MON":6,"TUE":5,"WED":4,"THU":3,"FRI":2,"SAT":1}

print(day[S])
H,W,N = map(int, input().split())
now = [int(i) for i in input().split()]
S = input()
T = input()
flag = True
SM = [now[0],now[1]]
TM = [now[0],now[1]]

for n in range(N):
    if S[n] == 'L':
            SM[1] -= 1
    if S[n] == 'R':
            SM[1] += 1 
    if S[n] == 'U':
            SM[0] -= 1 
    if S[n] == 'D':
            SM[0] += 1
    if T[n] == 'L':
            TM[1] -= 1
    if T[n] == 'R':
            TM[1] += 1 
    if T[n] == 'U':
            TM[0] -= 1 
    if T[n] == 'D':
            TM[0] += 1

sm = [0,0,0,0]
if W-SM[1] >= SM[1]-1:
    sm[0] = 1
if W-SM[1] < SM[1]-1:
    sm[1] = 1
if H-SM[0] <= SM[0]-1:
    sm[2] = 1
if H-SM[0] < SM[0]-1:
    sm[3] = 1

tm = [0,0,0,0]
if W-TM[1] >= TM[1]-1:
    tm[0] = 1
if W-TM[1] <= TM[1]-1:
    tm[1] = 1
if H-TM[0] <= TM[0]-1:
    tm[2] = 1
if H-TM[0] <= TM[0]-1:
    tm[3] = 1

for n in range(N):
    if S[n] == 'L':
        if sm[0] == 1:
            now[1] -= 1
    if S[n] == 'R':
        if sm[1] == 1:
            now[1] += 1 
    if S[n] == 'U':
        if sm[3] == 1:
            now[0] -= 1 
    if S[n] == 'D':
        if sm[4] == 1:
            now[0] += 1
    #print(now)

    if now[0]*now[1] == 0 or now[0] == H+1 or now[1] == W+1 :
        flag = False
        break
    
    if T[n] == 'L':
        if tm[1] == 0:
            now[1] -= 1
    if T[n] == 'R':
        if tm[2] == 0:
            now[1] += 1 
    if T[n] == 'U':
        if tm[3] == 0:
            now[0] -= 1 
    if T[n] == 'D':
        if tm[4] == 0:
            now[0] += 1
    #print(now)

    if now[0]*now[1] == 0 or now[0] == H+1 or now[1] == W+1 :
        flag = False
        break

if flag:
    print('YES')
else:
    print('NO')

### FIXED CODE ###

H,W,N = map(int, input().split())
st = [int(i) for i in input().split()]
S = input()
T = input()


def simu(dim1):
    now = [st[0],st[1]]

    if dim1 == 'U':
        dim2,L,step,dim = 'D',H,1,0
    if dim1 == 'D':
        dim2,L,step,dim = 'U',H,-1,0
    if dim1 == 'L':
        dim2,L,step,dim = 'R',W,1,1
    if dim1 == 'R':
        dim2,L,step,dim = 'L',W,-1,1

    for i in range(N):
        if S[i] == dim1:
            now[dim] -= step
        if now[dim] < 1 or now[dim] >= L+1:
            return True
        if T[i] == dim2:
            if step == 1:
                if now[dim] < L:
                    now[dim] += step
            else:
                if now[dim] > 1:
                    now[dim] += step
    return False
        
Dim = ['U','D','R','L']
for d in Dim:
    if simu(d):
        print('NO')
        exit()
print('YES')
n, m = [int(i) for i in input().split(" ")]
score_dict = {}
 
for i in range(m):
    p, s = input().split(" ")
    if p not in score_dict:
        score_dict[p] = []
    
    score_dict[p].append(s)
 
ac_count = 0
wa_count = 0
 
for i in score_dict.values():

    if "AC" in i:
        ac_count += 1
        wa_count += i.index("AC")]
    else:
        wa_count += len(i)
 
print("{0} {1}".format(ac_count, wa_count))

### FIXED CODE ###

n, m = [int(i) for i in input().split(" ")]
score_dict = {}
 
for i in range(m):
    p, s = input().split(" ")
    if p not in score_dict:
        score_dict[p] = []
    
    score_dict[p].append(s)
 
ac_count = 0
wa_count = 0
 
for i in score_dict.values():

    if "AC" in i:
        ac_count += 1
        wa_count += i.index("AC")
 
print("{0} {1}".format(ac_count, wa_count))
import sys, re
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from collections import deque, defaultdict, Counter
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop, heapify
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N, M, R = MAP()
r = LIST()
dist_matrix = [[INF]*N for _ in range(N)]

for _ in range(M):
	A, B, C = MAP()
	dist_matrix[A-1][B-1] = C
	dist_matrix[B-1][A-1] = C

for i in range(N):
	dist_matrix[i][i] = 0

#for i in range(N):
#	print(dist_matrix[i])
#print()

def Warshall_Floyd(dist, N):
	for k in range(N):
		for i in range(N):
			for j in range(N):
				dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j])

Warshall_Floyd(dist_matrix, N)

#for i in range(N):
#	print(dist_matrix[i])


ans = INF
for x in permutations(r):
	tmp = x[0]
	dis = 0
	for i in range(1, R):
		dis += dist_matrix[tmp-1][x[i]-1]
		tmp = x[i]
	ans = min(ans, dis)
	
print(int(ans))





### FIXED CODE ###

import sys, re
from collections import deque, defaultdict, Counter
from math import ceil, sqrt, hypot, factorial, pi, sin, cos, tan, asin, acos, atan, radians, degrees#, log2
from itertools import accumulate, permutations, combinations, combinations_with_replacement, product, groupby
from operator import itemgetter, mul
from copy import deepcopy
from string import ascii_lowercase, ascii_uppercase, digits
from bisect import bisect, bisect_left
from fractions import gcd
from heapq import heappush, heappop
from functools import reduce
def input(): return sys.stdin.readline().strip()
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
def ZIP(n): return zip(*(MAP() for _ in range(n)))
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
mod = 10 ** 9 + 7

N = INT()

num = defaultdict(int)

for _ in range(N):
	A = INT()
	num[A-1] ^= 1

ans = 0
for x in num:
	ans += num[x]

print(ans)
A,B,C,D = map(int, input().split())
#倒せるターン
TakahashiTrun = 0
AokiTurn = 0
if(C % B != 0):
    TakahashiTurn = C // B + 1
else:
    TakahashiTrun = C // B

if(A % D != 0):
    AokiTurn = A // D + 1
else:
    AokiTurn = A // D
    
if(TakahashiTurn - 1 >= AokiTurn):
    print("No")
else:
    print("Yes")

### FIXED CODE ###

A,B,C,D = map(int, input().split())
THP = A
AHP = C
while(True):
    #高橋のターン
    AHP -= B
    if(AHP <= 0):
        print("Yes")
        break
    #青木のターン
    THP -= D
    if(THP <= 0):
        print("No")
        break
a,b=map(int,input())
if (a+b)//2==0:
  print (a+b)/2
else:
  print('IMPOSSIBLE')

### FIXED CODE ###

a,b=map(int,input().split())
if (a+b)%2==0:
    print ((a+b)//2)
else:
    print('IMPOSSIBLE')
#!/usr/bin/env python3
import sys
import operator
import itertools

def op(op_str):
    funcs = {
            "+":operator.add,
            "-":operator.sub
            }
    return funcs[op_str]

def solve(A,B,C,D):
    for o in itertools.product(["+","-"], repeat = 3):
        ret = op(o[0])(A,B)
        ret = op(o[1])(C,ret)
        ret = op(o[2])(D,ret)
        if ret == 7:
            print(f"{A}{o[0]}{B}{o[1]}{C}{o[2]}{D}=7")
            return


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = input()
    L = [int(c) for c in S]
    
    solve(*L)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys
import operator
import itertools

def op(op_str):
    funcs = {
            "+":operator.add,
            "-":operator.sub
            }
    return funcs[op_str]

def solve(A,B,C,D):
    for o in itertools.product(["+","-"], repeat = 3):
        ret = op(o[0])(A,B)
        ret = op(o[1])(ret,C)
        ret = op(o[2])(ret,D)
        if ret == 7:
            print("{0}{1}{2}{3}{4}{5}{6}=7".format(A,o[0],B,o[1],C,o[2],D))
            return


    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    S = input()
    L = [int(c) for c in S]
    
    solve(*L)

if __name__ == '__main__':
    main()
import sequtils, strutils


if isMainModule:
  var
    n = stdin.readLine.parseInt
    h = stdin.readLine.split.map(parseInt)
    dp: array[1..100000, int]

  for i in 1..n:
    for j in 1..2:
      if i + j > n:
        break
      elif dp[i+j] > min(dp[i] + abs(h[i-1] - h[i+j-1])) or dp[i+j] == 0:
        dp[i+j] = min(dp[i] + abs(h[i-1] - h[i+j-1]))

  echo dp[n]


### FIXED CODE ###

n = int(input())
h = list(map(int, input().split()))
dp = [float("inf")] * (100000+1)

dp[1] = 0
for i in range(1, 100000+1):
    for j in range(1, 3):
        if i + j > n:
            break
        elif dp[i+j] > dp[i] + abs(h[i-1] - h[i+j-1]):
            dp[i+j] = dp[i] + abs(h[i-1] - h[i+j-1])

print(dp[n])
A, B = map(int, input().slit())
 
A_price = A / 8 * 100
 
B_price = B / 10 * 100


if int(A_price) == int(B_price):
  print(int(A_price))
else:
  print(-1)
  

### FIXED CODE ###

A,B = map(int, input().split())
num = 0
while num < 1011:
  num += 1
  X = num * 0.08
  if int(X) == A:
    Y = num * 0.1
    if int(Y) == B:
      print(num)
      break
    else:
      pass
  elif num == 1010:
    print(-1)
    break
  else:
    pass
N, M = [int(i) for i in input().strip().split(' ')]

a = {}
b = {}
for i in range(M):
  X, Y, Z = [int(i) for i in input().strip().split(' ')]
  if X not in a:
    a[X] = set()
    b[X] = 0
  if Y not in a:
    a[Y] = set()
    b[Y] = 0

  a[X].add(Y)
  b[X] += 1
  a[Y].add(X)
  b[Y] += 1


def make_keys(keys, key):
  if key in keys:
    return
  keys.add(key)
  if key in a:
    for k in a[key]:
      make_keys(keys, k)


counter = 0
# print(b)
for key, v in b:
  if key not in a:
    continue
  keys = set()
  make_keys(keys, key)

  for k in keys:
    if k in a:
      del a[k]

  counter += 1

print(counter + N - len(b))

### FIXED CODE ###

N, M = [int(i) for i in input().strip().split(' ')]

a = {}
for i in range(M):
  X, Y, _ = [int(i) for i in input().strip().split(' ')]
  if X not in a: a[X] = set()
  if Y not in a: a[Y] = set()
  a[X].add(Y)
  a[Y].add(X)

len_a = len(a)


def test(key_set):
  tmp = set()
  for key in key_set:
    if key in a:
      tmp = tmp.union(a[key])
      del a[key]

  #print('key_set = {}, tmp = {}'.format(key_set, tmp))
  return tmp


counter = 0
# print(b)

while len(a) > 0:
  #print('---')
  #print('a = {}'.format(a))
  key, key_set = a.popitem()
  #print('key = {}, key_set = {}'.format(key, key_set))
  tmp = test(key_set)
  while len(tmp) > 0:
    tmp = test(tmp)
  #print('a = {}'.format(a))
  counter += 1

print(counter + N - len_a)
N = int(input()) 
result = 1

for n in range(N):
  A = int(input())
  if A == 0:
    result = 0
    break
  result = result*A
  if result>1000000000000000000:
    result = -1
    break

print(result)
    

### FIXED CODE ###

A,B = map(int,input().split())
print(A*B)
N, K = map(int, input().split())
A = list(map(int, input().split()))
new_l=[A[0]]
for i in range(K):
    r = i%N
    if A[new_l[r]-1] in new_l:
        target = A[new_l[r]-1]
        break
    new_l.append(A[new_l[r]-1])
    i+=1

index = new_l.index(target)
right = new_l[:index]
left  = new_l[index:]
pattern = K-len(right)
n = pattern % len(left)
print(left[n-1])

### FIXED CODE ###

n,k = map(int,input().split())
A = [0]+list(map(int,input().split()))
visited = [False for _ in range(n+1)]
pos = 1
x = []
flg = False
for i in range(k):
    if visited[pos] == False:
        x.append(pos)
        visited[pos] = True
        pos = A[pos]
    else:
        flg = True
        pre = x.index(pos)
        loop = x[pre:]
        break
if not flg:
    print(pos)
else:
    print(loop[(k-pre)%len(loop)])
s = input()
t = input()

pos = [0]*len(t)
for i, c in enumerate(t):
    ind = [ii for ii, v in enumerate(s) if v == c]
    if ind[0] == -1:
        print(-1)
        exit()
    pos[i] = ind

print(pos)

lens = len(s)
last = pos[0][0]
print(last)
res = last + 1
for vals in pos[1:]:
    for i, val in enumerate(vals):
        if last < val:
            res += val - last
            break
        else:
            if i==len(vals)-1:
                res += (lens - last - 1) + (val + 1)
            else:
                continue
        last = val

print(res)


### FIXED CODE ###

import collections
import bisect
s = input()
t = input()

dict_pos = collections.defaultdict(list) # dict of index 
for i, ch in enumerate(s, 1): 
    dict_pos[ch].append(i)

count_loop = 0
last_pos = -1
for ch in t:
    list_pos = dict_pos[ch]
    if len(list_pos) == 0:
        print(-1)
        quit()
    if list_pos[-1] <= last_pos:
        last_pos = list_pos[0]
        count_loop += 1
    else:
        last_pos = list_pos[bisect.bisect_right(list_pos, last_pos)]

print(count_loop * len(s) + last_pos)
ans = 0
S = input()
for i in range(1,len(S)): if S[i-1] != S[i]: ans += 1
print(ans) 

### FIXED CODE ###

ans = 0
S = input()
for i in range(1,len(S)):
  if S[i-1] != S[i]: ans += 1
print(ans)
import sys
mod = int(1e9+7)
input=sys.stdin.readline
N = int(input())
A = list(map(int, input().split()))
#S[0]は使わない
S = [[0]*60 for _ in range(N)]

tmp = A[-1]
idx = 0
while tmp > 0:
    if tmp%2:
        S[-1][idx] += 1
    idx += 1
    tmp //= 2

for i in range(N-2, 0, -1):
    for j in range(60):
        S[i][j] = S[i+1][j]
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            S[i][idx] += 1
        idx += 1
        tmp //= 2

ans = 0
for i in range(N-1):
    tmp = A[i]
    idx = 0
    while tmp > 0:
        if tmp % 2:
            ans += ((N-1-i)-S[i+1][idx])*pow(2, idx, mod)%mod

        else:
            ans += S[i+1][idx]*pow(2, idx, mod)%mod

        idx += 1
        tmp //= 2
        ans %= mod

    rest = S[i+1][idx:]
    for x in rest:
        ans += xpow(2, idx, mod)%mod
        idx += 1
        ans %= mod

print(ans)

### FIXED CODE ###

mod = int(1e9+7)
N = int(input())
A = list(map(int, input().split()))
ans = 0
for i in range(60):
    a = 0
    b = 0
    for j in range(N):
        if A[j] % 2:
            a += 1
        else:
            b += 1
        A[j] //= 2
    ans += a*b*pow(2, i, mod)
    ans %= mod
print(ans)
N, M = map(int, input().split())
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if N < 2:
  a = cmb(M,2)
elif M < 2:
  a = cmb(N,2)
else:
  a = cmb(N,2) + cmb(M,2)

print(int(a))

### FIXED CODE ###

N, M = map(int, input().split())
 
nCr = {}
def cmb(n, r):
    if r == 0 or r == n: return 1
    if r == 1: return n
    if (n,r) in nCr: return nCr[(n,r)]
    nCr[(n,r)] = cmb(n-1,r) + cmb(n-1,r-1)
    return nCr[(n,r)]

if N < 2 and M < 2:
  a = 0
elif N < 2:
  a = cmb(M,2)
elif M < 2:
  a = cmb(N,2)
elif N > 1 and M > 1:
  a = cmb(N,2) + cmb(M,2)

print(int(a))
n = int(input())
AB = [[0]+list(map(int,input().split())) for _ in range(n)]
CD = [[1]+list(map(int,input().split())) for _ in range(n)]
from operator import itemgetter
points = AB.copy()
for c,d in CD:
    points.append([c+0.1,d+0.1])
points.sort(key = itemgetter(2))
points.sort(key = itemgetter(1))
temp = 0
ans = 0
for flag, x, y in points:
    if flag:
        if temp > 0:
            ans += 1
            temp -= 1
    else:
        temp += 1
print(ans)
    

### FIXED CODE ###

n = int(input())
AB = [[0]+list(map(int,input().split())) for _ in range(n)]
CD = [list(map(int,input().split())) for _ in range(n)]
from operator import itemgetter

points = AB.copy()
for c,d in CD:
    points.append([1,c,max(0,d-0.1)])
points.sort(key = itemgetter(2))

ans = 0
record = [0]*(2*n+1)
for flag, x, y in points:
    if flag:
        for i in range(x-1,-1,-1):
            if record[i] > 0:
                ans += 1
                record[i] -= 1
                break
    else:
        record[x] += 1
print(ans)
def mygcd(N,A,S):
    if S == 'R':
        A.reverse()
    ans = [0, A[0]]
    for i in range(1, N):
        ans.append(math.gcd(ans[i],A[i]))
    if S == 'R':
        ans.reverse()
    return ans

def GCDonBlack(N,A):
    L = mygcd(N,A,'L')
    R = mygcd(N,A,'R')
    M = [math.gcd(L[i], R[i+1])  for i  in range(0,N)]
    return max(M)

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

### FIXED CODE ###

import fractions
def mygcd(N,A,S):
    if S == 'R':
        A.reverse()
    ans = [0, A[0]]
    for i in range(1, N):
        ans.append(fractions.gcd(ans[i],A[i]))
    if S == 'R':
        ans.reverse()
    return ans

def GCDonBlack(N,A):
    L = mygcd(N,A,'L')
    R = mygcd(N,A,'R')
    M = [fractions.gcd(L[i], R[i+1])  for i  in range(0,N)]
    return max(M)

N = int(input())
A = list(map(int, input().split()))
print(GCDonBlack(N,A))
s = input()
odd = ["R", "U", "D"]
even = ["L", "U", "D"]

for i in range(0, len(s), 2):
    if not (s[i] in odd) and (s[i+1]):
        print("No")
        exit(0)

print("Yes")

### FIXED CODE ###

s = input()
odd = ["R", "U", "D"]
even = ["L", "U", "D"]

for i in range(len(s)):
    if i%2 == 0:
        if not s[i] in odd:
            print("No")
            exit(0)
    else:
        if not s[i] in even:
            print("No")
            exit(0)

print("Yes")
import sys
from collections import deque
import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,d = IL()
    d = d*d
    c = 0
    for _ in range(n):
        x,y = IL()
        if x*x + y*y <= d:
            c += 1

    print(c)
    exit()

### FIXED CODE ###

import sys
from collections import deque
import numpy as np
import math
sys.setrecursionlimit(10**6)
def S(): return sys.stdin.readline().rstrip()
def SL(): return map(str,sys.stdin.readline().rstrip().split())
def I(): return int(sys.stdin.readline().rstrip())
def IL(): return map(int,sys.stdin.readline().rstrip().split())

if __name__=='__main__':
    n,d = IL()
    d = d*d
    c = 0
    for _ in range(n):
        x,y = IL()
        if x*x + y*y <= d:
            c += 1

    print(c)
    exit()
#106_C
S=input()
K=int(input())
for i in range(len(S)):
    if S[i]!='1':
        ans=i
        break

print('1' if K<=ans else S[ans])

### FIXED CODE ###

#106_C
S=input()
K=int(input())
ans=0
for i in range(len(S)):
    if S[i]!='1':
        ans=i
        break

print('1' if K<=ans else S[ans])
l

### FIXED CODE ###

import bisect
import copy
import heapq
import math
import sys
from collections import *
from functools import lru_cache
from itertools import accumulate, combinations, permutations, product
def input():
    return sys.stdin.readline()[:-1]
def ruiseki(lst):
    return [0]+list(accumulate(lst))
sys.setrecursionlimit(500000)
mod=pow(10,9)+7
al=[chr(ord('a') + i) for i in range(26)]
direction=[[1,0],[0,1],[-1,0],[0,-1]]

a,b=map(int,input().split())
print(a*b)
import math, string, fractions, heapq, re, array, bisect, sys, random, time, copy
import itertools as it
import operator as op
import collections as cl
import functools as ft
import pandas as pd
import numpy as np

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))
def LF(): return list(map(float, input().split()))
def LS(): return input().split()
def I(): return int(input())
def F(): return float(input())
def S(): return input()


if __name__ != "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 3), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()
        LR[i][2] = i

    L = pd.DataFrame(LR).sort_values(0)
    R = pd.DataFrame(LR).sort_values(1)

    for _ in range(Q):
        l = L.copy()


if __name__ == "__main__":
    N, M, Q = LI()
    LR = np.ndarray((M, 3), dtype='uint32')

    for i in range(M):
        LR[i][0], LR[i][1] = LI()

    LR = pd.DataFrame(LR)

    for _ in range(Q):
        p, q = LI()
        LR[2] = p <= LR[0]
        LR[3] = LR[1] <= q
        print(sum(LR[2]*LR[3]))


### FIXED CODE ###

def LI(): return list(map(int, input().split()))
def LI_(): return list(map(lambda x: int(x) - 1, input().split()))


if __name__ == "__main__":
    N, M, Q = LI()
    LR = [[0]*(N+1) for _ in range(N+1)]
    for i in range(M):
        l, r = LI()
        LR[l][r] += 1

    # 二次元累積和
    for i in range(1, N+1):
        for j in range(1, N+1):
            LR[i][j] += LR[i][j-1]
            LR[i][j] += LR[i-1][j]
            LR[i][j] -= LR[i-1][j-1]

    for _ in range(Q):
        p, q = LI()
        p -= 1
        result = LR[q][q] - LR[p][q] - LR[q][p] + LR[p][p]
        print(result)