Harryxun/stf_run huggingface dataset:
n,m = map(int,input().split())
s = []
k = []
p = []
for i in range(m):
    q = input().split()
    k.append(int(q[0]))
    q.remove(q[0])
    s.append(q)
    #print(q)
    for j in range(k[i]):
        s[i][j] = int(q[j])
        #print(s)
    
q = input().split()
for j in range(m):
        p.append(int(q[j]))
count = 0
for i in range(pow(2,n)):
    list = []
    for o in range(n):
        list.append(i%pow(2,o+1))
        i = i // pow(2,o+1)
    #print(list)
    for j in range(m):
        wa = 0
        for l in range(k[j] ):
            wa += list[s[j][l]-1]
        if wa == p[j]*2:
            count += 1

print(count)


### FIXED CODE ###

a,p =map(int,input().split())
b = (3*a + p) // 2
print(b)
h,w=map(int,input().split())
s=[]
if h%3==0 or w%3==0:
    print(0)
else:
    for i in range(1,h):
        a=max(i*w,((h-i)*(w//2)),w*(h-i)//2)
        b=min(i*w,((h-i)*(w//2)),w*(h-i)//2)
        s.append((abs(a-b)))
    for j in range(1,w):
        a=max(h*j,(h//2)*(w-j),h*((w-j)//2))
        b=min(h*j,(h//2)*(w-j),h*((w-j)//2))
        s.append(abs(a-b))
print(min(s))

### FIXED CODE ###

h,w=map(int,input().split())
s=float('inf')
for i in range(1,h):
    a1=min(i*w,w*((h-i)//2))
    b1=max(i*w,w*(h-i-(h-i)//2))
    d1=b1-a1
    a2=min(i*w,(h-i)*(w//2))
    b2=max(i*w,(h-i)*(w-w//2))
    d2=b2-a1
    s=min(s,d1,d2)
for j in range(1,w):
    a1=min(j*h,h*((w-j)//2))
    b1=max(j*h,h*(w-j-(w-j)//2))
    d1=b1-a1
    a2=min(j*h,(w-j)*(h//2))
    b2=max(j*h,(w-j)*(h-h//2))
    d2=b2-a2
    s=min(s,d1,d2)
print(s)
N = int(input())
V = list(map(int, input().split()))

even = []
odd = []
for i in range(len(V)):
    if V[i] % 2 ==0:
        even.append(V[i])
    else:
        odd.append(V[i])

even =Counter(even)
even = list(even.items())
even = sorted(even,key=itemgetter(1),reverse = True)

odd =Counter(odd)
odd = list(odd.items())
odd = sorted(odd,key=itemgetter(1),reverse = True)

cnt = 0
if len(odd) == 0 :
    if len(even) == 1:
        cnt = N // 2
    else:
        cnt = 0
elif len(even) == 0 :
    if len(odd) == 1:
        cnt = N // 2
    else:
        cnt = 0
#書き換える数は最頻出の上位２つ以外、つまりn-(even[0][1]+even[1][1])
elif even[0][1] != odd[0][1]:
    cnt = N - (even[0][1] + odd[0][1])
elif odd[0][1] == even[0][1]:
    if even[1][1] > odd[1][1]:
        cnt = N- (odd[0][1] + even[1][1])
    elif odd[1][1] > even[1][1]:
        cnt = N- (even[0][1] + odd[1][1])

print(cnt)

### FIXED CODE ###

from collections import Counter

n = int(input())
v = list(map(int,input().split()))
ac = Counter(v[::2]).most_common(2)
bc = Counter(v[1::2]).most_common(2)



if ac[0][0] != bc[0][0]:            #奇数列と偶数列の最頻数が同じ要素でない場合
    ans =  n - ac[0][1] - bc[0][1]  #全体の数から書き換える必要がない数（それぞれの最頻値）を引けばよい
else:                               #奇数列と偶数列の最頻数が同じ要素の数の場合
    if len(bc) == 1 or len(ac) == 1:#全部同じ数の場合 
        ans = n // 2
    else: #２番目の最頻数を比較し、大きいほうの列の最も多大きい最頻数ともう一方の列の2番目に大きい最頻数を書き換える
        ans = n - max(ac[0][1] + bc[1][1], ac[1][1] + bc[0][1])
print(ans)
while True:
    n = int(input())
    if not n:
        break
    a = [list(map(int, input().split())) for j in range(n)]
    c = [max(a[i][j] for i in range(n)) for j in range(n)]
    r = [min(a[i]) for i in range(n)]

    print([c[j] for i in range(n) for j, x in enumerate(a[i]) if x == r[i] and c[j] == r[i]][0])

### FIXED CODE ###

while True:
    n = int(input())
    if not n: break
    a = [list(map(int, input().split())) for _ in range(n)]
    s = max(min(a[i]) for i in range(n))
    c = [max(a[i][j] for i in range(n)) for j in range(n)]
    for j in range(n):
        if c[j] == s:
            print(s)
            break
    else:
        print(0)
N = int(input())
num_lists = list(map(int, input().split))
ans = - 1

for i in num_lists:
  for j in num_lists:
    diff = abs(i - j)
    if diff > ans:
      ans = diff

print(ans)

### FIXED CODE ###

N = int(input())
num_lists = list(map(int, input().split()))
max_num = max(num_lists)
min_num = min(num_lists)
ans = max_num - min_num
print(ans)
S=input()
N=len(S)
S1=list(S[0:(N-1)//2])
S2=list(S[(N+3)//2-1:])
if(len(S1)%2==1):
    S1.pop(len(S1)//2)

if(len(S2)%2==1):
    S2.pop(len(S2)//2)

for i,s in enumerate((S1)):
    if(s!=S1[-1-i]):
        print('No')
        sys.exit()

for i,s in enumerate((S2)):
    if(s!=S2[-1-i]):
        print('No')
        sys.exit()
        
print('Yes')

### FIXED CODE ###

import sys
S=input()
N=len(S)
S1=list(S[0:(N-1)//2])
S2=list(S[(N+3)//2-1:])
S=list(S)
S.pop(N//2)
if(len(S1)%2==1):
    S1.pop(len(S1)//2)

if(len(S2)%2==1):
    S2.pop(len(S2)//2)

for i,s in enumerate(S):
    if(s!=S[-1-i]):
        print('No')
        sys.exit()

for i,s in enumerate(S1):
    if(s!=S1[-1-i]):
        print('No')
        sys.exit()

for i,s in enumerate(S2):
    if(s!=S2[-1-i]):
        print('No')
        sys.exit()
        
print('Yes')
while 1:
	H,W=map(int,raw_input().split())
	if H==0 and W==0:
		break
	for i in H:
		print "#"*W 
		print "/n"

### FIXED CODE ###

while 1:
	H,W=map(int,raw_input().split())

	if H==0 and W==0:
		break

	for i in range(H):
		print "#"*W 
	print ""
def ceil(n): # ceiling関数
    if n > int(n):
        return(int(n)+1)
    else:
a,b = map(int,input().split())
print(ceil(a+B/2))


### FIXED CODE ###

def ceil(n): # ceiling関数
    if n > int(n):
        return(int(n)+1)
    else:
        return(int(n))
a,b = map(int,input().split())
print(ceil((a+b)/2))
a,b,c=map(int, input().split())
if a<b and b<c:
	print(‘Yes’)
else:
	print(’No’)



### FIXED CODE ###

a,b,c=map(int, input().split())
if a<b and b<c :
	print("Yes")
else:
	print("No")
a=input()
a=a.split()
x=int(a[0])
p=input()
p=p.split()

i=0
p_1=p+[]



for y in p_1:
  p_1[i]=abs(int(p_1[i])-x)
  i=i+1

p_1.sort()
if p_1[0]==0:
  del p_1[0]

q=p_1[0]
if str(x-q) in p:
  print(x-q)
else:
  print(x+q)






### FIXED CODE ###

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

for y in range(x+1):
  for b in[-1,1]:
    c=x+y*b
    if a.count(c)==0:
      print(c)
      exit(0)
h, w = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]
A = [list(map(int, input().split())) for i in range(h)]

# C[i][j]はiをjにするのに必要なコスト
# warshal-floyd
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
for i in range(10):
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == -1:
            ans += 0
        else:
            ans += C[A[i][j]][1]
print(ans)


### FIXED CODE ###

h, w = map(int, input().split())
C = [list(map(int, input().split())) for i in range(10)]
A = [list(map(int, input().split())) for i in range(h)]

# C[i][j]はiをjにするのに必要なコスト
# warshal-floyd
for k in range(10):
    for i in range(10):
        for j in range(10):
            C[i][j] = min(C[i][j], C[i][k] + C[k][j])
ans = 0
for i in range(h):
    for j in range(w):
        if A[i][j] == -1:
            ans += 0
        else:
            ans += C[A[i][j]][1]
print(ans)
n = int(input())
l = []
for i in range(n):
    l.append(int(input())
           
for j in range(n):
	print(max(l[:i]+l[i+1:]))        

### FIXED CODE ###

n = int(input())
l = []
for i in range(n):
	l.append(int(input()))
           
s = sorted(l, reverse=True)
      
for value in l:
    if value == s[0]:
        print(s[1])
    else:
        print(s[0])
# -*- coding:utf-8 -*-

def cmb(n, r):
    if n == 0 or r == 0:
        return 1
    a = b = 1
    for i in range(1, r + 1):
        print(r,i)
        a *= i
    for i in range(n-r+1,n+1):
        b *= i
    return b//a

N = list(map(int,input().split()))
M = 10**9 + 7
red = N[0]-N[1]
for i in range(1,N[1]+1):
    x = cmb(red + 1, i) * cmb(N[1] - 1,i-1)
    print(x%M)


### FIXED CODE ###

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

a = list(input())
dic = {}
for x in a:
    dic.setdefault(x, 0)
    dic[x] += 1
if (len(dic) == 2):
    if(dic[a[0]]==2):
        print("Yes")
    else:
        print("No")
else:
    print("No")
W,H,x,y,r=map(int,input().split())
print x+r<W&&r<x&&r<y&&y+r<H?"Yes":"No"

### FIXED CODE ###

W,H,x,y,r=map(int,input().split())
if not (x+r>W or r>x or r>y or y+r>H):print("Yes")
else:print("No")
n,k=map(int,input().split())
cnt=0
while n>0:
    n=n//k
    cnt+=1
print(cnt)

### FIXED CODE ###

n,r=map(int,input().split())
print(r+100*(10-n) if n<10 else r)
import sys

sys.setrecursionlimit(10000)

N, M = map(int, input().split())
A = []

for _ in range(M):
    a = int(input())
    A.append(a)

d = {}


def f(x):
    # print(d)
    if x in A:
        return 0
    if x > N:
        return 0
    if x == N:
        return 1

    if d.get(x):
        return d[x]

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2
    #
    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    d[x] = ans
    return ans


print(f(0) % 1000000007)


### FIXED CODE ###

import sys

sys.setrecursionlimit(1000000)

N, M = map(int, input().split())
A = []
ANS = []
for i in range(N + 10):
    ANS.append(None)

for _ in range(M):
    a = int(input())
    A.append(a)
    ANS[a] = 0


def f(x):
    # print(ANS)
    # if x in A:
    #     print('::::', x)
    #     d[x] = 0
    #     return 0
    if ANS[x] is not None:
        return ANS[x]

    if x > N:
        return 0
    if x == N:
        return 1

    # if d.get(x + 1):
    #     x1 = d.get(x + 1)
    # else:
    #     x1 = f(x + 1)
    #     d[x + 1] = x1
    #
    # if d.get(x + 2):
    #     x2 = d.get(x + 2)
    # else:
    #     x2 = f(x + 2)
    #     d[x + 2] = x2

    # ans = x1 + x2
    ans = f(x + 1) + f(x + 2)
    ANS[x] = ans
    return ans


print(f(0) % 1000000007)
import math 

A,B=(int(i)for i in input().split())

print((A * B) // math.gcd(A, B))


### FIXED CODE ###

import fractions 

A,B=(int(i)for i in input().split())

print((A * B) // fractions.gcd(A, B))
s = sorted(input())
t = sorted(input()).reverse()
print("Yes" if s < t else "No")


### FIXED CODE ###

s = sorted(input())
t = sorted(input())[:: -1]
print("Yes" if s < t else "No")
n=int(input())
abc = [list(map(int, input().split())) for i in range(n)]
#[[10,40,70],[20,50,80],[30,60,90]]
ABC=[[0,0,0]]
#A = [0]
#B = [0]
#C = [0]
for i in range(n):
  a = abc[i][0] + max(B[-1], C[-1])#10+max(0,0),20+max(40,70)=90,30+max(120,120)=150
  b = abc[i][1] + max(A[-1], C[-1])#40+max(0,0),50+max(10,70)=120,60+max(90,120)=180
  c = abc[i][2] + max(A[-1], B[-1])#70+mac(0,0),80+max(10,40)=120,90+max(90,120)=210
  ABC += [[a,b,c]]
  #A += [a]#0,10,90,150
  #B += [b]#0,40,120,180
  #C += [c]#0,70,120,210
print(max(ABC[-1])

### FIXED CODE ###

n=int(input())
abc = [list(map(int, input().split())) for i in range(n)]
#[[10,40,70],[20,50,80],[30,60,90]]
A = [0]
B = [0]
C = [0]
for i in range(n):
  a = abc[i][0] + max(B[-1], C[-1])#10+max(0,0),20+max(40,70)=90,30+max(120,120)=150
  b = abc[i][1] + max(A[-1], C[-1])#40+max(0,0),50+max(10,70)=120,60+max(90,120)=180
  c = abc[i][2] + max(A[-1], B[-1])#70+mac(0,0),80+max(10,40)=120,90+max(90,120)=210
  A += [a]#0,10,90,150
  B += [b]#0,40,120,180
  C += [c]#0,70,120,210
print(max(A[-1], B[-1], C[-1]))
N,K = map(int,input().split())
h = list(map(int,input().split()))

costs = [0] * N
for i in range(1,N):
  _h = h[i]
  s = 0
  if i > K:
    s = i-K
  mn = float('inf')
  for a,b in zip(costs[s:i],h[s:i]):
    cur = a + abs(_h-b)
    if cur < mn:
      mn = cur
 
  costs[i] = mn
print(costs[-1])

### FIXED CODE ###

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

costs = [0] * N
costs[0] = 0
costs[1] = abs(h[1] - h[0])
for i in range(2,N):
  tmp1 = costs[i-2] + abs(h[i] - h[i-2])
  tmp2 = costs[i-1] + abs(h[i] - h[i-1])
  costs[i] = min(tmp1,tmp2)
print(costs[N-1])
import math

class Input():
	def readInt(self):
		return int(input())

	def readIntArray(self):
		return [int(x) for x in input().split(" ")]

	def readString(self):
		return input()

	def readStringArray(self):
		return input().split(" ")

	def readFloat(self):
		return float(input())

	def readFloatArray(self):
		return [float(x) for x in input().split(" ")]

def main():
	inp = Input()
	n, k = inp.readIntArray()
	height = inp.readIntArray()

	cost = [math.inf for i in range(n)]
	cost[0] = 0

	for i in range(n):
		for j in range(1, k+1):
			if (i + j) < n:
				# print(f"j = {j}")
				cost[i+j] = min(cost[i+j], cost[i] + abs(height[i+j] - height[i]))
		# print(f"i = {i}", cost)

	print(cost[n-1])
	

if __name__ == "__main__":
   main()


### FIXED CODE ###

n, k = [int(x) for x in input().split()]
h = [int(x) for x in input().split()]

def abs(x):
    if x >= 0:
        return x
    return -x

c = [0]
c.append(abs(h[1] - h[0]))
for i in range(2, n):
    cmin = None
    for cur in range(i-1, i-1-k, -1):
        if cur < 0:
            break
        val = abs(h[i] - h[cur]) + c[cur]
        if cmin is None or val < cmin:
            cmin = val
    c.append(cmin)

print(c[-1])
n,k=map(int,input().split())
if(n>k):
    if(n%k==0):
        print(0)
    else:
        print(min((n%k),(n//k+1)*k-n))
elif(n==k):
    print(0)
else:
    if(k%n==0):
        print(n)
    else:
        if(k-n)<=n:
            print(k-n)
        else:
            print(n)


### FIXED CODE ###

n,k=map(int,input().split())
if(n>k):
    if(n%k==0):
        print(0)
    else:
        print(min((n%k),(n//k+1)*k-n))
elif(n==k):
    print(0)
elif(n==0):
    print(0)
else:
    if(k%n==0):
        print(n)
    else:
        if(k-n)<=n:
            print(k-n)
        else:
            print(n)
input = input()
return input ** 2

### FIXED CODE ###

input = int(input())
print(input ** 3)
#include <bits/stdc++.h>
using namespace std;

int main()
{
    int N, Y;
    cin >> n >> sum;

    int res;
    for(int x = 0; x <= n; x++){
        for(int y = 0; y <= n - x; y++){
            int z = n - x - y;
            res = 10000 * x + 5000 * y + 1000 * z;
            if(res == sum)
                cout << x << ' ' << y << ' ' << z << endl;
            else
                cout << -1 << ' ' << -1 << ' ' << -1 << endl;
        }
    }
}


### FIXED CODE ###

N, sum = [int(i) for i in input().split()]

for x in range(N+1):
	for y in range(N+1 - x):
		z = N - x - y
		if 10000*x + 5000*y + 1000*z == sum:
			print(x, y, N - x - y)
			exit()
print(-1, -1, -1)
sum = 0
n = int(input())
l = [list(map(int, input().split())) for i in range(3)]

for i in range(n-1):
  sum = sum + l[1][i]
  if l[0][i+1] - l[0][i] == 1:
    sum = sum + l[2][l[0][i]]
sum = sum + l[1][n-1]
print(sum)

### FIXED CODE ###

sum = 0
n = int(input())
l = [list(map(int, input().split())) for i in range(3)]

for i in range(n-1):
  sum = sum + l[1][i]
  if l[0][i+1] - l[0][i] == 1:
    sum = sum + l[2][l[0][i]-1]
sum = sum + l[1][n-1]
print(sum)
A,B,C,D = map(int, input().split())
if D<A or B<C: print("0")
elif A<C and D<B: print(D-C)
elif C<A and B<D: print(B-A)
elif D-A < B-C: print(D-A)
else: print(B-C)

### FIXED CODE ###

N = input()
if N[0] == N[2]: print("Yes")
else: print("No")
from heapq import heappush,heappop
n,m=map(int,input().split())
a,b,c=[None]*n,[None]*n,[None]*n
inf=float("inf")
d=[inf]*n

for i in range(m):
  a[i],b[i],c[i]=map(int,input().split())
  c[i]=-c[i]

d[0]=0
for loop in range(n-1):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
      
ans=-d[n-1]
neg=[False]*n
for loop in range(n):
  for i in range(m):
    if d[a[i]-1]==inf:continue
    if d[b[i]-1]>d[a[i]-1]+c[i]:
      d[b[i]-1]=d[a[i]-1]+c[i]
      neg[b[i]-1]=True
    if neg[a[i]-1]:
      neg[b[i]-1]=True

if neg[n-1]:
  print("inf")
else:
  print(ans)

### FIXED CODE ###

n,m=map(int,input().split())
inf=float("inf")
l=[tuple(map(int,input().split())) for i in range(m)]
 
d=[inf]*n
d[0]=0

for i in range(n):
  for a,b,c in l:
    a,b,c=a-1,b-1,-c
    if d[a]!=inf and d[b]>d[a]+c:
      d[b]=d[a]+c
      if i==n-1 and b==n-1:
        print("inf")
        exit()
print(-d[-1])
n = int(input())
a = [i in int(input().split()))]
for  i in range(1,n+1):
    v  = a[i]
    j = i-1
    while a[j]>a[j+1] and j>0:
        a[j] = v
        j -=1
    a[j+1] = 
    print(*a)


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
for  i in range(n):
    v  = a[i]
    j = i-1
    while a[j]>v and j>=0:
        a[j+1] = a[j]
        j -=1

    a[j+1] = v
    print(*a)
x,n = map(int,input().split())
mp = set(range(1,101))
p = set(list(map(int,input().split())))
lp = list(mp-p)
sub_lp = [abs(i-x) for i in lp]
print(lp[sub_lp.index(min(sub_lp))])

### FIXED CODE ###

x,n = map(int,input().split())
if n == 0:
    print(x)
else:
    mp = set(range(-1,102))
    p = set(list(map(int,input().split())))
    lp = list(mp-p)
    sub_lp = [abs(i-x) for i in lp]
    print(lp[sub_lp.index(min(sub_lp))])
s1,s2,s3 = input().split()

s1 = s1[0:1].upper
s2 = s2[0:1].upper
s3 = s3[0:1].upper
print(s1 + s2 + s3)

### FIXED CODE ###

s1,s2,s3 = input().split()

s1 = str(s1[0:1].upper())
s2 = str(s2[0:1].upper())
s3 = str(s3[0:1].upper())
print(s1 + s2 + s3)
x = raw_input()
y = raw_input()

x = int(x)
y = int(y)

print x * y 2 * x + 2 * y 

### FIXED CODE ###

length = raw_input()
a, b = length.split()

a = int(a)
b = int(b)

print a * b, 2 * (a + b)
A, B, C, K = map(int, input().split())
sum = 0

if K >= A:
	sum = A
	K = K - A
else:
	sum = K
	K = 0
if K >= B and K >= 1:
	K = K - B
else:
	K = 0
if K >= C and K >= 1:
	sum = sum - C
else:
	sum = sum - K

if sum >= 1:
	print(sum)
else:
	print(0)

### FIXED CODE ###

S = input()
T = input()

if S == T[:-1]:
	print("Yes")
else:
	print("No")
a,b,k=map(int,input().split())
m=max(a,b)
ans=[]
for i in range(1,m):
  if a%i==0 and b%i==0:
    ans.append(i)
ans.reverse()
print(ans[k-1])

### FIXED CODE ###

a,b,k=map(int,input().split())
inte=[];mini=min(a,b);j=1
for i in range(1,mini+1):
  if a%i==0 and b%i==0:
    inte.append(i)
inte.sort(reverse=True)
print(inte[k-1])
N=int(input())
S=input()
result=0
for i in range(N):
  if [i:i+3]=='ABC':
    result+=!
print(result)


### FIXED CODE ###

N=int(input())
S=input()
result=0
for i in range(N):
  if S[i:i+3]=='ABC':
    result+=1
print(result)
# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import numpy as np
import bisect

N , Z ,W = input().split()
N = int(N)
Z = int(Z)
W = int(W)
a = input().split()
a = [int(i) for i in reversed(a)]

rst = [ np.abs(W - a[0]) , np.abs(a[1] - a[0]) ]
print(np.max(rst))

### FIXED CODE ###

# coding: utf-8
# Here your code !
#!/usr/bin/env python3
# -*- coding: utf-8 -*-
 
import numpy as np
import bisect

N , Z ,W = input().split()
N = int(N)
Z = int(Z)
W = int(W)
a = input().split()
a = [int(i) for i in reversed(a)]

if N == 1 : 
    print(np.abs(W - a[0]))
else : 
    rst = [ np.abs(W - a[0]) , np.abs(a[1] - a[0]) ]
    print(np.max(rst))
N, M, Q = map(int, input().split())
    rail = []
    for i in range(M):
        r = list(map(int, input().split()))
        rail.append(r)
     
    query = []
    for i in range(Q):
        q = list(map(int, input().split()))
        query.append(q)
     
    f = [[0 for i in range(N)] for j in range(N)]
    g = [[0 for i in range(N)] for j in range(N)]
     
    for i in range(M):
        f[rail[i][0]-1][rail[i][1]-1] += 1
     
    for i in range(N):
        j = 0
        while j + i < N:
            if i == 0:
                g[j][j+i] = f[j][j+i]
            else:
                g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
            j += 1
     
    for i in range(Q):
        print(g[query[i][0]-1][query[i][1]-1])

### FIXED CODE ###


N, M, Q = map(int, input().split())
rail = []
for i in range(M):
    r = list(map(int, input().split()))
    rail.append(r)
 
query = []
for i in range(Q):
    q = list(map(int, input().split()))
    query.append(q)
 
f = [[0 for i in range(N)] for j in range(N)]
g = [[0 for i in range(N)] for j in range(N)]
 
for i in range(M):
    f[rail[i][0]-1][rail[i][1]-1] += 1
 
for i in range(N):
    j = 0
    while j + i < N:
        if i == 0:
            g[j][j+i] = f[j][j+i]
        else:
            g[j][j+i] = f[j][j+i] + g[j+1][j+i] + g[j][j+i-1] - g[j+1][j+i-1]
        j += 1
 
for i in range(Q):
    print(g[query[i][0]-1][query[i][1]-1])
S=list(map(int.input().split()))
T=list(map(int.input().split()))
int x = 0

for i in range(3):
  if S[i] == T[i]:
    x += 1
print(x)


### FIXED CODE ###

S=input()
T=input()
x = 0
for i in range(3):
  if S[i] == T[i]:
    x += 1
print(x)
S = list(input())
S.sort()
if (S[0] == S[1]) and (S[2] == S[3]):
  print(Yes)
else:
  print(No)

### FIXED CODE ###

S = list(input())
S.sort()
if (S[0] == S[1]) and (S[2] == S[3]) and (S[1] != S[2]):
  print('Yes')
else:
  print('No')
S = list(input())
print(S[:3]+"8"+S[4:])

### FIXED CODE ###

S = input()
print(S[:3]+"8"+S[4:])
k = int(input())

i = 0
lun_ls = [1, 2, 3, 4, 5, 6, 7, 8, 9]
n = 0
while n < 9991:
  i += 1
  s = str(i)
  for j in range(len(s)-1):
    if (int(s[j]) - int(s[j+1])) not in [-1, 0, 1]:
      break
    else:
      lun_ls.append(i)
      n += 1

print(lun_ls[k-1])

### FIXED CODE ###

from collections import deque
 
k = int(input())
q = deque([1, 2, 3, 4, 5, 6, 7, 8, 9])
 
for i in range(k):
  a = q.popleft()
  if a % 10 == 0:
    q.append(10*a)
    q.append(10*a + 1)
  elif a % 10 == 9:
    q.append(10*a + 8)
    q.append(10*a + 9)
  else:
    q.append(10*a + a%10 - 1)
    q.append(10*a + a%10)
    q.append(10*a + a%10 + 1)
else:
  print(a)
Pat=[1]
for p in range(51):
    Pat.append(Pat[p]*2+1)
    
All=[1]
for a in range(51):
    All.append(All[a]*2+3)
    
N,X=map(int,input().split())
    
def saiki(n,x):
    if n==0:
        if x<=0:
            return 0
        else:
            return 1
    elif x<n:
        return 0
    elif x<(All[n]+1)//2-1:
        return saiki(n-1,x-1)
    elif x==(All[n-1]+2):
        return Pat[n-1]+1
    elif x<All[n]:
        return Pat[n-1]+1+saiki(n-1,x-2-All[n-1])
    
print(saiki(N,X))

### FIXED CODE ###

Pat=[1]
All=[1]
for i in range(51):
    Pat.append(Pat[i]*2+1)
    All.append(All[i]*2+3)

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

def saiki(N,X):
    if N==0:
        if X<=0:
            return 0
        else:
            return 1
    elif X<=All[N-1]+1:
        return saiki(N-1,X-1)
    elif X<=All[N]-1:
        return Pat[N-1]+1+saiki(N-1,X-2-All[N-1])
    else:
        return Pat[N]
        
print(saiki(N,X))
def d_make_them_even(H, W, A):
    from itertools import product
    # グリッドを -1 の壁で包む
    wall = [[-1] * (W + 2)]
    grid = wall + [[-1] + row + [-1] for row in A] + wall

    ans_tmp = []
    for h, w in product(range(H), range(W)):
        if grid[h][w] % 2 == 1:
            # コイン1枚をグリッドの右か下に押し付ける
            for dh, dw in zip((0, 1), (1, 0)):
                nh, nw = h + dh, w + dw
                if grid[nh][nw] != -1:
                    grid[nh][nw] += 1
                    grid[h][w] -= 1
                    ans_tmp.append('{0} {1} {2} {3}'.format(h + 1, w + 1, nh + 1, nw + 1))
                    break
    ans = '\n'.join([str(len(ans_tmp)), *ans_tmp])
    return ans

H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_make_them_even(H, W, A))

### FIXED CODE ###

def d_make_them_even(H, W, A):
    board = [row for row in A]
    ans = []
    for h in range(H):
        for w in range(W):
            if board[h][w] % 2 == 1:
                for nh, nw in zip((0, 1), (1, 0)):
                    if 0 <= h + nh <= H - 1 and 0 <= w + nw <= W - 1:
                        board[h + nh][w + nw] += 1
                        board[h][w] -= 1
                        ans.append('{0} {1} {2} {3}'.format(h + 1, w + 1, h + nh + 1, w + nw + 1))
                        break
    ans.insert(0, str(len(ans)))
    ans = '\n'.join(ans)
    return ans

H, W = [int(i) for i in input().split()]
A = [[int(i) for i in input().split()] for j in range(H)]
print(d_make_them_even(H, W, A))
import sys
x, y = map(int,sys.stdin.readline().split())
cnt = 0
while x <= y:
    cnt += 1
    x *= 2
print(cnt)


### FIXED CODE ###

import sys
a, b, c, d = map(int, sys.stdin.readline().split())
if a+b > c+d:
    print('Left')
elif a+b == c+d:
    print('Balanced')
else:
    print('Right')