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

#!python3

iim = lambda: map(int, input().rstrip().split())
from collections import defaultdict

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353

    dp0 = [[]]
    ans = 0
    T  = [defaultdict(int, [(0, 1)])]
    for ai in A:
        tmp = []
        for t1 in T:
            t2 = t1.copy()
            for k, v in t1.items():
                if k + ai > S:
                    continue
                t2[k+ai] += v
                t2[k+ai] %= mod
            tmp.append(t2)

            ans += t2[S]
            ans %= mod

        T += tmp

    print(ans)


if __name__ == "__main__":
    resolve()


### FIXED CODE ###

#!python3

iim = lambda: map(int, input().rstrip().split())

def resolve():
    N, S = iim()
    A = list(iim())
    mod = 998244353
    S1 = S + 1

    dp = [0] * (S+1)

    dp[0] = pow(2, N, mod)
    inv = pow(2, mod-2, mod)

    for ai in A:
        for i in range(S, ai-1, -1):
            dp[i] = (dp[i] + dp[i-ai]*inv) % mod

    print(dp[-1])


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

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Acount = Counter(A)
Adic = dict(Acount)
# print(Adic)
s = 0
for key, value in Adic.items():
    s += key*value
for i in range(q):
    b, c = map(int, input().split())
    if not b in set(Adic.keys()):
        Adic[b] = 0
    s += (c - b) * Adic[b]
    if not c in set(Adic.keys()):
        Adic[c] = 0
    Adic[c] += Adic[b]
    Adic[b] = 0
    print(s)


### FIXED CODE ###

from collections import Counter
n = int(input())
A = list(map(int, input().split()))
q = int(input())
Acount = Counter(A)
Adic = dict(Acount)
Akey = set(Adic.keys())
M = max(A)
L = [0 for i in range(10**5)]
for i in range(M):
    if i+1 in Akey:
        L[i] = Adic[i+1]
s = 0
for i in range(M):
    s += (i + 1) * L[i]
for i in range(q):
    b, c = map(int, input().split())
    s += (c - b) * L[b - 1]
    L[c - 1] += L[b - 1]
    L[b - 1] = 0
    print(s)
### BUGGY CODE ###

import collections
from collections import deque


N = int(input())
A = list(map(int,input().split()))
d = deque(A)
ans = 0
for i in range(N):
    q = d.popleft()
    a = collections.Counter(d)
    tmp = a.values()
    l = list(tmp)
    for j in range(len(l)):
        n = l[j]-1
        ans += n*(n+1)//2
    print(ans)
    ans = 0
    d.append(q)




### FIXED CODE ###

import collections

N = int(input())
A = list(map(int,input().split()))
a = collections.Counter(A)
v = a.values()
l_v = list(v)

#合計
s = 0
for i in range(len(l_v)):
    n = l_v[i]-1
    s += n*(n+1)//2
#カウント
for i in range(N):
    print(s-(a[A[i]]-1))
### BUGGY CODE ###

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = 10**9+1
        for k in range(n):
            if k==j or k==i:
                continue
            dp = min(dp,a[i][k]+a[k][j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)

### FIXED CODE ###

n = int(input())
a = [list(map(int,input().split())) for _ in range(n)]
ans = 0
for i in range(n):
    for j in range(i,n):
        if i==j:
            continue
        dp = 10**9+1
        for k in range(n):
            if k==j or k==i:
                continue
            dp = min(dp,a[i][k]+a[k][j])
        if a[i][j]<dp:
            ans += a[i][j]
        elif a[i][j]>dp:
            print(-1)
            exit()
print(ans)
### BUGGY CODE ###

A,B,Q=map(int,input().split())
s=[]
for _ in range(A):
    s.append(int(input()))
t=[]
for _ in range(B):
    t.append(int(input()))
from bisect import bisect
infty=1e50
for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    if 0<i<A:
        sL=x-s[i-1]
        sR=s[i]-x
    elif i==0:
        sL=infty
        sR=s[i]-x
    else:
        sL=x-s[-1]
        sR=infty
    
    if 0<j<B:
        tL=x-t[j-1]
        tR=t[j]-x
    elif j==0:
        tL=infty
        tR=t[j]-x
    else:
        tL=x-t[-1]
        tR=infty
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))




### FIXED CODE ###

A,B,Q=map(int,input().split())
inf=1e50
s=[-inf]
for _ in range(A):
    s.append(int(input()))
s.append(inf)

t=[-inf]
for _ in range(B):
    t.append(int(input()))
t.append(inf)
from bisect import bisect

for _ in range(Q):
    x=int(input())
    i=bisect(s,x)
    j=bisect(t,x)
    
    sL=x-s[i-1]
    sR=s[i]-x
    
    tL=x-t[j-1]
    tR=t[j]-x
    print(min(max(sR,tR),max(sL,tL),sR+tL+min(sR,tL),sL+tR+min(sL,tR)))
### BUGGY CODE ###

# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))


H,W,M=map(int, input().split())
#P = [list(map(int,input().split())) for i in range(M)]
Hlist=[0] * M
Wlist=[0] * M
P = []
for i in range(M):
    Hlist[i],Wlist[i]=map(int, input().split())
    P.append([Hlist[i],Wlist[i]])


HC = Counter(Hlist)
HD = HC.most_common()
WC = Counter(Wlist)
WD = WC.most_common()

Hmax = HD[0][1]
Wmax = WD[0][1]
ans = Hmax + Wmax


for i in range(len(HD)):
    if HD[i][1] != Hmax:
        break
    for j in range(len(WD)):
        if WD[j][1] != Wmax:
            break
        tmp = [HD[i][0],WD[j][0]]
        if (tmp in P) == False:
            print(ans)
            sys.exit()
        

print(ans-1)


### FIXED CODE ###

# -*- coding: utf-8 -*-
 
## Library
 
import sys
from fractions import gcd
import math
from math import ceil,floor
import collections
from collections import Counter
import itertools
import copy

## input
 
# N=int(input())
# A,B,C,D=map(int, input().split())
# S = input()
# yoko = list(map(int, input().split()))
# tate = [int(input()) for _ in range(N)]
# N, M = map(int,input().split()) 
#    P = [list(map(int,input().split())) for i in range(M)]
#    S = []
#    for _ in range(N):
#        S.append(list(input()))


H,W,M=map(int, input().split())
#P = [list(map(int,input().split())) for i in range(M)]
Hlist=[0] * M
Wlist=[0] * M
P = []
for i in range(M):
    Hlist[i],Wlist[i]=map(int, input().split())
    P.append([Hlist[i],Wlist[i]])

Pset = set(map(tuple, P))

HC = Counter(Hlist)
HD = HC.most_common()
WC = Counter(Wlist)
WD = WC.most_common()

Hmax = HD[0][1]
Wmax = WD[0][1]
ans = Hmax + Wmax

# print(P)
# print(Pset)
# print("H----")
# print(Hlist)
# print(HC)
# print(HD)
# print("Hmax=",Hmax)
# print("W----")
# print(Wlist)
# print(WC)
# print(WD)
# print("Wmax=",Wmax)

# print(ans)


for i in range(len(HD)):
    if HD[i][1] != Hmax:
        break
    for j in range(len(WD)):
        if WD[j][1] != Wmax:
            break
        tmp = tuple([HD[i][0],WD[j][0]])
        if (tmp in Pset) == False:
            print(ans)
            sys.exit()
        
print(ans-1)
### BUGGY CODE ###

N = int(input())
S = input()

count = 0
for i in range(1000):
    password = str(i).zfill(3)
    j = 0
    for s in S:
        if s == password[j]:
            j += 1
            if j == 3:
                count += 1
                break
print(count)

### FIXED CODE ###

N = int(input())
S = input()

count = 0
for i in range(1000):
    password = str(i).zfill(3)
    j = 0
    for s in S:
        if s == password[j]:
            j += 1
            if j == 3:
                count += 1
                break
print(count)
### BUGGY CODE ###

d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=(i*10**k)%13
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=(int(t)*10**k)%13
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])

### FIXED CODE ###

d=[0]*13
d[0]=1
s=input()
for k,t in enumerate(s[::-1]):
    if t=='?':
        d2=[0]*13
        for i in range(10):
            u=i*pow(10,k,13)
            for i in range(13):
                d2[(i+u)%13]+=d[i]
    else:
        u=int(t)*pow(10,k,13)
        d2=[0]*13
        for i in range(13):
            d2[(i+u)%13]+=d[i]
    for i in range(13):
        d[i]=d2[i]%(10**9+7)
print(d[5])
### BUGGY CODE ###

import numpy as np
from collections import deque

h, w = map(int, input().split())
s = [list(input()) for _ in range(h)]

ans = 0
for i in range(h):
    for j in range(w):
        if s[i][j] == '#': continue
        q = deque()
        q.append([i, j, 0])
        visited = np.zeros((h + 5, w + 5), dtype = bool)
        dirr = [[1, 0], [0, 1], [-1, 0], [0, -1]]
        mx = 0
        while len(q) != 0:
            x, y, z = q[0]
            ans = max(ans, z)
            visited[x][y] = True
            for p in range(4):
                nx, ny = x + dirr[p][0], y + dirr[p][1]
                if 0 <= nx < h and 0 <= ny < w:
                    if not visited[nx][ny] and s[nx][ny] == '.':
                        q.append([nx, ny, z + 1])
            q.popleft()
print(ans)


### FIXED CODE ###

#!/usr/bin/env python3
import sys
sys.setrecursionlimit(10**5)
input = sys.stdin.readline
from collections import deque

h, w = [int(item) for item in input().split()]
field = []
field.append("#" * (w + 2))
for i in range(h):
    field.append("#" + input().rstrip() + "#")
field.append("#" * (w + 2))


ans = 0
for i in range(1, h+1):
    for j in range(1, w+1):
        if field[i][j] == "#":
            continue
        dist = [[-1] * (w + 2) for _ in range(h + 2)]
        dist[i][j] = 0
        dq = deque()
        dq.append((i, j, 0))
        while dq:
            x, y, d = dq.popleft()
            if field[x+1][y] == "." and dist[x+1][y] == -1:
                dist[x+1][y] = d+1
                dq.append((x+1, y, d+1))
            if field[x][y+1] == "." and dist[x][y+1] == -1:
                dist[x][y+1] = d+1
                dq.append((x, y+1, d+1))
            if field[x-1][y] == "." and dist[x-1][y] == -1:
                dist[x-1][y] = d+1
                dq.append((x-1, y, d+1))
            if field[x][y-1] == "." and dist[x][y-1] == -1:
                dist[x][y-1] = d+1
                dq.append((x, y-1, d+1))
        for line in dist:
            ans = max(ans, max(line))
        
print(ans)
### BUGGY CODE ###

import heapq
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
edges=[[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    a,b=a-1,b-1
    edges[a].append((b, c))
    edges[b].append((a, c))

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node, cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
dist=[[] for _ in range(n)]
for i in range(n):
    dist[i]=dijkstra(i,edges)
ans=float("inf")
t=itertools.permutations(r)
for i in t:
    d=0
    start=i[0]-1
    for end in i[1:]:
        d+=dist[start][end-1]
        start=end-1
    ans=min(ans,d)
print(ans)

### FIXED CODE ###

import heapq
import itertools
n,m,R=map(int,input().split())
r=list(map(int,input().split()))
edges=[[] for _ in range(n)]
for _ in range(m):
    a,b,c = map(int, input().split())
    a,b=a-1,b-1
    edges[a].append((b, c))
    edges[b].append((a, c))

def dijkstra(x,route):
    d=[float('inf')]*n
    d[x]=0
    visited={x}
    hq=[(0,x)]
    while hq:
        u=heapq.heappop(hq)[1]
        visited.add(u)
        for node, cost in route[u]:
            if (node not in visited) and d[node]>d[u]+cost:
                d[node]=d[u]+cost
                heapq.heappush(hq,(d[node],node))
    return d
dist=[[] for _ in range(R)]
for i in range(R):
    start=r[i]-1
    dist[i]=dijkstra(start,edges)
ans=float("inf")
t=itertools.permutations(r)
for i in t:
    d=0
    start=i[0]
    for end in i[1:]:
        d+=dist[r.index(start)][end-1]
        start=end
    ans=min(ans,d)
print(ans)
### BUGGY CODE ###

import math
import collections

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def comb(n,k,p):
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a,b,p):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

def m():
    ans = 1
    f = prime_factors(M)
    counts = collections.Counter(f)
    for k,v in counts.items():
        ans *= comb(v + N-1, N-1, MOD)
    return ans % MOD

print(m())

### FIXED CODE ###

import math
import collections

N, M = map(int, input().split())
MOD = 10 ** 9 + 7


def prime_factors(n):
    i = 2
    factors = []
    while i * i <= n:
        if n % i:
            i += 1
        else:
            n //= i
            factors.append(i)
    if n > 1:
        factors.append(n)
    return factors


def comb(n,k,p):
    from math import factorial
    if n < 0 or k < 0 or n < k: return 0
    if n == 0 or k == 0: return 1
    a = factorial(n) % p
    b = factorial(k) % p
    c = factorial(n - k) % p
    return (a * power_func(b, p - 2, p) * power_func(c, p - 2, p)) % p


def power_func(a,b,p):
    if b == 0: return 1
    if b % 2 == 0:
        d = power_func(a, b // 2, p)
        return d * d % p
    if b % 2 == 1:
        return (a * power_func(a, b - 1, p)) % p

def m():
    ans = 1
    f = prime_factors(M)
    counts = collections.Counter(f)
    for k,v in counts.items():
        ans *= comb(v + N-1, N-1, MOD)
    return ans % MOD

print(m())
### BUGGY CODE ###

n = int(input())
D = list(map(int, input().split()))
m = int(input())
T = list(map(int, input().split()))
D.sort()
T.sort()
if n<=m:
    if D==T:
        print('YES')
        exit()
    else:
        print('NO')
        exit()

r = 'YES'
for i in range(m):
    if T[i] in D:
        idx = D.index(T[i])
        D = D[idx+1:]
    else:
        r = 'NO'
        break
print(r)

### FIXED CODE ###

n = int(input())
dD = input().split()
m = int(input())
dT = input().split()
d = dict()

for di in dD:
    if di in d:
        d[di] += 1
    else:
        d[di] = 1

ans = 'YES'
for ti in dT:
    if ti not in d or d[ti]==0:
        ans = 'NO'
        break
    else:
        d[ti] -= 1
print(ans)
### BUGGY CODE ###

n = int(input())

x = (10**9 + 7)
k=1
for i in range(1,n+1):
  k = k * i

  
  

print(k % x)

### FIXED CODE ###

n = int(input())

x = (10**9 + 7)
k=1
for i in range(1,n+1):
  k = k * i
  k = k%x

print(k)
### BUGGY CODE ###

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

ans = 1
for i in range(1,n):   
    if min(lst[:i]) > lst[i]:
        ans += 1

print(ans) 

### FIXED CODE ###

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

ans = 1
lst_min = []
for i in range(n):
    if i == 0:
        lst_min.append(lst[i])
    else:
        lst_min.append(
            min(lst_min[i-1], lst[i])
        )
        if lst_min[i] == lst[i]:
            ans += 1
print(ans)
### BUGGY CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
import heapq
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def dijkstra_heap(s):
    #始点sから各頂点への最短距離
    d = [float("inf")] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for e in edge[s]:
        heapq.heappush(edgelist,e)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge[1]]:
            continue
        v = minedge[1]
        d[v] = minedge[0]
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,[e[0]+d[v],e[1]])
    return d

# n,w = map(int,input().split()) #n:頂点数　w:辺の数

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

for i in range(1, N-1):
    edge[i].append([1, i+1])
    edge[i].append([1, i-1])
edge[0].append([1, 1])
edge[N-1].append([1, N-2])
edge[X-1].append([1, Y-1])
edge[Y-1].append([1, X-1])

dd = defaultdict(int)
for i in range(N):
    dists = dijkstra_heap(i)
    for j in dists[i+1:]:
        dd[j] += 1

for k in range(1, N):
    print(dd[k])


### FIXED CODE ###

import sys, math
from itertools import permutations, combinations
from collections import defaultdict, Counter, deque
from math import factorial
from bisect import bisect_left #bisect_left(list, value)
import heapq
#from fractions import gcd
sys.setrecursionlimit(10**7)
enu = enumerate
MOD = 10**9+7
def input(): return sys.stdin.readline()[:-1]
def pri(x): print('\n'.join(map(str, x)))

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

def dijkstra_heap(s,edge):
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d
# n,w = map(int,input().split()) #n:頂点数　w:辺の数

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

for i in range(1, N-1):
    edge[i].append([1, i+1])
    edge[i].append([1, i-1])
edge[0].append([1, 1])
edge[N-1].append([1, N-2])
edge[X-1].append([1, Y-1])
edge[Y-1].append([1, X-1])

dd = defaultdict(int)
for i in range(N):
    dists = dijkstra_heap(i, edge)
    for j in dists[i+1:]:
        dd[j] += 1

for k in range(1, N):
    print(dd[k])
### BUGGY CODE ###

from numpy import*
m=lambda:map(int,input().split())
n,k=m()
a=matrix([list(m())for i in[0]*n],'O')
b=eye(n,n,0,'O')
while k:b=[b,b*a][k&1];a*=a;k>>=1
print(sum(b)%(10**9+7))

### FIXED CODE ###

import numpy
M=10**9+7
n,k=map(int,input().split())
a=numpy.matrix([list(map(int,input().split()))for i in[0]*n],dtype='O')
b=numpy.eye(n,dtype='O')
while k:b=[b,b*a%M][k&1];a=a*a%M;k>>=1
print(b.sum()%M)
### BUGGY CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))
A.sort()

pc = True
gg = False
cnt = Counter()

fm = {}

def factorization(n):
    arr = []
    temp = n
    for i in range(2, int(-(-n**0.5//1))+1):
        if temp in fm:
            arr += fm[temp]
            break
        if temp%i==0:
            while temp%i==0:
                temp //= i
            arr.append(i)
    if temp!=1:
        arr.append(temp)
    if arr==[]:
        arr.append(n)
    fm[n] = arr
    return arr

for a in factorization(A[0]):
    if a > 1:
        cnt[a] = 1

for i in range(1, N):
    for a in factorization(A[i]):
        if cnt[a] >= 1:
            pc = False
        if a > 1:
            cnt[a] += 1

if pc:
    print("pairwise coprime")
elif cnt.most_common(1)[0][1] < N:
    print("setwise coprime")
else:
    print("not coprime")

### FIXED CODE ###

from collections import Counter
N = int(input())
A = list(map(int, input().split()))

x = max(A)
hurui = [x]*(x+1)
for i in range(2, x+1):
    for j in range(i, x+1, i):
        hurui[j] = min(i, hurui[j])

cnt = Counter([1])
for i in range(N):
    num = A[i]
    while num > 1:
        x = hurui[num]
        while num%x == 0:
            num //= x
        cnt[x] += 1

a = cnt.most_common(1)[0][1]
if a == 1:
    print("pairwise coprime")
elif a < N:
    print("setwise coprime")
else:
    print("not coprime")
### BUGGY CODE ###

#!/usr/bin/python3
from collections import defaultdict

(n, m) = map(int, input().split())

xti = {}
yti = {}
xti[0] = -1
yti[0] = -1

lvs = []
for i in range(n):
    (a, b, c) = map(int, input().split())
    yti[a] = -1
    yti[b] = -1   
    xti[c] = -1
    lvs.append((a, b, c))

lhs = []
for i in range(m):
    (d, e, f) = map(int, input().split())
    yti[d] = -1
    xti[e] = -1   
    xti[f] = -1
    lhs.append((d, e, f))

xs = sorted(xti.keys())
for (i, x) in enumerate(xs):
    xti[x] = i
    
ys = sorted(yti.keys())
for (i, y) in enumerate(ys):
    yti[y] = i

xsl = len(xs) * 2
ysl = len(ys) * 2

fi = [ [ 0 for x in range(xsl) ] for y in range(ysl) ]

for (a, b, c) in lvs:
    x = xti[c] * 2
    for y in range(yti[a] * 2, yti[b] * 2 + 1):
        fi[y][x] = -1

for (d, e, f) in lhs:
    y = yti[d] * 2
    for x in range(xti[e] * 2, xti[f] * 2 + 1):
        fi[y][x] = -1

q = [(xti[0] * 2, yti[0] * 2)]

s = 0
while q:
    (cx, cy) = q.pop(-1)
    if cx < 0 or cx >= xsl or cy < 0 or cy >= ysl:
        continue
    
    if fi[cy][cx] != 0:
        continue

    if cx == 0 or cx == xsl - 1 or cy == 0 or cy == ysl - 1:
        print('INF')
        exit()

    fi[cy][cx] = 1
    s += (xs[(cx + 1) // 2] - xs[cx // 2]) * (ys[(cy + 1) // 2] - ys[cy // 2])
    q.append((cx, cy - 1))
    q.append((cx + 1, cy))
    q.append((cx, cy + 1))
    q.append((cx - 1, cy))

print(s)
#for xl in fi:
#    print(xl)




### FIXED CODE ###

#!/usr/bin/python3


(n, m) = map(int, input().split())

xti = {}
yti = {}
xti[0] = -1
yti[0] = -1

lvs = []
for i in range(n):
    (a, b, c) = map(int, input().split())
    yti[a] = -1
    yti[b] = -1   
    xti[c] = -1
    lvs.append((a, b, c))

lhs = []
for i in range(m):
    (d, e, f) = map(int, input().split())
    yti[d] = -1
    xti[e] = -1   
    xti[f] = -1
    lhs.append((d, e, f))

xs = sorted(xti.keys())
for (i, x) in enumerate(xs):
    xti[x] = i
    
ys = sorted(yti.keys())
for (i, y) in enumerate(ys):
    yti[y] = i

xsl = (len(xs) + 1) * 2
ysl = (len(ys) + 1) * 2

fi = [ [ 0 for x in range(xsl) ] for y in range(ysl) ]

for (a, b, c) in lvs:
    x = xti[c] * 2 + 1
    for y in range(yti[a] * 2 + 1, yti[b] * 2 + 1 + 1):
        fi[y][x] = 2

for (d, e, f) in lhs:
    y = yti[d] * 2 + 1
    for x in range(xti[e] * 2 + 1, xti[f] * 2 + 1 + 1):
        fi[y][x] = 2

(cx, cy) = (xti[0] * 2, yti[0] * 2)
q = []
q.append((cx, cy))
fi[cy][cx] = 1
s = (xs[cx // 2] - xs[(cx - 1)// 2]) * (ys[cy // 2] - ys[(cy - 1) // 2])
dxs = [0, 1, 0, -1]
dys = [1, 0, -1, 0]

while q:
    (x, y) = q.pop(-1)

    for i in range(4):
        cx = x + dxs[i] * 2
        cy = y + dys[i] * 2
    
        if fi[cy][cx] != 0:
            continue

        pcx = x + dxs[i]
        pcy = y + dys[i]
        if fi[pcy][pcx] == 2:
            continue
        
        
        if cx == 0 or cx == xsl - 2 or cy == 0 or cy == ysl - 2:
            print('INF')
            exit()

        fi[cy][cx] = 1
        s += (xs[cx // 2] - xs[(cx - 1)// 2]) * (ys[cy // 2] - ys[(cy - 1) // 2])
        q.append((cx, cy))

print(s)

#for xl in fi:
#    print(xl)