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

# -*- coding: utf-8 -*-
x,y,z,k = map(int, input().split())

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

v = []


d = [e1+e2 for e1 in a for e2 in b]

d = sorted(d, reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e = sorted(e, reverse=True)

for i in range(k):
    print(e[i])


### FIXED CODE ###

# -*- coding: utf-8 -*-
x,y,z,k = map(int, input().split())

a = list(map(int,input().split()))
b = list(map(int,input().split()))
c = list(map(int,input().split()))
a.sort(reverse=True)
b.sort(reverse=True)
c.sort(reverse=True)


d = [e1+e2 for e1 in a for e2 in b]
d.sort(reverse=True)
d = d[:k]

e = [e1+e2 for e1 in d for e2 in c]
e.sort(reverse=True)


for i in range(k):
    print(e[i])
### BUGGY CODE ###

N = int(input())
S = []
ans = 0
for i in range(N):
    a = input()
    s = [ ]
    for j in range(10):
        s.append(a[j])
    s.sort()
    ans += S.count(s)
    S.append(s)
print(ans)

### FIXED CODE ###

N = int(input())
S = {}
ans = 0
for i in range(N):
    a = input()
    s = [ ]
    for j in range(10):
        s.append(a[j])
    s.sort()
    b =s[0]
    for k in range(1,10):
        b += s[k]
    if b in S:
        ans += S[b]
    else:
        S[b] = 0
    S[b] += 1
print(ans)
### BUGGY CODE ###

n,k=map(int,input().split())
s=list(map(int,input().split()))

while k>0:
  s[s.index(max(s))]=0
  k-=1
    
print(sum(s))

### FIXED CODE ###

import sys

n,k=map(int,input().split())
s=list(map(int,input().split()))
s.sort(reverse=True)

if k<len(s):
  for i in range(k):
    s[i]=0
else:
  for i in range(n):
    print(0)
    sys.exit()

print(sum(s))
### BUGGY CODE ###


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

    n = int(input())
    a = list(map(int, input().split()))
    A = []
    A_append = A.append
    cnt = 0

    for i in range(n-1):
        A_append((a[i]))
        x = sum(A) + a[i+1]
        if sum(A) > 0 and x > 0:
            y = -(x+1)
            cnt -= y
            a[i+1] += y

        elif sum(A) < 0 and x < 0:
            y = -(sum(A) - a[i+1])-1
            cnt += y
            a[i+1] += y

    if sum(a) == 0:
        cnt += 1

    print(cnt)

if __name__ == '__main__':
    main()

### FIXED CODE ###

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

def Chk(a, pos):
    cnt = 0
    tmp = 0

    for a in A:
        tmp += a

        if pos and tmp < 1:
            cnt += 1 - tmp
            tmp = 1
        elif not pos and tmp > -1:
            cnt += 1 + tmp
            tmp = -1

        pos = not pos
    return cnt

print(min(Chk(A, True), Chk(A, False)))
### BUGGY CODE ###

N = int(input())
A = list(map(int,input().split()))
total = 0
for i in range(N):
  for k in range(N):
    if i!=k and i<k:
      total+=A[i]*A[k]
print(total%(10**9+7)) 

### FIXED CODE ###

N = int(input())
A = list(map(int,input().split()))
total = 0
mod = 10**9+7
an = sum(A)

for i in range(N):
  total+=(an-A[i])*A[i]
s = total//2
print(s%mod)
### BUGGY CODE ###

#!/usr/bin/env python3
import sys


def solve(R: int, G: int, B: int, N: int):
    cnt= 0
    for r in range(0, N+1, R):
        for g in range(0, N + 1 - r, G):
            b = (N - r - g) / B
            if b % 1 == 0 and b >= 0:
                cnt += 1
            else:
                continue
            if N - r - g < 0:
                break

    print(cnt)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    R = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(R, G, B, N)

if __name__ == '__main__':
    main()


### FIXED CODE ###

#!/usr/bin/env python3
import sys


def solve(R: int, G: int, B: int, N: int):
    cnt= 0
    for r in range(0, N + 1, R):
        upper = N + 1 - r
        for g in range(0, upper, G):
            temp = upper-1-g
            if temp < 0:
                break
            b = temp / B
            if b % 1 == 0 and b >= 0:
                cnt += 1
            else:
                continue
    print(cnt)
    return


# Generated by 1.1.4 https://github.com/kyuridenamida/atcoder-tools  (tips: You use the default template now. You can remove this line by using your custom template)
def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    R = int(next(tokens))  # type: int
    G = int(next(tokens))  # type: int
    B = int(next(tokens))  # type: int
    N = int(next(tokens))  # type: int
    solve(R, G, B, N)

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

n=int(input())
ans=0
for i in range(1,n+1):
    a=sorted(set(str(i)))
    if a == ['3','5','7']:
        ans+=1
print(ans)



### FIXED CODE ###

import itertools as it
n=int(input())
ans=0
for nn in range(3,10):
    l=[ i for i in it.product(['3','5','7'], repeat=nn)]
    for ll in l:
        if int(''.join(ll)) <= n:
            if len(set(ll)) ==3:
                ans+=1

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

import sys
input = sys.stdin.readline
S = list(input())
N = len(S)

def solver(n,m,idx):
    N = n+m
    if (n-m)%2 == 0:
        ans = [0] * N
        ans[idx[0]] = (n+m)//2
        ans[idx[1]] = (n+m)//2
    else:
        ans = [0] * N
        if m%2 == 1:
            ans[idx[1]] = (n+m)//2 + 1
            ans[idx[0]] = (n+m)//2
        else:
            ans[idx[0]] = (n+m)//2 + 1
            ans[idx[1]] = (n+m)//2
    return ans    
    
    
        
        
ans = []
m = 0
n = 0
flagL = False
idx = []
for s in S:
    if s == 'R':
        if flagL:
            ans = ans + solver(n,m,idx)
            n = 0
            m = 0
            flagL = False
        n += 1
    elif s == 'L':
        if not flagL:
            flagL = True
            idx = [n-1,n]
        m += 1 
ans = ans + solver(n,m,idx)
    
print(*ans,sep = ' ')

### FIXED CODE ###

#import sys
#input = sys.stdin.readline
S = list(input())
N = len(S)

def solver(n,m,idx):
    if (n-m)%2 == 0:
        ans[idx[0]] = (n+m)//2
        ans[idx[1]] = (n+m)//2
    else:
        if m%2 == 1:
            ans[idx[1]] = (n+m)//2 + 1
            ans[idx[0]] = (n+m)//2
        else:
            ans[idx[0]] = (n+m)//2 + 1
            ans[idx[1]] = (n+m)//2
    return    
    
    
        
        
ans = [0] * N
m = 0
n = 0
flagL = False
idx = []
for i,s in enumerate(S):
    if s == 'R':
        if flagL:
            solver(n,m,idx)
            n = 0
            m = 0
            flagL = False
        n += 1
    elif s == 'L':
        if not flagL:
            flagL = True
            idx = [i-1,i]
        m += 1 
solver(n,m,idx)
    
print(*ans,sep = ' ')
### BUGGY CODE ###

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)
for i in range(k+1):
    ans+=ue*inv[n-1-i]*inv[i]*m*po%mod
    po*=iii
print(ans%mod)

### FIXED CODE ###

n,m,k=map(int,input().split())
mod=998244353
if m==1:print(0 if k!=n-1 else 1);exit()
fact=[1]*(n-1+1)
inv=[1]*(n-1+1)
for i in range(2,n-1+1):
    fact[i]=i*fact[i-1]%mod
inv[-1]=pow(fact[-1],mod-2,mod)
for i in range(n-1,1,-1):
    inv[i-1]=inv[i]*i%mod
ans=0
po=pow(m-1,n-1,mod)*m%mod
ue=fact[n-1]
iii=pow(m-1,mod-2,mod)%mod
for i in range(k+1):
    ans+=ue*inv[n-1-i]%mod*inv[i]%mod*po%mod
    po*=iii
    po%=mod
print(ans%mod)
### BUGGY CODE ###

from collections import deque
n=int(input())
league=[deque(map(int,input().split())) for _ in range(n)]

total_match=n*(n-1)//2
match=0
day=0

for _ in range(total_match):
    day+=1
    today_match=[]

    for i in range(n):
        if i in today_match:
            continue
        if league[i]:
            m=league[i][0]-1
            if m in today_match:
                continue
            if league[m] and league[m][0]-1==i:
                today_match.extend((league[i].popleft()-1, league[m].popleft()-1))
    if not today_match:
        day=-1
        break
    match+=len(today_match)//2
    if match>=total_match:
        break

print(day)

### FIXED CODE ###

import sys
input = sys.stdin.buffer.readline
sys.setrecursionlimit(10 ** 7)

N = int(input())
pair = N * (N - 1) // 2
ptoi = dict()

i = 0
for x in range(1, N):
    for y in range(x + 1, N + 1):
        ptoi[(x, y)] = i
        ptoi[(y, x)] = i
        i += 1

edge = [[] for _ in range(pair)]
indeg = [0] * pair
for i in range(1, N+1):
    inp = list(map(int, input().split()))
    for s, t in zip(inp[:-1], inp[1:]):
        edge[ptoi[(i, s)]].append(ptoi[(i, t)])
        indeg[ptoi[(i, t)]] += 1


now = [i for i, d in enumerate(indeg) if d == 0]
day = 0
while now:
    nxt = []
    while now:
        s = now.pop()
        for t in edge[s]:
            if indeg[t] <= 0:
                continue
            indeg[t] -= 1
            if indeg[t] == 0:
                nxt.append(t)
    day += 1
    now = nxt

if all(i <= 0 for i in indeg):
    print(day)
else:
    print(-1)
### BUGGY CODE ###

N=int(input())
A = [int(x) for x in input().split()]

ans=1
if 0 in A:
    ans = 0
else:
    for a in A:
        A.reverse()
        if a > 10**18:
            ans = -1
            break
        else:
            ans *= a
            if ans > 10**18:
                ans = -1
print(ans)

                


### FIXED CODE ###

N=int(input())
A = [int(x) for x in input().split()]

ans=1
if 0 in A:
    ans = 0
else:
    A.sort(reverse=True)
    for a in A:
        if a > 10**18:
            ans = -1
            break
        else:
            ans *= a
            if ans > 10**18:
                ans = -1
                break
print(ans)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())

count=0
for ri in range(int(n/r)+1):
    for gi in range(int(n/g)+1):
        if (n-ri*r-gi*g)%b==0 and (n-ri*r-gi*g)/b>=0:
            count+=1

print(count)


### FIXED CODE ###

r,g,b,n=map(int,input().split())

count=0
for ri in range(int(n/r)+1):
    for gi in range(int((n-ri*r)/g)+1):
        sumc=n-ri*r-gi*g
        if sumc<0:
            break
        if sumc%b==0:
            count+=1

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

n = int(input())
s = []
ans = 0
for _ in range(n):
    s.append("".join(sorted(str(input()))))
for i in range(n-1):
    for j in range(i+1, n):
        if s[i] == s[j]: ans +=1
print(ans)

### FIXED CODE ###

n = int(input())
s = []
d = {}
for _ in range(n):
    s.append("".join(sorted(str(input()))))
for si in s:
    if si not in d.keys():
        d[si] = 1
    else: d[si] += 1
ans = 0
val = d.values()
for v in val:
    ans += v*(v-1)/2
print(int(ans))
### BUGGY CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint,time,random
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

def cal(T):
    res = 0
    last = [0] * 26
    for day in range(D):
        t = T[day]; t -= 1
        last[t] = 0
        res += s[day][t]
        for i in range(26):
            if i == t: continue
            last[i] += 1
            res -= c[i] * last[i]
    return res
def check_change(td,tq):
    global score,res
    old_q = res[td]
    res[td] = tq
    now = cal(res)
    if now > score:
        score = now
    else:
        res[td] = old_q

start_time = time.time()
n = 26
D = inp()
c = inpl()
s = []
max_s = []
for i in range(D):
    tmp = inpl()
    mx = 0; ind = -1
    for j in range(n):
        if tmp[j] > mx:
            mx = tmp[j]
            ind = j
    max_s.append(ind+1)
    s.append(tmp)

last = [0] * n
res = [-1] * D
for d in range(D):
    ans = -1
    mx = -INF
    for i in range(n):
        now = s[d][i]
        for j in range(n):
            if i == j: continue
            now -= s[d][j] * (last[j]+1)
        if now > mx:
            mx = now
            ans = i
    res[d] = ans+1
    for j in range(n):
        last[j] += 1
        if j == ans: last[j] = 0
score = cal(res)
# print(now_score)
for x in itertools.combinations(range(D), 2):
    old = []
    if sum(x^y for x,y in zip(res,max_s)) == 0: continue
    for i in range(2):
        old.append(res[x[i]])
        res[x[i]] = max_s[x[i]]
    now = cal(res)
    if now > score:
        score = now
    else:
        for i in range(2):
            res[x[i]] = old[i]
while time.time() - start_time < 1.83:
    td,tq = random.randrange(0,D), random.randrange(1,n+1)
    check_change(td,tq)

for x in res:
    print(x)

### FIXED CODE ###

from collections import Counter,defaultdict,deque
from heapq import heappop,heappush,heapify
import sys,bisect,math,itertools,fractions,pprint
sys.setrecursionlimit(10**8)
mod = 10**9+7
INF = float('inf')
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))

n = 26
D = inp()
c = inpl()
s = [inpl() for _ in range(D)]
last = [0] * n
res = [-1] * D
for d in range(D):
    ans = -1
    mx = -INF
    for i in range(n):
        now = s[d][i]
        for j in range(n):
            if i == j: continue
            now -= s[d][j] * (last[j]+1)
        if now > mx:
            mx = now
            ans = i
    res[d] = ans+1
    for j in range(n):
        last[j] += 1
        if j == ans: last[j] = 0
for x in res:
    print(x)
### BUGGY CODE ###

import math
n,a,b= map(int, input().split())
mod = 10 ** 9 + 7
def power_func(a,n,mod):
  bi=str(format(n,"b"))#2進表現に
  res=1
  for i in range(len(bi)):
    res=(res*res) %mod
    if bi[i]=="1":
      res=(res*a) %mod
  return res


def cmb(n, r, mod):
    if (r < 0 or r > n):
        return 0
    r=min(r,n-r)

    return g1[n] * g2[r] * g2[n - r] % mod


N =10 ** 9 # 出力の制限
g1 = [1, 1]  # 元テーブル
g2 = [1, 1]  # 逆元テーブル
inverse = [0, 1]  # 逆元テーブル計算用テーブル

for i in range(2, N + 1):
    g1.append((g1[-1] * i) % mod)
    inverse.append((-inverse[mod % i] * (mod // i)) % mod)
    g2.append((g2[-1] * inverse[-1]) % mod)

ans=(power_func(2,n,mod)-1-cmb(n,a,mod)-cmb(n,b,mod))%mod
print(ans)

### FIXED CODE ###

import math
n,c,d= map(int, input().split())
mod = pow(10,9)+7

def comb(n,k):
    x=1
    y=1
    for i in range(1,k+1):
        x*=(n+1-i)
        x%=mod
        y*=i
        y%=mod
    return x*pow(y,mod-2,mod)


ans=(pow(2,n,mod)-1-comb(n,c)-comb(n,d))%mod
print(ans)
### BUGGY CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(n+1):
    for j in range(n+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            cnt+=1
print(cnt)

### FIXED CODE ###

r,g,b,n=map(int,input().split())
cnt=0
for i in range(n//r+1):
    for j in range(n//g+1):
        if (n-i*r-j*g)%b==0 and n-i*r-j*g>=0:
            cnt+=1
print(cnt)
### BUGGY CODE ###

N,Q = map(int,input().split())
S = input()
LR = [input().split() for _ in range(Q)]
for lr in LR:
    l = int(lr[0])
    r = int(lr[1])
    print(S[l-1:r].count('AC'))

### FIXED CODE ###

import bisect

N,Q = map(int,input().split())
S = input()
L = []
for i in range(N):
    if S[i:i+2] == 'AC':
        L.append(i)
for i in range(Q):
    l,r = map(int,input().split())
    a = bisect.bisect_left(L,l-1)
    b = bisect.bisect_right(L,r-2)
    print(b-a)
### BUGGY CODE ###

N=int(input())
s=[sorted(list(input())) for i in range(N)]
s.sort()

counter=0

i=0
while i<N-1:
  j=i+1
  while j<N:
    if s[i]==s[j]:
	    counter+=1
	    j+=1
    else:
      break
    
  i+=1
  
print(counter)

### FIXED CODE ###

N=int(input())
s=[''.join(sorted(input())) for i in range(N)]


dic={}
counter=0
for i in range(N):
  if (s[i] in dic.keys())==True:
    counter+=dic[s[i]]
    dic[s[i]]=dic[s[i]]+1
  else:
    dic[s[i]]=1

print(counter)
### BUGGY CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = list(map(int, input().split()))

    tmp = 0
    for i in range(len(inlis)-k+1):
        if tmp < sum(inlis[i:i+k]):
            tmp = sum(inlis[i:i+k])
            tmplis = inlis[i:i+k]
    ans = sum(map(kitaichi, tmplis))
    print(ans)



    
if __name__ == "__main__":
    main()


### FIXED CODE ###

def kitaichi(x):
    return x * (x+1) / (2 * x)

def main():
    n, k = map(int, input().split())
    inlis = tuple(map(int, input().split()))
    kitalis = list(map(kitaichi, inlis))
    kitadic = {}
    kitadic[0] = kitalis[0] 
    for i in range(1, n):
        kitadic[i] = kitadic[i-1] + kitalis[i]
       
    tmp = 0
    if n == k:
        print(kitadic[n-1])
    else:
        for i in range(n - k):
            atai = kitadic[i+k] - kitadic[i]
            if tmp < atai:
                tmp = atai
        print(tmp)
        exit()



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

from fractions import gcd
N, M = map(int, input().split())
if M%N==0:
  print(M//N)
else:
  c = M%N
  b = M//N
  ans = 0
  x = M
  for i in range(1,b+1):
    x -= N
    if gcd(i,x)>ans:
      ans = gcd(i,x)
  print(ans)
  print(' ')

### FIXED CODE ###

N, M = map(int, input().split())
ls = []
for i in range(1,M+1):
  if M%i==0:
    j = M//i
    if i<=M//N:
      ls += [i]
    if j<=M//N:
      ls += [j]
  if M**0.5<i:
    break
print(max(ls))
### BUGGY CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = {start}
    w = defaultdict(lambda: -1)
    w[start] = 0
    while len(open) != 0:
        target = min(open, key=lambda x: w[x])
        open.remove(target)
        for next in E[target]:
            if w[next] == -1:
                open.add(next)
                w[next] = w[target] + 1
    return w[end] // 3


print(bfs(E, S, T))


### FIXED CODE ###

import sys
from collections import Counter, deque, defaultdict
from itertools import accumulate, permutations, combinations, takewhile, compress, cycle
from functools import reduce
from math import ceil, floor, log10, factorial
import math

sys.setrecursionlimit(1000000)

MOD = 10 ** 9 + 7

INF = float('inf')
# N = int(input())
# A = [int(x) for x in input().split()]
# A = [int(input()) for _ in range(N)]
# dp = [[0] * 100 for _ in range(100)]
# dp = defaultdict(lambda: float('inf'))
# print('hoge', file=sys.stderr)

N, M = [int(x) for x in input().split()]

# E = {set() for _ in range(N + 1)}
E = defaultdict(lambda: set())

for i in range(M):
    u, v = [int(x) for x in input().split()]
    u -= 1
    v -= 1
    E[3 * u].add(3 * v + 1)
    E[3 * u + 1].add(3 * v + 2)
    E[3 * u + 2].add(3 * v)

S, T = [int(x) for x in input().split()]
S = 3 * (S - 1)
T = 3 * (T - 1)


def bfs(e, start, end):
    open = deque([start])
    w = dict()
    w[start] = 0
    while len(open) != 0:
        target = open.popleft()
        for next in E[target]:
            if not next in w:
                open.append(next)
                w[next] = w[target] + 1

    return w[end] // 3 if end in w else -1


print(bfs(E, S, T))
### BUGGY CODE ###

N = int(input())
a = input().split()
sum0 = 0

for i in range(N):
  a[i] = int(a[i])
  sum0 += a[i]

for i in range(N-1):
  if(i == 0):
   b = a[0]
   min = abs(2*b-sum0)
  elif(1<=i<=int(N/2)-1):
   b = a[:i+1]
   #print(b)
   tmp = abs(2*sum(b)-sum0)
   if(min > tmp):
      min = tmp
  else:
   b = a[i+1:]
   #print(b)
   tmp = abs(2*sum(b)-sum0)
   if(min > tmp):
      min = tmp
  #print(min)
print(min)
 

### FIXED CODE ###

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

min_dif = float('inf')
s1 = 0
for i in range(N):
  if(i != N-1):
   s1 += A[i]
   s2 = sum_all - s1
   tmp_dif = abs(s1 - s2)
   min_dif = min(min_dif,tmp_dif)
print(min_dif)
### BUGGY CODE ###

N, M, K = map(int, input().split())
mod = 998244353

facs = [1] * (N + 1)
nfac = 1
for i in range(1, N):
    nfac = nfac * i %mod
    facs[i] = nfac

s = 0
for i in range(0, K+1):
    patterns = facs[N-1] * pow(facs[i], mod-2, mod) * pow(facs[N-1-i], mod-2, mod) % mod
    d = patterns * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)

### FIXED CODE ###

N, M, K = map(int, input().split())
mod = 998244353

facs = [1] * N
invs = [1] * N
nfac = 1
for i in range(1, N):
    nfac = nfac * i % mod
    facs[i] = nfac
    invs[i] = pow(facs[i], mod-2, mod)

s = 0
for i in range(K+1):
    d = facs[N-1] * invs[i] * invs[N-1-i] \
        * M * pow(M-1, N-1-i, mod) % mod
    s = (s + d) % mod

print(s)
### BUGGY CODE ###

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

list = []
count = 1

for i in range(a[0]-a[1]+1):  # 始まりの位置
    for j in range(a[1]):
        count *= b[i+j]
    list.append(count)
    count = 1
for i in range(len(list)-1):
    if list[i+1] > list[i]:
        print('Yes')
    else:
        print('No')


### FIXED CODE ###

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

for i in range(k,n):
    if a[i] > a[i-k]:
        print('Yes')
    else:
        print('No')
### BUGGY CODE ###

D,N = map(int,input().split())
ans = []
for i in range(100000000):
  if i%(100**D) == 0:
    ans.append(i)
print(ans[N])


### FIXED CODE ###

import sys
d,n = map(int,input().split())
num = 100**d
if n == 100:
  print(101*num)
  sys.exit()
if d == 0:
  print(n)
else:
  print((100**d)*n)
### BUGGY CODE ###

#H,W = map(int,input().split())
N=int(input())
A = list(map(int,input().split()))
#S=str(input())
c=[]
for i in range(1,N+1):
    C=A.count(i)
    c.append(C)

for k in c:

    print(k)


### FIXED CODE ###

#H,W = map(int,input().split())
N=int(input())
A = list(map(int,input().split()))
#S=str(input())
c=[0]*N
for i in A:
    c[i-1]+=1
for k in c:
    print(k)
### BUGGY CODE ###


n,m = list(map(int,input().split()))
d = []
spr = [[False]*m]
s = 1<<0
for i in range(m):
  a,b = list(map(int,input().split()))
  d.append( ((1<<a)-1) ^ ((1<<b)-1) )

ans = float('inf')
for bit in range(1<<n):
  spr = [True for _ in range(m)]
  for k in range(m):
      if (d[k] & bit) > 0:
        spr[k] = False
  if sum(spr) == 0:
      ans = min(ans, sum([1 for i in range(n) if bit & 1<<i]))
      print(ans)
      exit()


     



### FIXED CODE ###


n,m = list(map(int,input().split()))
d = [0]*m
spr = [True]*m
ma = 0
mi = 0
for i in range(m):
    a,b = list(map(int,input().split()))
    d[i] = [a,b]

d = sorted(d)
pre = d[0][1]
ans = 1
for i,(a,b) in enumerate(d):
  if a < pre:
    if b < pre:
      pre = b
  else:
    ans += 1
    pre = b

print(ans)