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

n,m = map(int,input().split())
first = []
second = []
for i in range(m):
    a,b =  map(int,input().split())
    if a == 1:
        first.append(b)
    if b == n:
        second.append(a)

for i in range(len(first)):
    if first[i] in second:
        print('POSSIBLE')
        exit()
else:
    print('IMPOSSIBLE')

### FIXED CODE ###

n,m = map(int,input().split())
c = []
for i in range(m):
    a,b =  map(int,input().split())
    if a == 1:
        c.append(b)
    if b == n:
        c.append(a)
        
if len(c) == len(set(c)):
    print('IMPOSSIBLE')
else:
    print('POSSIBLE')
### BUGGY CODE ###

from collections import deque

s = deque(input().rstrip())
q = int(input())
for i in range(q):
    query = input()
    if int(query[0]) == 1:
        s.reverse()
    else:
        _, f, c = query.split()
        if int(f) == 1:
            s.appendleft(c)
        else:
            s.append(c)

print(''.join(s))

### FIXED CODE ###

from collections import deque

s = deque(input().rstrip())
q = int(input())

reverse = False
for i in range(q):
    query = input()
    if int(query[0]) == 1:
        reverse = not reverse
    else:
        _, f, c = query.split()
        if int(f) == 1:
            if reverse:
                s.append(c)
            else:
                s.appendleft(c)
        else:
            if reverse:
                s.appendleft(c)
            else:
                s.append(c)
if reverse:
    s.reverse()

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

s = list(input())
t = list(input())

f = True
for i in t:
    if(not i in s):
        f = False
i = 0
if(not f):
    print(-1)
else:
    for x in t:
         
        while(s[i % len(s)] != x):
            i+=1
        i+=1
    print(i)







### FIXED CODE ###

s = input()
t = input()
d = {i:[] for i in "abcdefghijklmnopqrstuvwxyz"}
for i in range(len(s)):
    d[s[i]].append(i)
for i in t:
    if len(d[i]) == 0:
        print(-1)
        exit()

def binary_search(arr, k):
    l, r = 0, len(arr)-1
    while l <= r:
        m = l+r >> 1
        if arr[m] < k:
            l = m+1
        else:
            r = m-1
    return l

a, b = 0, 0
for i in t:
    j = binary_search(d[i], a)
    if len(d[i]) <= j:
        a = 0
        b += 1
        j = binary_search(d[i], 0)
    a = d[i][j] + 1
print(b * len(s) + a)
### BUGGY CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)
    items = [(next(data), next(data)) for _ in range(N)]
    Q = next(data)

    H = min(N + 1, 1 << 10)
    Hb = (H - 1).bit_length()
    dp = [[0] * (MX + 1) for _ in range(H)]
    for i in range(1, H):
        v, w = items[i - 1]
        dpi = dp[i]
        dpip = dp[i >> 1]
        for j in range(w):
            dpi[j] = dpip[j]
        for j in range(w, MX + 1):
            dpi[j] = max(dpip[j], dpip[j - w] + v)

    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue
        ans = []
        for i in range(1 << (v.bit_length() - Hb)):
            node = v
            value = weight = 0
            while node >= H:
                if i & 1:
                    iv, iw = items[node - 1]
                    value += iv
                    weight += iw
                node >>= 1
                i >>= 1
            if weight > L:
                continue
            ans.append(value + dp[node][L - weight])
        print(max(ans))

if __name__ == '__main__':
    main()


### FIXED CODE ###

import sys
MX = 10**5
def main():
    data = map(int, sys.stdin.buffer.read().split())
    N = next(data)

    H = min(N + 1, 1 << 10)
    dp = [None] * H
    dp[0] = [0] * (MX + 1)
    IV, IW = [], []
    i = 1
    for v, w in zip(data, data):
        if i < H:
            dpi = dp[i >> 1][:]
            dp[i] = dpi
            for j in range(MX, w - 1, -1):
                dpi[j] = max(dpi[j], dpi[j - w] + v)
        else:
            IV.append(v)
            IW.append(w)
        i += 1
        if i > N:
            break

    Q = next(data)
    for v, L in zip(data, data):
        if v < H:
            print(dp[v][L])
            continue

        item_values = []
        item_weights = []
        while v >= H:
            item_values.append(IV[v - H])
            item_weights.append(IW[v - H])
            v >>= 1

        l = len(item_values)
        V = [0] * (1 << l)
        W = [0] * (1 << l)
        ans = dp[v][L]
        for i in range(1, 1 << l):
            msb = i & (-i)
            msbb = msb.bit_length() - 1
            wi = W[i - msb] + item_weights[msbb]
            W[i] = wi
            if wi <= L:
                vi = V[i - msb] + item_values[msbb]
                ans = max(ans, vi + dp[v][L - wi])
                V[i] = vi
        print(ans)

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

def find(tab, a):
    if tab[a]==-1:
        return a
    tab[a] = find(tab, tab[a])
    return tab[a]

def union(tab, a, b):
    p1, p2 = find(tab, a), find(tab, b)
    if p1 != p2:
        tab[p1] = p2

def count(tab):
    from collections import defaultdict
    dic = defaultdict(lambda: 0)
    for i in range(len(tab)):
        dic[find(tab, i)]+=1
    ans=0
    for k, cnt in dic.items():
        if cnt>1:
            ans += cnt*(cnt-1)//2
    return ans

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [-1]*N
arr = [count(tab)]

for a, b in reversed(ABs):
    union(tab, a-1, b-1)
    arr.append(count(tab))

maxp = arr[-1]
for cp in reversed(arr[:-1]):
    print(maxp-cp)


### FIXED CODE ###

import sys
sys.setrecursionlimit(100000)

def find(tab, a):
    if tab[0][a]==a:
        return a
    tab[0][a] = find(tab, tab[0][a])
    return tab[0][a]

def union(tab, a, b):
    p1, p2 = (find(tab, a), find(tab, b))
    if p1 != p2:
        tab[0][p1] = p2
        tab[1][p2] += tab[1][p1]

def size(tab, a):
    return tab[1][a]

N, M = [int(a) for a in input().split(" ")]
ABs = [[int(a) for a in input().split(" ")] for i in range(M)]
tab = [[i for i in range(N)], [1 for i in range(N)]]
arr = []

for a, b in reversed(ABs):
        a, b = (a-1, b-1)
        pa, pb = (find(tab, a), find(tab, b))
        na, nb = (size(tab, pa), size(tab, pb))
        if pa!=pb:
            dn = ((na+nb)*(na+nb-1)//2)-(na*(na-1)//2)-(nb*(nb-1)//2)
            arr.append(dn)
            union(tab, a, b)
        else:
            arr.append(0)

acc = 0
for cp in reversed(arr):
    acc += cp
    print(acc)
### BUGGY CODE ###

from collections import Counter
from collections import deque
from scipy.special import comb
from copy import deepcopy

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

ldeq = deque()
rdeq = deque(A)

def process(mdeq):
    cm = Counter(mdeq)
    cnt = 0
    for key in cm:
        cnt += comb(cm[key], 2)
    print(int(cnt))

for i in range(N):
    a = rdeq.popleft()
    mdeq = deepcopy(rdeq)
    mdeq.extendleft(ldeq)
    process(mdeq)
    ldeq.append(a)

### FIXED CODE ###

from collections import Counter

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

cA = Counter(A)

allS = 0
for key in cA:
    allS += cA[key] * (cA[key] - 1) / 2

for i in range(N):
    if A[i] in cA.keys():
        print(int(allS - (cA[A[i]] - 1)))
    else:
        print(int(allS))
### BUGGY CODE ###

N = int(input())
P_ls = list(map(int, input().split(' ')))
rst = 0
for i in range(N):
    val = P_ls[i]
    if min(P_ls[: i + 1]) == val:
        rst += 1
print(rst)

### FIXED CODE ###

N = int(input())
P_ls = list(map(int, input().split(' ')))
rst, min_val = 0, 10 ** 6
for i in P_ls:
    if min_val >= i:
        rst += 1
        min_val = i
print(rst)
### BUGGY CODE ###


H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = []
done = {}
for i in range(Q):
    L, R = tests[i]
    if (L, R) in done:
        scores.append(done[(L, R)])
    elif L == R:
        scores.append(0)
    else:
        x, y = stage[L]
        score = 0
        nowL = L
        while nowL < R:
            if (nowL, R) in done:
                score += done[(nowL, R)]
                break
            new_x, new_y = stage[nowL + D]
            score += abs(new_x - x) + abs(new_y - y)
            x = new_x
            y = new_y
            nowL += D
        scores.append(score)
        done[(L, R)] = score

for score in scores:
    print(score)



### FIXED CODE ###

import numpy as np

H, W, D = [int(x) for x in input().strip().split(' ')]
stage = {}
for i in range(H):
    nums = [int(x) for x in input().strip().split(' ')]
    for j in range(W):
        stage[nums[j]] = [i + 1, j + 1]
Q = int(input())
tests = []
for _ in range(Q):
    tests.append([int(x) for x in input().strip().split(' ')])

scores = np.zeros([H * W + 1]).astype(np.int)
for i in range(H * W, 0, -1):
    if i + D > H * W:
        scores[i] = 0
    else:
        x, y = stage[i]
        ox, oy = stage[i + D]
        scores[i] = scores[i + D] + abs(x - ox) + abs(y - oy)

for i in range(Q):
    L, R = tests[i]
    print(scores[L] - scores[R])
### BUGGY CODE ###

#import re
X = raw_input()
iter = 100000
#pat = re.compile('(ST)')
for i in xrange(iter):
    if ('ST' not in X):
	break
    X = X.replace('ST','')
    if len(X) == 0:
        break
print len(X)

### FIXED CODE ###

import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time,copy,functools
from collections import deque

sys.setrecursionlimit(10**7)
inf = 10**20
mod = 10**9 + 7

DR = [1, -1, 0, 0]
DC = [0, 0, 1, -1]

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]
def LF(): return [float(x) for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def I(): return int(sys.stdin.readline())
def F(): return float(sys.stdin.readline())
def S(): return input()
     
def main():
    x = S()
    s_cnt = 0
    removed = 0
    for c in x:
        if c == 'S':
            s_cnt += 1
        if c == 'T':
            if s_cnt > 0:
                s_cnt -= 1
                removed += 2
    print(len(x) - removed)
main()
### BUGGY CODE ###

import math
def parent(i):
    return math.floor(i / 2)

def get_largest(i):
    l = i << 1
    r = l + 1
    largest = None
    size = len(A) - 1
    if l <= size and A[i] < A[l]:
        largest = l
    else:
        largest = i
    if r <= size and A[largest] < A[r]:
        largest = r
    return largest


def max_heapify(i):
    largest = get_largest(i)
    x = i
    while largest is not x:
        tmp = A[x]
        A[x] = A[largest]
        A[largest] = tmp
        x = largest
        largest = get_largest(x)

def extract():
    m = A[1]
    A[1] = A[-1]
    A.pop()
    max_heapify(1)
    return m

def insert_key(key):
    A.append(key)
    i = len(A) - 1
    while 1 < i and A[parent(i)] < A[i]:
        tmp = A[i]
        A[i] = A[parent(i)]
        A[parent(i)] = tmp
        i = parent(i)

inp = input()
A = [None]

while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(extract())
    elif inp[0] == 'i':
        insert_key(int(inp[7:]))
    inp = input()

### FIXED CODE ###

import math
import heapq

A = []
inp = input()
while True:
    if inp == 'end':
        break
    elif inp[0] == 'e':
        print(-heapq.heappop(A))
    elif inp[0] == 'i':
        heapq.heappush(A, -int(inp[7:]))
    inp = input()
### BUGGY CODE ###

K=int(input())
import math
S=0
for i in range(1,K+1):
    for j in range(1,K+1):
        for k in range(1,K+1):
            S+=math.gcd(math.gcd(i,j),k)
print(S)

### FIXED CODE ###

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

S = input()
N = len(S)
S = "x"+S+"x"
L = [1]*N
 
cnt = 0
m1 = [0]*N
m2 = [0]*N
while m2 != L:
  m2 = m1[:]
  m1 = L[:]
  tmp = L[:]
  for i in range(N):
    if L[i] == 0:
      pass
    elif S[i+1] == "R" and S[i+2]!="x":
      tmp[i] -= L[i]
      tmp[i+1] += L[i]
    elif S[i+1] == "L" and S[i]!="x":
      tmp[i] -= L[i]
      tmp[i-1] += L[i]
  L = tmp[:]
  cnt += 1

if cnt%2 == 1:
  print(' '.join(map(str,m1)))
else:
  print(' '.join(map(str,L)))

### FIXED CODE ###

S = input()
N = len(S)
L = [1]*N

for i,s in enumerate(S):
  if s == "R":
    s2 = S[i+1]
    if s2 == "R":
      L[i+2] += L[i]
      L[i] = 0

for i in range(N-1,-1,-1):
  s = S[i]
  if s == "L":
    s2 = S[i-1]
    if s2 == "L":
      L[i-2] += L[i]
      L[i] = 0

print(*L)
### BUGGY CODE ###

R, G, B, N = [int(n) for n in input().split()]

count = 0
for r in range(N//R + 1):
    for g in range((N-r*R)//G + 1):
        b_ = N - (R * r + G * g) 
        if b_ % B == 0 and 0 <= b_ / B <=  N//B:
                count += 1

print(count)

### FIXED CODE ###

R, G, B, N = [int(n) for n in input().split()]

count = 0
for r in range(N//R + 1):
    for g in range((N-r*R)//G + 1):
        b_ = N - (R * r + G * g) 
        if b_ % B == 0:
                count += 1

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

N=int(input())
s=[str(sorted(input())) for i in range(N)]
ans=0
for i in set(s):
    c=0
    for j in s:
        if i ==j:c+=1
    ans+=c*(c-1)//2
print(ans)

### FIXED CODE ###

N=int(input())
s=sorted([str(sorted(input())) for i in range(N)])+[""]
ans=c=0
j=s[0]
for i in s[1:]:
    if i==j:
        c+=1
    else:
        j=i
        ans+=c*(c+1)//2
        c=0
print(ans)
### BUGGY CODE ###

from collections import Counter


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return (n * (n - 1)) // 2


N = int(input())
A = list(map(int, input().split()))
for k in range(N):
    c = Counter(A[:k] + A[k + 1:])

    print(sum(map(choose, c.values())))


### FIXED CODE ###

from collections import Counter


def choose(n: int) -> int:
    if n < 2:
        return 0
    else:
        return (n * (n - 1)) // 2


N = int(input())
A = list(map(int, input().split()))
c = Counter(A)
d = {key: choose(value) for key, value in c.items()}
if len(d) > 1:
    sum_d = sum(d.values())
    for a in A:
        print(sum_d - d[a] + choose(c[a] - 1))
else:
    ans = choose(N - 1)
    for _ in range(N):
        print(ans)
### BUGGY CODE ###

import sys

N = int(sys.stdin.readline())
A = sorted(list(map(int, sys.stdin.readline().split(' '))))

ans = 0
while len(A) > 0:
    if not (len(A) > 1 and A[0] == A[1]):
        ans += 1
    A = [a for a in A if a % A[0] != 0]

print(ans)


### FIXED CODE ###

from collections import Counter
import numpy as np

A_MAX = 10 ** 6 + 1

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

dp = np.zeros(shape=A_MAX, dtype=np.int64)

if A[1] == 1:
    print(1)
elif A[1] > 1:
    print(0)
else:
    for a in A.keys():
        multiples = np.arange(a, A_MAX, a)
        np.add.at(dp, multiples, 1)

    ans = 0
    for a, count in A.items():
        if count > 1:
            continue
        if dp[a] == 1:
            ans += 1

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

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:
    to[b].append(a)
subtree = [[i] for i in range(N+1)]
for j in range(N, 0, -1):
    for u in to[j]:
        subtree[u].extend(subtree[j])
ans = [0] * N
for p, x in px_list:
    for u in subtree[p]:
        ans[u-1] += x
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 sys import stdin


if __name__ == "__main__":
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


### FIXED CODE ###

from sys import stdin


def main():
    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    len_S = len(S)
    cnt = 0
    for i in range(len_S):
        for j in range(i+3,len_S):
            if j == i+3:
                mod = int(S[len_S-j-1:len_S-i])%3
            else:
                mod = (mod+int(S[len_S-j-1]))%3
            if mod == 0:
                _ = int(S[len_S-j-1:len_S-i])
                if _%673==0:
                    cnt += 1
                    break
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)


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

    _in = [_.rstrip() for _ in stdin.readlines()]
    S =     _in[0]   # type:str
    # vvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvvv
    cnt = 0
    mod_arr = [0] * 2019
    mod_arr[0] += 1

    num, dec = 0, 1
    for s in S[::-1]:
        num += int(s)*dec
        num %= 2019
        dec *= 10
        dec %= 2019
        mod_arr[num] += 1

    for i in range(2019):
        if mod_arr[i] > 0:
            cnt += mod_arr[i]*(mod_arr[i]-1)//2
    # ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
    print(cnt)
### BUGGY CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
i=0
while cnt<sum(a)//2:
    temp=cnt
    cnt+=a[i]
    i+=1
print(min(abs(sum(a)-temp*2),abs(sum(a)-cnt*2)))

### FIXED CODE ###

n=int(input())
a=list(map(int,input().split()))
cnt=0
i=0
s=sum(a)
while cnt<s//2:
    temp=cnt
    cnt+=a[i]
    i+=1
    
print(min(abs(sum(a)-temp*2),abs(sum(a)-cnt*2)))
### BUGGY CODE ###

# TLEになる愚直コードなはず

import itertools
 
n, k = map(int, input().split())
arr = [i for i in range(n+1)]
 
a = 0
for i in range((n+1)-(k-1)):
    tmp = set()
    for group in itertools.combinations(arr, i+k):
        tmp.add(sum(group))
    #print(tmp)
    a += len(tmp)
 
print(a)

### FIXED CODE ###

import numpy as np

n, k = map(int, input().split())
ans = 0
mod = 10 ** 9 + 7
arr = np.arange(n+1)
a = np.cumsum(arr)
b = np.cumsum(arr[::-1])

for i in range(k, n+1+1):
    ans += b[i-1] - a[i-1] + 1
print(ans%mod)
### BUGGY CODE ###

import sys
n_list = map(int, sys.stdin.readlines())
n_max = max(n_list)

pn_candidates = range(2, n_max+1)
pn_list = []

while pn_candidates != []:
    pn = pn_candidates[0]
    pn_list.append(pn)
    pn_candidates = [x for x in pn_candidates[1:] if x % pn != 0]

for n in n_list:
    print len([pn for pn in pn_list if pn <= n])

### FIXED CODE ###

import sys
n_list = map(int, sys.stdin.readlines())
n_max = max(n_list)

pn_candidates = [0] + [1] * (n_max - 1)

pn = 2
while pn <= n_max:
    if pn_candidates[pn - 1] != 1:
        pn += 1
        continue

    i = 2
    while pn * i <= n_max:
        pn_candidates[pn * i - 1] = 0
        i += 1
    pn += 1 

for n in n_list:
    print sum(pn_candidates[:n])
### BUGGY CODE ###

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


if n % 2 == 0:
    for i in range(n):
        if i % 2 != 0:  # 偶数なら前
            b.insert(0, a[i])
        else:
            b.append(a[i])
else:
    for j in range(n):
        if j % 2 == 0:  # 偶数なら後ろ
            b.insert(0, a[j])
        else:
            b.append(a[j])

for j in b:
    print("{}".format(j), end=" ")

### FIXED CODE ###

from collections import deque

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


if n % 2 == 0:
    for i in range(n):
        if i % 2 != 0:  # 偶数なら前
            b.appendleft(a[i])
        else:
            b.append(a[i])
else:
    for j in range(n):
        if j % 2 == 0:  # 偶数なら後ろ
            b.appendleft(a[j])
        else:
            b.append(a[j])

print(*b)
### BUGGY CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re



def main_sum():
    N,M,K=map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    A_len = len(A)
    B_len = len(B)

    Asum = [0] * (A_len + 1)
    Bsum = [0] * (B_len + 1)

    maxA = 0
    maxB = 0

    add = 0
    for i in range(1,A_len+1):
        add += A[i-1]
        Asum[i] = add
        if add <= K:
            maxA = i + 1

    add = 0
    for i in range(1,B_len+1):
        add += B[i-1]
        Bsum[i] = add
        if add <= K:
            maxB = i + 1

    ans = 0
    prevmax = 0
    for i in reversed(range(maxA)):
        for j in range(prevmax,maxB):
            if Asum[i] + Bsum[j] <= K:
                if ans < i + j:
                    ans = i + j
                    prevmax = j
            else:
                break

    print(ans)

main_sum()


### FIXED CODE ###

import itertools
import functools
import math
from collections import Counter
from itertools import combinations
import re



def main_sum():
    N,M,K=map(int,input().split())
    A = list(map(int,input().split()))
    B = list(map(int,input().split()))

    A_len = len(A)
    B_len = len(B)

    Asum = [0] * (A_len + 1)
    Bsum = [0] * (B_len + 1)

    maxA = len(A) + 1
    maxB = len(B) + 1

    add = 0
    for i in range(1,A_len+1):
        Asum[i] = A[i-1] + Asum[i-1]

    add = 0
    for i in range(1,B_len+1):
        Bsum[i] = B[i-1] + Bsum[i-1]

    ans = 0
    prev = 0
    for i in reversed(range(maxA)):
        for j in range(prev,maxB):
            if Asum[i] + Bsum[j] <= K:
                prev = j
                if ans < i + j:
                    ans = i + j
                if j == (maxB - 1):
                    print(ans)
                    exit()
            else:
                break

    print(ans)




main_sum()
### BUGGY CODE ###

N = int(input())

nlist=[""]*N

for i in range(N):
    t=str(input())
    t = ''.join(sorted(t))
    nlist[i] = t

cnt=1
sum=0
for i in range(N):
    cnt=1
    cnt=nlist.count(nlist[i])
    if(cnt!=1):
        sum+=cnt-1

print(int(sum/2))


### FIXED CODE ###

import math
N = int(input())

nlist=[""]*N
d={}
for i in range(N):
    t=str(input())
    t=''.join(sorted(t))
    if d.get(t,None)==None:
        d[t]=1
    else:
        d[t]+=1 
ans=0

#print(d.keys(),d.values())
for i in d.values():
    ans += i*(i-1)/2
print(int(ans))