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

# encoding: utf-8


class Solution:
    @staticmethod
    def binary_search():
        array_length_1 = int(input())
        array_1 = [int(x) for x in input().split()]
        array_length_2 = int(input())
        array_2 = [int(x) for x in input().split()]

        # print(len(set(array_1).intersection(set(array_2))))
        left, right, count = 0, array_length_1, 0
        for each in array_2:
            while left < right:
                mid = int((left + right) / 2)
                if array_1[mid] == each:
                    count += 1
                elif each < array_1[mid]:
                    right = mid
                else:
                    left = mid + 1

        print(count)


if __name__ == '__main__':
    solution = Solution()
    solution.binary_search()

### FIXED CODE ###

# encoding: utf-8


import sys


class Solution:
    def __init__(self):
        """
        init input array
        """
        self.__input = sys.stdin.readlines()

    @property
    def solution(self):
        length_1 = int(self.__input[0])
        array_1 = list(map(int, self.__input[1].split()))
        length_2 = int(self.__input[2])
        array_2 = list(map(int, self.__input[3].split()))

        assert length_1 == len(array_1) and length_2 == len(array_2)

        count = 0

        for each in array_2:
            if self.binary_search(key=each, array=array_1, array_length=length_1):
                count += 1

        return str(count)

    @staticmethod
    def binary_search(key, array, array_length):
        # print(len(set(array_1).intersection(set(array_2))))
        left, right = 0, array_length
        while left < right:
            mid = (left + right) // 2
            if key == array[mid]:
                return True
            elif key < array[mid]:
                right = mid
            else:
                left = mid + 1
        return False


if __name__ == '__main__':
    case = Solution()
    print(case.solution)
### BUGGY CODE ###

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

for i in range(n):
	b.append(a[i])
	b.reverse()

print(*b)


### FIXED CODE ###

from collections import deque

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

b = deque()

for i in range(n):
    if (i+1) %2 == n % 2:
        b.appendleft(a[i])
    else:
        b.append(a[i])
ans = list(b)
print(*ans)
### BUGGY CODE ###

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

while abs(N-K) <= N:
  N=abs(N-K)
print(N)

### FIXED CODE ###

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

t=N%K
ans=min(t,K-t)
print(ans)
### BUGGY CODE ###

S=list(input())
T=list(input())
N=len(S)

i=-1
for t in T:
  if t in set(S[(i+1)%N:]):
    i+=S[(i+1)%N:].index(t)+1
  elif t in set(S[:(i+1)%N]):
    i+=len(S[(i+1)%N:])+S.index(t)+1
  else:
    print(-1)
    exit()

print(i+1)


### FIXED CODE ###

import bisect
S=list(input())
T=list(input())
sT=set(T)
N=len(S)
TI={}
for i in range(N):
  s=S[i]
  if s in sT:
    if s in TI:
      TI[s].append(i)
    else:
      TI[s]=[i]

i=-1
for t in T:
  if t not in TI:
    print(-1)
    exit()
  else:
    ni=TI[t][(bisect.bisect_right(TI[t],i%N))%len(TI[t])]
    if ni>i%N:
      i+=ni-i%N
    else:
      i+=N-i%N+ni
print(i+1)
### BUGGY CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(h)]
    B=[list(map(int,input().split())) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    dp[0][0]|=1<<x

    from itertools import product
    for i,j in product(range(h),range(w)):
        x=abs(A[i][j]-B[i][j])
        if(i-1>=0):
            for y,s in enumerate(bin(dp[i-1][j])[:1:-1]):
                if(s=='1'):
                    dp[i][j]|=1<<(y+x)
                    dp[i][j]|=1<<(abs(y-x))
        if(j-1>=0):
            for y,s in enumerate(bin(dp[i][j-1])[:1:-1]):
                if(s=='1'):
                    dp[i][j]|=1<<(y+x)
                    dp[i][j]|=1<<(abs(y-x))

    for i,s in enumerate(bin(dp[-1][-1])[:1:-1]):
        if(s=='1'):
            print(i)
            return
resolve()

### FIXED CODE ###

import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
def resolve():
    h,w=map(int,input().split())
    A=[list(map(int,input().split())) for _ in range(h)]
    B=[list(map(int,input().split())) for _ in range(h)]
    dp=[[0]*w for _ in range(h)]
    x=abs(A[0][0]-B[0][0])
    offset=12800
    dp[0][0]|=1<<(x+offset)
    dp[0][0]|=1<<(-x+offset)

    from itertools import product
    for i,j in product(range(h),range(w)):
        if(i==0 and j==0): continue
        x=abs(A[i][j]-B[i][j])
        S=0
        if(i>0): S|=dp[i-1][j]
        if(j>0): S|=dp[i][j-1]
        dp[i][j]=(S<<x)|(S>>x)

    for i in range(12800):
        if((dp[-1][-1]>>(i+offset))&1):
            print(i)
            return
resolve()
### BUGGY CODE ###

n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

points=[k]*n
for a in A:
  for i in range(n):
    if a-1==i:
      pass
    else:
      points[i]-=1
for p in points:
  if p<=0:
    print('No')
  else:
    print('Yes')

### FIXED CODE ###

import sys
import itertools
input = sys.stdin.readline
n,k,q=map(int,input().split())
A=[int(input()) for _ in range(q)]

ans=[k]*n
for i in range(q):
  ans[A[i]-1]+=1
for i in range(n):
  if ans[i]-q>0:
    print('Yes')
  else:
    print('No')
### BUGGY CODE ###

import sys
n=int(input())
a=[0]+[list(map(int,sys.stdin.readline().strip().split()[::-1])) for _ in range(n)]

pairs=n*(n-1)//2
ans=0

while pairs>0:
    ans+=1
    tpairs=0
    dic={}

    for i in range(1,n+1):
        if len(a[i])==0:
            continue
        lasta=a[i][-1]
        p=(min(i,lasta),max(i,lasta))

        if p in dic:
            dic[p]+=1
        else:
            dic[p]=1

    for (i,j),v in dic.items():
        if v==1:
            continue

        a[i].pop()
        a[j].pop()
        tpairs+=1
    
    if tpairs==0:
        print(-1)
        break

    pairs-=tpairs
else:
    print(ans)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**6)

n=int(input())
g=[set() for _ in range(n*(n-1)//2+1)]
visit=[0]*(n*(n-1)//2+1)
d=[0]*(n*(n-1)//2+1)

for i in range(1,n+1):
    last=0
    for j in list(map(int,input().split())):
        mi,ma=(min(i-1,j-1),max(i-1,j-1))
        current=ma*(ma-1)//2+mi+1
        g[last].add(current)
        last=current

def dfs(u):
    if visit[u]==2:
        return d[u]
    
    ans=0
    visit[u]=1
    for v in g[u]:
        if visit[v]==1:
            print(-1)
            exit(0)
        
        d[u]=max(d[u],1+dfs(v))
    
    visit[u]=2
    return d[u]

print(dfs(0))
### BUGGY CODE ###

item = [i for i in input()]
n = int(input())
for i in range(n):
    tmp = input()
    if tmp[0] == '1':
        item.reverse()
    else:
        _, q, s = tmp.split()
        if q == '1':
            item = [s] + item
        else:
            item += [s]
print(''.join(item))


### FIXED CODE ###

from collections import deque


def main():
    item = deque([i for i in input()])
    n = int(input())
    flag = 0
    append = item.append
    for i in range(n):
        tmp = input()
        if tmp[0] == '1':
            flag += 1
            continue

        _, q, s = tmp.split()
        if q == '1' and flag % 2 == 0:
            item.appendleft(s)
            continue
        elif q == '2' and flag % 2 == 1:
            item.appendleft(s)
            continue
        append(s)

    if flag % 2 == 1:
        item.reverse()
    print(''.join(item))

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

L, R = map(int, input().split())

tmp = []
if L+2019 < R:
    for i in range(L+1, L+2019+1):
        for j in range(L, R+1):
            if i == j:
                continue
            tmp.append(i * j % 2019)
else:
    for i in range(L, R+1):
        for j in range(L, R+1):
            if i == j:
                continue
            tmp.append((i * j) % 2019)

print(min(tmp))

### FIXED CODE ###

L, R = map(int, input().split())

tmp = []
if L + 2019 < R:
    for i in range(L, L+2019+1):
        for j in range(L, L+2019+1):
            if i == j:
                continue
            tmp.append(i * j % 2019)
else:
    for i in range(L, R+1):
        for j in range(L, R+1):
            if i == j:
                continue
            tmp.append((i * j) % 2019)

print(min(tmp))
### BUGGY CODE ###

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

B = [0] * N
for i in reversed(range(N)):
    ball = 0
    base = i + 1

    for j in range(1, N + 1):
        if ball * j - 1 >= N:
            break
        ball += B[ball * j - 1]

    if ball % 2 != A[i]:
        B[i] = 1

print(sum(B))
print(*[i for i, b in enumerate(B, start=1) if b == 1], sep=' ')


### FIXED CODE ###

N = int(input())
A = [0] + list(map(int, input().split()))

B = [0] * (N + 1)

for i in reversed(range(1, N + 1)):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += B[j]

    if tmp % 2 != A[i]:
        B[i] = 1

for i in range(1, N + 1):
    tmp = 0
    for j in range(i, N + 1, i):
        tmp += B[j]
    if A[i] != tmp % 2:
        print(-1)
        exit()

print(sum(B))
ans = []
for i, b in enumerate(B):
    if b == 1:
        ans.append(i)
if len(ans) > 0:
    print(*ans, sep=' ')
### BUGGY CODE ###

import math
from itertools import product
K = int(input())
cc = [i for i in range(1,K+1)]
count = 0
for i in product(cc,repeat = 3):
  aa = i[0]
  for j in [1,2]:
    aa = math.gcd(aa,i[j])
  count += aa
print(count)

### FIXED CODE ###

from math import gcd
K = int(input())
count = 0
for i in range(1,K+1):
  for j in range(1,K+1):
    for k in range(1,K+1):
      count += gcd(gcd(i,j),k)
print(count)
### BUGGY CODE ###

n = int(input())

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

ans = 1

flag_0 = False

for a_i in a:
    
    if a_i == 0:
        flag_0 = True
        break

    ans *= a_i
    
    if ans > 10**18:
        ans = -1
        
if flag_0 == True:
    print(0)
elif ans <0:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input())

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

ans = 1

flag_0 = False

if 0 in a:
    print(0)
else:
    for a_i in a:
        ans *= a_i
        if ans > 10**18:
            ans = -1
            break
    print(ans)
### BUGGY CODE ###

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

islow = True
counter = 0
min = 0

for i in range(len(plist)):
    islow = True
    if i == 0:
        counter += 1
        min = plist[i]
        current_min = i
    elif min > plist[i]:
        for j in range(current_min, plist.index(plist[i])):
            if plist[i] <= plist[j]:
                pass
            else:
                islow = False
                break
        if islow:
            counter += 1
            min = plist[i]
            current_min = i
            
print(counter)

### FIXED CODE ###

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

islow = True
counter = 0
min = 0

for i in range(len(plist)):
    islow = True
    if i == 0:
        counter += 1
        min = plist[i]
        current_min = i
    elif min > plist[i]:
        counter += 1
        min = plist[i]
        current_min = i
        
print(counter)
### BUGGY CODE ###

import math 

K = int(input())
mymemo =  [ [float('INF') for k in range(K+1) ] for kk in range(K+1) ]
#print(mymemo)

mysum = 0
for a in range(1,K+1):
    for b in range(1,K+1):
        for c in range(1,K+1):
            if mymemo[a][b] != float('INF'):
                mygcd = mymemo[a][b]
            else:
                mygcd = math.gcd(a,b)
                mymemo[a][b] = mygcd
            if mymemo[mygcd][c] != float('INF'):
                mygcd2 = mymemo[mygcd][c]
            else:
                mygcd2 = math.gcd(mygcd,c)
                mymemo[mygcd][c] = mygcd2
            mysum += mygcd2
            #print(a, b,c, mygcd)
            #print(mymemo)
print(mysum)


### FIXED CODE ###

import math 
import functools

K= int(input())
gcd_list = [ [float('INF') for i in range(K+1)] for j in range(K+1)]
#print(gcd_list)

for i in range(1,K+1):
    for j in range(1, K+1):
        gcd_list[i][j] = math.gcd(i,j)
#for g in gcd_list:
    #print(g)
mysum = 0
for i in range(1,K+1):
    for j in range(1,K+1):
        mygcd = gcd_list[i][j]
        for k in range(1,K+1):
            mygcd2 = math.gcd(mygcd, k)
            mysum += mygcd2 
        
print(mysum)
### BUGGY CODE ###

import numpy as np
import math
from functools import lru_cache

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
x = np.array(x)
h = np.array(h)

# どこまで巻き込めるかを調査
search = np.searchsorted(x,2*d+x,side="right")-1

@lru_cache(maxsize=None)
def keisan():
    count = 0
    for i in range(n):
        if h[i] > 0:
            count += math.ceil(h[i]/a)
            h[i:search[i]+1] -= a*math.ceil(h[i]/a)
    return count

print(keisan())

### FIXED CODE ###

from itertools import accumulate
import math
import bisect

n,d,a = map(int,input().split())
xh = [tuple(map(int,input().split())) for _ in range(n)]
xh.sort()
x = [xh[i][0] for i in range(n)]
h = [xh[i][1] for i in range(n)]
damage = [0]*(n+1)
point = 0

for i in range(n):
    if i != 0:
        damage[i] += damage[i-1]
    bi = bisect.bisect(x,2*d+x[i])
    count = max(math.ceil((h[i]-damage[i])/a),0)
    damage[i] += a*count
    damage[bi] -= a*count
    point += count
    
print(point)
### BUGGY CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,K,Q = map(int, input().split())
    res = [K]*N
    for _ in range(Q):
        a = int(input())
        a -= 1
        for n in range(N):
            if n != a:
                res[n] -= 1
    for x in res:
        if 0<x: print('Yes')
        else: print('No')

if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys
from bisect import *
from collections import *
from copy import deepcopy
from heapq import *
from itertools import *
from math import *
from operator import *
from pprint import *

sys.setrecursionlimit(10**8)

input = sys.stdin.readline

def main():
    """ main """
    N,K,Q = map(int, input().split())
    res = [0]*N
    for _ in range(Q):
        a = int(input())
        a -= 1
        res[a] += 1
    for x in res:
        if 0 < (K-Q+x): print('Yes')
        else: print('No')

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

import sys
#大きすぎるとダメ
sys.setrecursionlimit(10000)
h,w=map(int,input().split())
s=[list(input()) for i in range(h)]
inf=1000000000000000
d=[[inf]*w for i in range(h)]


def dfs(i,j):
    global h,w,s
    nex=[(0,-1),(0,1),(-1,0),(1,0)]
    for k in range(4):
        l,m=i+nex[k][0],j+nex[k][1]
        if 0<=i+nex[k][0]<h and 0<=j+nex[k][1]<w:
            if s[l][m]=="." and d[l][m]>d[i][j]+1:
                d[l][m]=d[i][j]+1
                dfs(l,m)
d[0][0]=0
dfs(0,0)
ans=0
for i in range(h):
    for j in range(w):
        if s[i][j]==".":
            ans+=1
if d[h-1][w-1]==inf:
    print(-1)
else:
    print(ans-d[h-1][w-1]-1)




### FIXED CODE ###

#一個だけRE、わからねえ
#解答見る
import sys
sys.setrecursionlimit(1005)
h,w=map(int,input().split())

def go_next(I,J,n):
    n+=1
    global dp,w,h
    if n>1000:
        return
    if 0<=I<h-1:
        if x[I+1][J]=="." and dp[I+1][J]>dp[I][J]+1:
            dp[I+1][J]=dp[I][J]+1
            go_next(I+1,J,n)
    if 0<I<=h-1:
        if x[I-1][J]=="." and dp[I-1][J]>dp[I][J]+1:
            dp[I-1][J]=dp[I][J]+1
            go_next(I-1,J,n)
    if 0<=J<w-1:
        if x[I][J+1]=="." and dp[I][J+1]>dp[I][J]+1:
            dp[I][J+1]=dp[I][J]+1
            go_next(I,J+1,n)
    if 0<J<=w-1:
        if x[I][J-1]=="." and dp[I][J-1]>dp[I][J]+1:
            dp[I][J-1]=dp[I][J]+1
            go_next(I,J-1,n)

x=[]
for i in range(h):
    x.append(list(input()))
#print(x)
c=0
for i in range(h):
    for j in range(w):
        if x[i][j]==".":
            c+=1
dp=[[10000000000 for i in range(w)]for j in range(h)]
dp[0][0]=1
go_next(0,0,0)
if dp[h-1][w-1]==10000000000:
    print(-1)
else:
    print(c-dp[h-1][w-1])
### BUGGY CODE ###

s=input()
ans=0
for i in range(len(s)-3):
    for j in range(i+4,len(s)+1):
        x=int(s[i:j])
        if x%2019==0:
            ans=ans+1
print(ans)

### FIXED CODE ###

s=input()
n=len(s)
t=[0]*2019
t[0]=1
d=1
tkk=0
for k in reversed(range(n)):
  tk=tkk+int(s[k])*d
  tk=tk%2019
  t[tk]=t[tk]+1
  tkk=tk
  d=d*10
  d=d%2019
ans=0
for i in t:
  ans=ans+i*(i-1)//2
print(ans)
### BUGGY CODE ###

import sys

def main():
    input = sys.stdin.readline

    a, b, m = input().split()
    a, b, m = int(a), int(b), int(m)
    alist = input().split()
    blist = input().split()

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * 200001
    count = 0
    for i in range(a):
      for j in range(b):
        try:
            res[count] = int(alist[i]) + int(blist[j])
        except Exception:
            pass
        count += 1

    for i in range(m):
        res[count] = int(alist[int(waribiki[i][0])-1]) + int(blist[int(waribiki[i][1])-1]) - int(waribiki[i][2])
        count += 1
      
    print(min(res))


if __name__ == '__main__':
    main()

### FIXED CODE ###

import sys

def main():
    input = sys.stdin.readline

    a, b, m = input().split()
    a, b, m = int(a), int(b), int(m)
    alist = list(map(int, input().split()))
    blist = list(map(int, input().split()))

    waribiki = [input().split() for _ in range(m)]
    
    res = [200000] * (m + 1)
    count = 0

    for i in range(m):
        res[count] = alist[int(waribiki[i][0])-1] + blist[int(waribiki[i][1])-1] - int(waribiki[i][2])
        count += 1

    res[count] = min(alist) + min(blist)
      
    print(min(res))


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

class BinaryIndexedTree(): #1-indexed
    def __init__(self, n):
        self.n = n
        self.tree = [0 for _ in range(n + 1)]

    def sum(self, idx):
        res = 0
        while idx:
            res += self.tree[idx]
            idx -= idx & -idx
        return res

    def add(self, idx, x):
        while idx <= self.n:
            self.tree[idx] += x
            idx += idx & -idx

    def bisect_left(self, x):
        if x <= 0: return 0
        res, tmp = 0, 2**((self.n).bit_length() - 1)
        while tmp:
            if res + tmp <= self.n and self.tree[res + tmp] < x:
                x -= self.tree[res + tmp]
                res += tmp
            tmp >>= 1
        return res + 1

class RAQandRSQ(): #1-indexed, BinaryIndexedTree
    def __init__(self, n):
        self.bit1 = BinaryIndexedTree(n)
        self.bit2 = BinaryIndexedTree(n)

    def add(self, lt, rt, x):
        self.bit1.add(lt, -x * (lt - 1))
        self.bit1.add(rt, x * (rt - 1))
        self.bit2.add(lt, x)
        self.bit2.add(rt, -x)

    def sum(self, lt, rt):
        rsum = self.bit2.sum(rt - 1) * (rt - 1) + self.bit1.sum(rt - 1)
        lsum = self.bit2.sum(lt - 1) * (lt - 1) + self.bit1.sum(lt - 1)
        return rsum - lsum

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

R = RAQandRSQ(N)

for i in range(N):
    R.add(i + 1, i + 2, A[i])

for i in range(K):
    query = []
    for j in range(N):
        s = R.sum(j + 1, j + 2)
        query.append((max(1, j - s + 1), min(N + 1, j + s + 2)))
    R = RAQandRSQ(N + 1)
    for l, r in query:
        R.add(l, r, 1)
    flag = False
    for j in range(N):
        if R.sum(j + 1, j + 2) < N:
            flag = True
    if not flag:
        break

res = [min(R.sum(i + 1, i + 2), N) for i in range(N)]

print(*res)

### FIXED CODE ###

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

for i in range(K):
    P = [0 for _ in range(N)] + [0]
    for j in range(N):
        P[max(0, j - A[j])] += 1
        P[min(N, j + A[j] + 1)] -= 1
    A = [0 for _ in range(N)]
    for j in range(N):
        P[j + 1] += P[j]
    flag = False
    for j in range(N):
        A[j] = P[j]
        if A[j] < N:
            flag = True
    if not flag:
        break

print(*A)
### BUGGY CODE ###

A , V = map(int, input().split())
B , W = map(int, input().split())
T = int(input())
flag = 0
for i in range(T):
    B += W
    A += V
    if B <= A:
        flag = 1
if flag == 1:
    print("YES")
else:
    print("NO")

### FIXED CODE ###

A , V = map(int, input().split())
B , W = map(int, input().split())
T = int(input())
flag = 0

if (V - W) <= 0:
    flag = 0
else:
    if ((V - W) * T) >= abs(A - B):
        flag = 1

if flag == 1:
    print("YES")
else:
    print("NO")
### BUGGY CODE ###

N=int(input())
x=0
for i in range(N):
    x=x+i
print(x)    


### FIXED CODE ###

N=int(input())
print(sum(range(1, N)))
### BUGGY CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))

ans = 0
for i, j in itertools.combinations(range(n), 2):
    ans += (a[i] * a[j]) % x

print(ans % x)

### FIXED CODE ###

import itertools
x = 10**9 + 7
n = int(input())
a = list(map(lambda i: i % x , map(int, input().split(" "))))
sum_a = []
prev = 0
for i in a:
    sum_a.append(prev + i)
    prev = prev + i

ans = 0
for i in range(n):
    ans += (a[i] * (sum_a[n-1] - sum_a[i] )) % x
print(ans % x)
### BUGGY CODE ###

N,M,Q = map(int,input().split())
C = {i:{} for i in range(1,N+1)}
for _ in range(M):
    L,R = map(int,input().split())
    if L not in C[R]:
        C[R][L] = 0
    C[R][L] += 1
for _ in range(Q):
    p,q = map(int,input().split())
    A = {i:0 for i in range(1,N+1)}
    for i in range(1,q+1):
        for a in C[i]:
            A[a] += C[i][a]
    cnt = 0
    for a in range(p,N+1):
        cnt += A[a]
    print(cnt)

### FIXED CODE ###

N,M,Q = map(int,input().split())
A = [[0 for _ in range(N+1)] for _ in range(N+1)]
for _ in range(M):
    L,R = map(int,input().split())
    A[L][R] += 1
B = [[0 for _ in range(N+2)] for _ in range(N+2)]
for i in range(N,0,-1):
    for j in range(1,N+1):
        B[i][j] = A[i][j]+B[i+1][j]+B[i][j-1]-B[i+1][j-1]
for _ in range(Q):
    p,q = map(int,input().split())
    print(B[p][q])
### BUGGY CODE ###

N = int(input())
D = list(map(int,input().split()))
ans = 1
if D[0] != 0:
  print(0)
  exit()

prev = 0
for i in range (N):
  if i == 0:
    prev = 1
    if D[0] != 0 or D.count(i) > 1:
      print(0)
      exit()
  else:
    count = D.count(i)
    ans = (ans * (prev**count) ) %998244353
    prev = count
print(ans)

### FIXED CODE ###

n = int(input())
d = list(map(int, input().split()))
b = 1
ans = 1
dd=[0]*10**5
for i in d:
    dd[i]+=1
max = max(d)
if d[0] == 0 and d.count(0) == 1:
    for i in range(1, max+1):
        if dd[i] == 0:
            print(0)
            exit()
        if dd[i] == 1:
            ans *= b
        else:
            if b != 1:
                ans *= pow(b, dd[i], 998244353)
        b = dd[i]
    print(ans % 998244353)
else:
    print(0)
### BUGGY CODE ###

# D - Even Relation

# ある頂点からの距離の偶奇が一致する点を同じ色で塗る

from scipy.sparse.csgraph import dijkstra

N = int(input())

neighbor = [[0]*N for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    neighbor[u-1][v-1] = w%2 + 2
    neighbor[v-1][u-1] = w%2 + 2

dist_from_0 = dijkstra(neighbor, indices = 0)

for i in range(N):
    print(0 if dist_from_0[i]%2 == 0 else 1)

### FIXED CODE ###

# D - Even Relation

# 木なのでノードAB間の辺を辿ればそれがAB間の最短経路となる
# 全ての｢辺｣についてループする

from collections import deque

N = int(input())

edge = [[] for _ in range(N)]

for _ in range(N-1):
    u, v, w = map(int, input().split())
    edge[u-1].append([v-1, w])
    edge[v-1].append([u-1, w])

color = [0] + [-1]*(N-1)
d = deque([0])

while d:
    current_point = d.pop()
    for current_edge in edge[current_point]:
        if color[current_edge[0]] == -1:
            color[current_edge[0]] = (color[current_point] + current_edge[1]) % 2
            d.append(current_edge[0])

for idx in range(N):
    print(color[idx])