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

n = int(input())
T = []
for _ in range(n-1):
    T += [list(map(int, input().split()))]
P = [0]+[-1]*(n-1)
T_sub = []
while T:
    for t in T:
        u, v, w = t
        pu, pv = P[u-1], P[v-1]
        if (pu < 0) & (pv < 0):
            T_sub += [t]
        elif (pu >= 0) & (pv < 0):
            P[v-1] = (pu+(w%2))%2
        else:
            P[u-1] = (pv+(w%2))%2
    T = T_sub
for p in P: print(p)

### FIXED CODE ###

n = int(input())
L = [[] for _ in range(n+1)]
R = [[] for _ in range(n+1)]
for _ in range(n-1):
    u, v, w = map(int, input().split())
    w %= 2
    L[u] += [[u, v, w]]
    R[v] += [[v, u, w]]
P = [[] for _ in range(2*n+2)]
P[1] += (L[1]+R[1])
L[1] = R[1] = []
for i in range(1, 2*n):
    for _, v, w in P[i]:
        P[i+2-w] += (L[v]+R[v])
        L[v] = R[v] = []
A = []
for p in P[1::2]: A += p
B = set([u for u, *_ in A])
for i in range(1, n+1): print(1 if i in B else 0)
### BUGGY CODE ###

import fractions
from functools import reduce

n, *a = map(int, open(0).read().split())

def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

lcm = lcm_list(a)

ans = 0
for a_i in a:
  ans += lcm // a_i

ans = ans % (10**9 + 7)
print(ans)

### FIXED CODE ###

import fractions
from functools import reduce

n, *a = map(int, open(0).read().split())

def lcm_base(x, y):
  return (x * y) // fractions.gcd(x, y)

def lcm_list(numbers):
  return reduce(lcm_base, numbers, 1)

lcm = lcm_list(a)

ans = 0
for a_i in a:
  ans += lcm // a_i

ans = ans % (10**9 + 7)
print(ans)
### BUGGY CODE ###

from itertools import product

x, y, z, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ab = [ai + bi for (ai, bi) in product(a, b)]
ab.sort(reverse=True)
abc = [abi + ci for (abi, ci) in product(ab[: min(k, x * y * z)], c)]
abc.sort(reverse=True)

for abci in abc[: min(k, x * y * z)]:
    print(abci)

### FIXED CODE ###

from itertools import product

x, y, z, k = list(map(int, input().split()))
a = sorted(list(map(int, input().split())), reverse=True)
b = sorted(list(map(int, input().split())), reverse=True)
c = sorted(list(map(int, input().split())), reverse=True)

ab = [ai + bi for (ai, bi) in product(a[:k], b[:k])]
ab.sort(reverse=True)
abc = [abi + ci for (abi, ci) in product(ab[: min(k, x * y * z)], c[:k])]
abc.sort(reverse=True)

for abci in abc[: min(k, x * y * z)]:
    print(abci)
### BUGGY CODE ###

from sys import setrecursionlimit
setrecursionlimit(10**7)
N, Q = [int(x) for x in input().split()]
ab_list = [[int(x) for x in input().split()] for _ in range(N-1)]
px_list = [[int(x) for x in input().split()] for _ in range(Q)]
to = [[] for _ in range(N+1)]
for a, b in ab_list:
    a -= 1
    b -= 1
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for p, x in px_list:
    ans[p-1] += x

def dfs(v, p=-1):
    for u in to[v]:
        if (u == p): continue
        ans[u] += ans[v]
        dfs(u, v)        
dfs(0)
print(' '.join([str(i) for i in ans]))


### FIXED CODE ###

N, Q = [int(x) for x in input().split()]
to = [[] for _ in range(N+1)]
for _ in range(N-1):
    a, b = [int(x)-1 for x in input().split()]
    to[b].append(a)
    to[a].append(b)
ans = [0] * N
for _ in range(Q):
    p, x = [int(x) for x in input().split()]
    p -= 1
    ans[p] += x

from collections import deque
q = deque()
q.append(0)
visited = [0] * N

while(q):
    v = q.pop()
    visited[v] = 1    
    for u in to[v]:
        if visited[u] == 1: continue
        ans[u] += ans[v]
        q.append(u)
print(' '.join([str(i) for i in ans]))
### BUGGY CODE ###

from collections import Counter

N = int(input())
*A, = map(int, input().split())
C = Counter(A)

if 1 in C:
    if C[1] == 1:
        print(1)
    else:
        print(0)
    exit()

B = []
for k, v in C.items():
    if v > 1:
        continue
    B.append(k)

ans = 0
for i, a in enumerate(B):
    for i in range(2, int(a**0.5)+1):
        if a % i == 0:
            if i in C:
                break
            if a // i in C:
                break
    else:
        ans += 1

print(ans)


### FIXED CODE ###

from collections import Counter

def main():
    N = int(input())
    *A, = map(int, input().split())
    C = Counter(A)

    MAX = 1000005
    T = [0]*MAX

    ans = 0
    for a in C.keys():
        if T[a]:
            continue
        else:
            for i in range(2*a, MAX, a):
                T[i] = 1

    ans = 0
    for a, n in C.items():
        if n == 1 and T[a] == 0:
            ans += 1

    print(ans)


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

mod = 10**9+7
 
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
 
dp = [-1 for __ in range(1 << n)]
dp[0] = 1
 
 
def dfs(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
 
 
print(dfs(2**n-1, 0))

### FIXED CODE ###

mod = 10**9+7
 
n = int(input())
a = [[int(x) for x in input().split()] for _ in range(n)]
 
dp = [-1 for __ in range(1 << n)]
dp[0] = 1
 
 
def dfs(bit, i):
    if dp[bit] != -1:
        return dp[bit]
    else:
        tmp = 0
        for j in range(n):
            if bit & (1 << j) and a[i][j]:
                tmp += dfs(bit ^ (1 << j), i+1)
    dp[bit] = tmp % mod
    return dp[bit]
 
 
print(dfs(2**n-1, 0))
### BUGGY CODE ###

f=lambda:map(int,input().split())
n,m=f()
# Union Find
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

for i in range(m):
  a,b=f()
  unite(a-1,b-1)
print(max(size(i) for i in range(n)))

### FIXED CODE ###

f=lambda:map(int,input().split())
n,m=f()
# Union Find
p=[-1]*n
def root(x):
  while p[x]>=0: x=p[x]
  return x
def unite(x,y):
  x,y=root(x),root(y)
  if x==y: return
  if x>y: x,y=y,x
  p[x]+=p[y]
  p[y]=x
def same(x,y):
  return root(x)==root(y)
def size(x):
  return -p[root(x)]

for i in range(m):
  a,b=f()
  unite(a-1,b-1)
print(-min(p))
### BUGGY CODE ###

import math
n,m = map(int,input().split())
price = list(map(int,input().split()))
price.sort(reverse=True)
while m != 0:
    tmp = max(price)
    tmp = tmp//2
    price[price.index(max(price))] = tmp
    m -= 1
print(sum(price))

### FIXED CODE ###

import heapq
n,m = map(int,input().split())
p = list(map(int,input().split()))
price = [x*(-1) for x in p]
heapq.heapify(price)
while m != 0:
    max_price = heapq.heappop(price)*(-1)
    heapq.heappush(price,(max_price//2)*(-1))
    m -= 1
print(sum(price)*(-1))
### BUGGY CODE ###

h,n=map(int,input().split())
a,b=[],[]
for i in range(n):
    a_sub,b_sub=map(int,input().split())
    a.append(a_sub)
    b.append(b_sub)
inf=10000000000000
ma=max(a)
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=[a[i],b[i]]
    for j in range(h):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
                if j+x[0]>=h:
                    dp[h]=min(dp[h],dp[j]+x[1])
            else:
                break
print(dp[h])


### FIXED CODE ###

h,n=map(int,input().split())
ab=[list(map(int,input().split())) for i in range(n)]
ab.sort(reverse=True)
inf=1000000000
ma=ab[0][0]
dp=[inf]*(h+1+ma)
dp[0]=0
for i in range(n):
    x=ab[i]
    for j in range(h):
        if dp[j]!=inf:
            if j+x[0]<=h+ma:
                if j+x[0]>=h:
                    dp[h]=min(dp[h],dp[j]+x[1])
                else:
                    dp[j+x[0]]=min(dp[j+x[0]],dp[j]+x[1])
            else:
                break
print(dp[h])
### BUGGY CODE ###

import itertools
import math


def get_primes(x):
    if x < 2:
        return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x):
            break
        if prime == 0:
            continue
        for non_prime in range(2 * prime, x, prime):
            primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


N = int(input())
primes = get_primes(100000)
ans = primes[:5]
i = 5

while len(ans) < N:
    p = primes[i]
    cand = itertools.combinations(ans, 4)
    admissible = True
    
    for c in cand:
        if sum(c) + p in primes:
            admissible = False
            break
    
    if admissible:
        ans.append(p)

    i += 1

print(*ans)

### FIXED CODE ###

import itertools
import math


def get_primes(x):
    if x < 2:
        return []

    primes = [i for i in range(x)]
    primes[1] = 0

    for prime in primes:
        if prime > math.sqrt(x):
            break
        if prime == 0:
            continue
        for non_prime in range(2 * prime, x, prime):
            primes[non_prime] = 0

    return [prime for prime in primes if prime != 0]


N = int(input())
primes = get_primes(55555)
ans = []
i = 4

while len(ans) < N:
    p = primes[i]
    
    if p % 5 == 1:
        ans.append(p)

    i += 1

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

from operator import itemgetter
# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = []
for i in range(M):
    move.append(list(map(int, input().split())))
move.sort(key=itemgetter(0))

dp = [0] * (N+1)
done_n = -1

def findpath(now_x):
    if now_x <= done_n:
        return dp[now_x]
    for x,y in move:
        if now_x == x:
            dp[now_x] = max(dp[now_x],findpath(y) + 1)
        if now_x < x:
            break
    return dp[now_x]

maxpath = 0
for do_n in range(1,N+1):
    done_n = do_n - 1
    maxpath = max(maxpath,findpath(do_n))

print(maxpath)


### FIXED CODE ###

import sys
sys.setrecursionlimit(10**5)

# スペース区切りの整数入力
N,M = map(int, input().split())
#指定数分の３つの整数を順番に受けてリストに入力
move = {}
for i in range(M):
    x,y = map(int, input().split())
    move.setdefault(x,[]).append(y)

dp = [-1] * (N+10)

def findpath(now_x):
    if dp[now_x] > -1:
        return dp[now_x]
    maxpath = 0
    if now_x in move.keys():
        for y in move[now_x]:
            maxpath = max(maxpath,findpath(y) + 1)
    dp[now_x] = maxpath
    return maxpath

Ans = 0
for do_x in range(1,N+1):
    Ans = max(Ans,findpath(do_x))

print(Ans)
### BUGGY CODE ###

n, k = map(int, input().split())
a = list(map(int, input().split()))
befscore = 1
score = 1
f = True
for i in range(n):
    score = score * a[i]

    if i >= k:
        score = int(score / a[i - k])
        if befscore >= score:
            print("No")
        else:
            print("Yes")

    befscore = score


### FIXED CODE ###

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

a = list(map(lambda x: x - ma, a))

befscore = 1
score = 1
f = True
for i in range(n):
    score = score + a[i]

    if i >= k:
        score = int(score - a[i - k])
        if befscore >= score:
            print("No")
        else:
            print("Yes")

    befscore = score
### BUGGY CODE ###

import numpy as np
N, M = map(int, input().split())
Alist = np.array(list(map(int, input().split())))
for _ in range(M):
    Alist[np.argmax(Alist)] /= 2
print(np.sum(Alist.astype(np.int64)))


### FIXED CODE ###

import heapq


def int_and_reverse(num):
    return int(num) * -1


N, M = map(int, input().split())
Alist = list(map(int_and_reverse, input().split()))
heapq.heapify(Alist)
for _ in range(M):
    x = (heapq.heappop(Alist) * -1) // 2
    heapq.heappush(Alist, -x)
print(-sum(Alist))
### BUGGY CODE ###

n = int(input())
a = list(map(int,input().split()))
ok = True
cnt = n%2+1
for i in range(cnt,n,2):
    if a.count(i)!=2:
        ok = False
        break
if ok:
    print(2**(n//2))
else:
    print(0)

### FIXED CODE ###

n = int(input())
a = list(map(int,input().split()))
ok = True
a.sort()
if n%2==0:
    for i in range(n):
        if a[i]!= i-i%2+1:
            ok = False
            break
else:
    for i in range(n):
        if a[i]!= i+i%2:
            ok = False
            break
if ok:
    print(2**(n//2)%(10**9+7))
else:
    print(0)
### BUGGY CODE ###

def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(m)]
    a.sort()
    dp = [10 ** 18 for i in range(n)]
    dp[0] = 0
    for l, r, c in a:
        tp = dp[l - 1] + c
        for i in range(l - 1, r):
            dp[i] = min(dp[i], tp)
    if dp[-1] == 10 ** 18:
        print(-1)
    else:
        print(dp[-1])


main()


### FIXED CODE ###

def main():
    n, m = map(int, input().split())
    a = [list(map(int, input().split())) for _ in range(m)]
    a.sort()
    INF = 10 ** 18
    dp = [INF for i in range(n)]
    dp[0] = 0
    for l, r, c in a:
        if dp[l - 1] == INF:
            print(-1)
            return None
        tp = dp[l - 1] + c
        for i in range(r - 1, l - 1, -1):
            if dp[i] == INF:
                dp[i] = tp
            elif tp < dp[i]:
                dp[i] = tp
            else:
                break
    if dp[-1] == INF:
        print(-1)
    else:
        print(dp[-1])


main()
### BUGGY CODE ###

import sys
from heapq import heapify, heappush, heappop

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
heapify(A)


for _ in range(M):
	b,c=map(int, sys.stdin.readline().split())
	for i in range(b):
		if A[0]<c:
			heappop(A)
			heappush(A, c)
		else:
			break

print sum(A)


### FIXED CODE ###

import sys

N,M=map(int, sys.stdin.readline().split())
A=map(int, sys.stdin.readline().split())
A.sort()

B=[ map(int, sys.stdin.readline().split()) for _ in range(M)] 
B.sort(key=lambda x: x[1], reverse=True)

i=0

for b,c in B:
	for i in range(i,N):
		if A[i]<c and 0<b:
			A[i]=c
			b-=1
		if b==0:
			break
	i+=1

print sum(A)
### BUGGY CODE ###

N = int(input())
S = input()
min = S[0:1].count("W") + S[2:N].count("E")

for i in range (N):
    count = S[0:i].count("W") + S[i+1:N].count("E")
    if min > count:
        min = count
print(min)


### FIXED CODE ###

N = int(input())
S = input()
min = S[1:N].count("E")
now = S[1:N].count("E")

for i in range (1,N):
    if S[i-1] == "E" and S[i] == "E":
        now -= 1
    if S[i-1] == "W" and S[i] == "W":
        now += 1
    if now < min:
        min = now
print(min)
### BUGGY CODE ###

n = int(input())

a = []

for _ in range(n):
    a.append(int(input()))

for i in range(n):
    a_removed = a.copy()
    del a_removed[i]
    print(max(a_removed))

### FIXED CODE ###

n = int(input())

a = []

for _ in range(n):
    a.append(int(input()))

a_max = max(a)
a_max_index = a.index(a_max)

a.sort(reverse=True)
a_second_max = a[1]

for i in range(n):
    if i == a_max_index:
        print(a_second_max)
    else:
        print(a_max)
### BUGGY CODE ###

n = int(input())
a = list(map(int, input().split()))
for i in a:
    if a.count(i) >= 2:
        print("NO")
        exit()
print("YES")


### FIXED CODE ###

n = int(input())
a = list(map(int, input().split()))
b = set(a)
a.sort()
if len(a) != len(b):
    print("NO")
else:
    print("YES")
### BUGGY CODE ###

s = input()
q = int(input())

for i in range(q):
    query = input()
    if query == "1":
        s = s[::-1]
    else:
        t, f, c = query.split()
        if f == "1":
            s = c + s
        else:
            s = s + c

print(s)

### FIXED CODE ###

from collections import deque

s = deque(input())
q = int(input())
reversed_flag = False

for i in range(q):
    query = input()
    if query == "1":
        reversed_flag = not reversed_flag
    else:
        t, f, c = query.split()
        if f == "1":
            if reversed_flag:
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if reversed_flag:
                s.appendleft(c)
            else:
                s.append(c)

if reversed_flag:
    s.reverse()

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

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if x + y + z == S and 0 <= z <= K:
            #print('{} {} {}'.format(x,y,z))
            count += 1

print(count)


### FIXED CODE ###

K, S = map(int, input().split())
count = 0
for x in range(K+1):
    for y in range(K+1):
        z = S - x - y
        if x + y + z == S and 0 <= z <= K:
            #print('{} {} {}'.format(x,y,z))
            count += 1

print(count)
### BUGGY CODE ###

import math
import collections
def trial_division_sqrt(n):

    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1

    return prime_count
def pc(n, r):
    return math.factorial(n) // (math.factorial(n - r)  * math.factorial(r))
s=0
x,N = map(int,input().split())

li = trial_division_sqrt(N)
li = li.most_common()
ans = 1
for i in range(0, len(li)):
    ans *= pc(li[i][1] + x-1, x-1)
print(ans % (pow(10, 9)+7))

### FIXED CODE ###

import math
import collections
def trial_division_sqrt(n):

    prime_count = collections.Counter()

    for i in range(2, int(math.sqrt(n)) + 2):
        while n % i == 0:
            n /= i
            prime_count[i] += 1
    if n > 1:
        prime_count[n] += 1

    return prime_count
def pc(n, r):
    return math.factorial(n) // (math.factorial(n - r)  * math.factorial(r))
nCr = {}
def cmb(n, r):
    if n - r < r: r = n - r
    if r == 0: return 1
    if r == 1: return n;

    numerator = [n - r + k + 1 for k in range(r)]
    denominator = [k + 1 for k in range(r)]

    for p in range(2,r+1):
        pivot = denominator[p - 1]
        if pivot > 1:
            offset = (n - r) % p;
            for k in range(p-1,r,p):
                numerator[k - offset] /= pivot
                denominator[k] /= pivot

    result = 1
    for k in range(r):
        if numerator[k] > 1:
            result *= int(numerator[k])

    return result;
s=0
x,N = map(int,input().split())

li = trial_division_sqrt(N)
li = li.most_common()
ans = 1
for i in range(0, len(li)):
    ans *= cmb(li[i][1] + x-1, x-1)
print(ans % (pow(10, 9)+7))
### BUGGY CODE ###

n,m=map(int,input().split())
l=[]
h=[]
count=0
for i in range(m):
    a,b=map(int,input().split())
    l.append(a)
    h.append(b)

for i in range(n):
    judge=True
    for j in range(m):
        #if not (((i+1) >= l[j]) and ((i+1) <= h[j])):
        if not ((i+1) >= l[j] and (i+1) <= h[j]):
            judge^=True
            break
    if judge:
        count+=1

print(count)

### FIXED CODE ###

n,m=map(int,input().split())
l=[]
h=[]
count=0
for i in range(m):
    a,b=map(int,input().split())
    l.append(a)
    h.append(b)

l_max=max(l)
h_min=min(h)
if (h_min-l_max)<0:
    print(0)
else:
    print(h_min-l_max+1)
### BUGGY CODE ###

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


def div(n):
    """give divisors"""
    divisors = [1]
    i = 2
    while n > 1:
        if n % i == 0:
            divisors.append(i)
            while n % i == 0:
                n = n/i
        i += 1
    return(divisors)


def comn_div(n, m):
    """give common divisors"""
    # 二つの約数を取って来てset&set
    cdiv_nm = set(div(n)) & set(div(m))
    return(list(cdiv_nm))
# 自然数以外が入ったら弾きたい気もする


cdiv_ab = comn_div(a, b)
disjoint = []
for i in range(len(cdiv_ab)):
    state = True
    # 自分より若い数字が約数の場合は除外
    for j in range(i):
        if comn_div(cdiv_ab[i], cdiv_ab[j]) != [1]:
            state = False
    if state:
        disjoint.append(i)
# print(cdiv_ab)
# print(disjoint)
print(len(disjoint))


### FIXED CODE ###

# def max_comn_div(n, m):
#     """give max common divisor"""
#     if n > m:
#         a, b = n, m
#     else:
#         a, b = m, n
#     while b != 0:
#         a, b = b, a % b
#     return a


# a = int(input())
# b = int(input())
# print(max_comn_div(a, b))

# def euc(a, b):
#      if a % b == 0:
#          return b
#      else:
#          return euc(b, a % b)


def euc(a, b):
    return b if a % b == 0 else euc(b, a % b)


def div(n):
    """give divisors"""
    divisors = [1]
    for i in range(2, int(n**0.5)+1):
        while n % i == 0:
            divisors.append(i)
            n /= i
    if n != 1:
        divisors.append(int(n))
    return set(divisors)


a, b = map(int, input().split())
# print(euc(a, b))
c = div(euc(a, b))
# print(c)
print(len(c))
### BUGGY CODE ###

n = int(input())
arr = [int(input()) for _ in range(n)]
colors = {}
cnum = 0

colors[cnum] = arr[-1]
for a in arr[-2::-1]:
  for c in range(cnum + 1):
    if colors[c] > a:
      colors[c] = a
      break
  else:
    cnum += 1
    colors[cnum] = a

print(cnum+1)


### FIXED CODE ###

import bisect

n = int(input())
arr = [int(input()) for _ in range(n)]
colors = []

colors.append(arr[-1])
cnum = len(colors)
for a in arr[-2::-1]:
  i = bisect.bisect_right(colors, a)
  if i < cnum:
    colors[i] = a
  else:
    colors.append(a)
    cnum += 1

print(cnum)
### BUGGY CODE ###

N,M=map(int,input().split())
a=[int(input()) for _ in range(M)]
mod=10**9+7
dp=[0]*(N+1)
dp[0]=1
if 1 not in a:
	dp[1]=1
else:
	dp[1]=0
for i in range(2,N+1):
	if i in a:
		continue
	else:
		dp[i]=dp[i-1]+dp[i-2]
ans=dp[N]%mod
print(ans)


### FIXED CODE ###

N,M=map(int,input().split())
dp=[0]*(N+1)
dp[0]=1
mod=10**9+7
a=[False for _ in range(N+1)]
for _ in range(M):
    a[int(input())]=True
    
for i in range(1,N+1):
    if a[i]:
        continue
    dp[i]=(dp[i-1]+dp[i-2])%mod
 
print(dp[N])
### BUGGY CODE ###

n = int(input());
ans = 1;
lis = list(map(int,input().split()))

for i in range(n):
    ans *= lis[i]
if ans>=1000000000000000001:
    print(-1)
else:
    print(ans)

### FIXED CODE ###

n = int(input());
ans = 1;
lis = list(map(int,input().split()))
flag = False
flag2 = False
for i in range(n):
    if lis[i]==0:
        flag = True
    if ans*lis[i]>=1000000000000000001:
        flag2 = True
    else:
        ans *= lis[i]

if flag:
    print(0)
elif flag2:
    print(-1)
else:
    print(ans)
### BUGGY CODE ###

from collections import defaultdict

S = input()
ans = 0
N = len(S)
mod = 2019
dp = defaultdict(int)
cur = 0
for i in range(N, -1, -1):
    if i == N:
        dp[0] += 1
    else:
        cur += ((10 ** (N - i - 1)) * int(S[i])) % mod
        cur %= mod
        dp[cur] += 1
for v in dp.values():
    if v > 1:
        ans += v * (v - 1) // 2
print(ans)


### FIXED CODE ###

from collections import defaultdict


def solve(input_s: str):
    ans = 0
    n = len(input_s)
    mod = 2019
    dp = defaultdict(int)
    cur = 0
    for i in range(n, -1, -1):
        if i == n:
            dp[0] += 1
        else:
            # cur += ((10 ** (n - i - 1)) * int(input_s[i])) % mod これはnがでかくなるとめちゃめちゃ遅い
            cur += pow(10, n - i - 1, 2019) * int(input_s[i]) % mod
            cur %= mod
            dp[cur] += 1
    for v in dp.values():
        if v > 1:
            ans += v * (v - 1) // 2
    return ans


if __name__ == '__main__':
    S = input()
    print(solve(S))
### BUGGY CODE ###

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]
 
rails.sort(key = lambda x:x[0],reverse=True)


for p,q in qs:
    ans=0
    for l,r in rails:
        if p<=l and r<=q:
            ans=ans+1
        elif p>l:
            break
    print(ans)


### FIXED CODE ###

from collections import Counter
from itertools import product

n,m,q  = map(int,input().split())
rails=[tuple(map(int,input().split())) for i in range(m)]
qs=[tuple(map(int,input().split())) for i in range(q)]

xlist = [[0 for j in range(n)] for i in range(n)]
sumlist = [[0 for j in range(n+1)] for i in range(n)]
for (l,r),i in Counter(rails).items():
    xlist[l-1][r-1]=i


for (i,j) in product(range(n),range(n)):
    sumlist[i][j+1]=sum(xlist[i][0:j+1])


for (p,q) in qs:
    ans = 0
    for i in range(p-1,q):
        ans = ans+sumlist[i][q]-sumlist[i][p-1]
    print(ans)