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

s=input()
t=input()
res=0
if len(set(t)-set(s)) > 0:
    res=-1
else:
    dic={}
    set_t=set(t)
    for e_t in t:
        dic[e_t]=[]
    for i in range(len(s)):
        if s[i] in set_t:
            dic[s[i]].append(i+1)
    cur = 0
    for i in range(len(t)):
        nxt=cur
        for e in dic[t[i]]:
            if e > cur:
                nxt=e
                break
        if nxt == cur:
            nxt = dic[t[i]][0]
            res+=len(s)
        cur=nxt
    res+=cur
print(res)

### FIXED CODE ###

s=input()
t=input()
import bisect
res=0
if len(set(t)-set(s)) > 0:
    res=-1
else:
    pos={}
    set_t=set(t)
    for e_t in t:
        pos[e_t]=[]
    for i in range(len(s)):
        if s[i] in set_t:
            pos[s[i]].append(i+1)
    cur = 0
    nxt=0
    for e_t in t:
        nxt=bisect.bisect_left(pos[e_t], cur+1)
        if nxt < len(pos[e_t]):
            cur=pos[e_t][nxt]
        else:
            cur=pos[e_t][0]
            res+=len(s)
    res+=cur
print(res)
### BUGGY CODE ###

N = int(input())
ans = 1
for i in range(N):
    ans = ans * (i + 1)
print(ans % (10**9 + 7))

### FIXED CODE ###

N = int(input())
ans = 1
for i in range(2, N + 1):
    ans = (ans * i) % (10**9 + 7)
print(ans)
### BUGGY CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    num_tmp = [0]*(max(A)+1)

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,max(A)+1,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()

### FIXED CODE ###

def main():
    N = int(input())
    A = list(map(int,input().split()))
    A.sort()
    MAX = A[-1]+1
    num_tmp = [0]*MAX

    for a in A:
        num_tmp[a] += 1
        if num_tmp[a] == 1:
            for i in range(2*a,MAX,a):
                num_tmp[i] = 2

    print(num_tmp.count(1))
    
main()
### BUGGY CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])


### FIXED CODE ###

H, N = map(int, input().split())
AB = []
for _ in range(N):
    a, b = map(int, input().split())
    AB.append((a, b))

INF = 10**20
dp = [0]
for i in range(1, H + 1):
    min_mp_cost = INF
    for damage, mp_cost in AB:
        parent = max(0, i - damage)
        new_cost = dp[parent] + mp_cost
        if new_cost < min_mp_cost:
            min_mp_cost = new_cost
    dp.append(min_mp_cost)
print(dp[-1])
### BUGGY CODE ###

from collections import Counter
import math

def nCr(n, r):
    if n < r:
        return 0
    return math.factorial(n) // (math.factorial(n - r) * math.factorial(r))


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

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

memo = {}
for i in range(n):
    num = A[i]
    if num in memo:
        print(memo[num])
    else:
        t = counter[num]
        ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
        print(ans)
        memo[num] = ans

### FIXED CODE ###

from collections import Counter

mod = (10 ** 9 + 7) ** 5
MAX = 2 * 10 ** 5 + 1 # これは変動するので注意

def com_init(MAX, mod):
    fac = [0] * MAX
    finv = [0] * MAX
    inv = [0] * MAX
    fac[0] = fac[1] = 1
    finv[0] = finv[1] = 1
    inv[1] = 1
    for i in range(2, MAX):
        fac[i] = fac[i - 1] * i % mod
        inv[i] = mod - inv[mod % i] * (mod // i) % mod
        finv[i] = finv[i - 1] * inv[i] % mod
    return fac, finv

fac, finv = com_init(MAX, mod)

def nCr(n, r):
    if n < r:
        return 0
    elif n < 0 or r < 0:
        return 0
    return fac[n] * (finv[r] * finv[n - r] % mod) % mod

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

counter = Counter(A)

mapping = {}
for k, v in counter.items():
    mapping[k] = nCr(v, 2)

all_sum = 0
for v in mapping.values():
    all_sum += v

memo = {}
for i in range(n):
    num = A[i]
    if num in memo:
        print(memo[num])
    else:
        t = counter[num]
        ans = all_sum - nCr(t, 2) + nCr(t - 1, 2)
        print(ans)
        memo[num] = ans
### BUGGY CODE ###

n,m = map(int, input().split())
s = []
g = []
for _ in range(m):
  a,b = map(int, input().split())
  if a == 1: s.append(b)
  elif b == n: g.append(a)
s.sort()
g.sort()
if min(len(s), len(g)) == len(g): x,y = g,s
else: x,y = s,g
  
ok = False
for v in x:
  if v in y: 
    ok = True
    break
print("POSSIBLE" if ok else "IMPOSSIBLE")

### FIXED CODE ###

n,m = map(int, input().split())
ab = [list(map(int, input().split())) for _ in range(m)]
ab.sort()
AB = sorted(ab, reverse=True, key=lambda x:x[1])
s = [0] * n
ans = "IMPOSSIBLE"
for a,b in ab:
    if a == 1: s[b-1] = 1
    else: break
for A, B in AB:
    if B == n:
        if s[A-1] == 1:
            ans = "POSSIBLE"
    else: break
print(ans)
### BUGGY CODE ###

# -*- coding:utf-8 -*-


def solve():
    """ TLE """
    X, Y, Z, K = list(map(int, input().split(" ")))
    A = list(map(int, input().split(" ")))
    B = list(map(int, input().split(" ")))
    C = list(map(int, input().split(" ")))

    ans = []

    for x in range(X):
        for y in range(Y):
            ab = A[x] + B[y]
            for z in range(Z):
                abc = ab + C[z]
                if len(ans) < K-1:
                    ans.append(abc)
                    continue
                elif len(ans) == K-1:
                    ans.append(abc)
                    ans.sort(reverse=True)
                    continue
                
                if abc > ans[-1]:
                    ans[-1] = abc
                    ans.sort(reverse=True)
                    continue

    
    for i in range(0, K):
        print(ans[i])


if __name__ == "__main__":
    solve()


### FIXED CODE ###

# -*- coding:utf-8 -*-

def solve():
    """ TLE """
    X, Y, Z, K = list(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)

    ans = []

    for x in range(X):
        for y in range(Y):
            ab = A[x] + B[y]
            for z in range(Z):
                if (x+1)*(y+1)*(z+1) > K:
                    break

                ans.append(ab + C[z])

    ans.sort(reverse=True)              
    
    for i in range(0, K):
        print(ans[i])


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

import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines
import numpy as np
def main():
    N = int(readline())
    A = np.zeros(N+1, dtype=np.int64)
    A[1:] = np.array(readline().split(), np.int64)
    table = np.zeros(N+1, dtype=np.int64) 
    for i in reversed(range(1, N+1)):
        table[i] = (table[::i].sum()+A[i])%2

    print(table.sum())
    for i in range(N):
        if table[i+1]:
            print(i+1, end=' ')
if __name__ == '__main__':
    main()

### FIXED CODE ###

#python3

def main():
    n = int(input())
    a = [int(i) for i in input().split()]
    b = [0 for _ in range(n)]
    for i in reversed(range(1, n+1)):
        s = 0
        j = i + i
        while j <= n: 
            s ^= b[j-1]
            j += i
        b[i-1] = s^a[i-1]
    
    m = sum(b)
    print(m)
    for i in range(n):
        if b[i] == 1:
            if i == n-1:
                print(i+1)
            else:
                print(i+1, end=' ')
        
main()
### BUGGY CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque
import copy

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

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
q=deque()
q.append(N)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in rev_al[fro]:
		if Visit[to]==0:
			q.append(to)
			
Visit1=Visit

#スタートからBFS
q=deque()
q.append(1)
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
while q:
	fro=q.popleft()
	Visit[fro]=1
	for to in al[fro]:
		if Visit[to]==0:
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") for _ in range(N+1) ]	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		if i==new_N-1 and D[b]!=max( D[b],D[a]+c ):
			print -1
			quit()
		D[b]=max( D[b],D[a]+c )

print max(0,D[N])

### FIXED CODE ###

# -*- coding: utf-8 -*-
import sys
from collections import deque

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

al=[ [] for i in range(N+1) ]		#隣接リスト
rev_al=[ [] for i in range(N+1) ]	#reverse隣接リスト
#辺のリスト
edge=[]

for i in range(M):
	a,b,c=map(int, sys.stdin.readline().split())
	al[a].append(b)
	rev_al[b].append(a)
	edge.append((a,b,c-P))


#ゴールからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(N)
Visit[N]=1
while q:
	fro=q.popleft()
	for to in rev_al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)
			
Visit1=Visit

#スタートからBFS
#訪問した頂点
Visit=[ 0 for _ in range(N+1) ]
q=deque()
q.append(1)
Visit[1]=1
while q:
	fro=q.popleft()
	for to in al[fro]:
		if Visit[to]==0:
			Visit[to]=1
			q.append(to)

Visit2=Visit

#1からもNからも到達可能な頂点の集合
V=[]
for v1,v2 in zip(Visit1,Visit2):
	V.append(v1&v2)

new_N=sum(V)

fedge=[]	#必要な要素だけをフィルターした辺集合
for a,b,c in edge:
	if V[a]==1 and V[b]==1:
		fedge.append((a,b,c))


D=[ float("-inf") ]*(N+1)	#頂点１からの距離 1-indexed
D[1]=0

#ベルマンフォード
for i in range(new_N):
	for a,b,c in fedge:
		if D[a]==float("-inf"): continue
		alt=D[a]+c
		if D[b]<alt:
			D[b]=alt
			if i==new_N-1:
				print -1
				quit()

print max(0,D[N])
### BUGGY CODE ###

import collections
N = int(input())
S = [list(input()) for i in range(N)]
ans = 0
for i in range(N-1):
    Si = collections.Counter(S[i]).most_common()
    Si.sort(key=lambda x: x[0])
    for j in range(i+1,N):
        Sj = collections.Counter(S[j]).most_common()
        Sj.sort(key=lambda x: x[0])
        if Si == Sj:
            ans += 1
print(ans)


### FIXED CODE ###

import collections
N = int(input())
S = [list(input()) for i in range(N)]

for i in range(N):
    Si = S[i]
    Si.sort()
    Si2 = ''.join(Si)
    S[i] = Si2

ans = 0
Sc = collections.Counter(S).most_common()
for s in Sc:
    ans += s[1]*(s[1]-1)//2

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

import collections
N, P = map(int, input().split())
S = input()

mods = [0] * (N+1)
for i in range(N):
  mods[i] = int(S[i:]) % P
c = collections.Counter(mods)
c = dict(c)

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c.get(mods[i], 0)

print(ans)

### FIXED CODE ###

N, P = map(int, input().split())
S = input()

mods = [0] * (N+1)
for i in range(N-1, -1, -1):
  mods[i] = (int(S[i])*pow(10, N-i-1, P)+mods[i+1]) % P
c = dict()
for m in mods:
  c[m] = c.get(m, 0)+1

ans = 0
if P == 2 or P == 5:
  for i, s in enumerate(S):
    s = int(s)
    if s % P == 0:
      ans += i+1
else:
  for i in range(N):
    c[mods[i]] -= 1
    ans += c[mods[i]]

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

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = []
B = []

good = []
no_good = []

for i in range(M):
    t = list(map(int, input().split()))
    A.append(t[0])
    B.append(t[1])

for i in range(M):
    if H[A[i]-1] > H[B[i]-1]:
        g = A[i]
        n = B[i]
    elif H[A[i]-1] < H[B[i]-1]:
        g = B[i]
        n = A[i]
    else:
        no_good.append(A[i])
        no_good.append(B[i])
        continue

    if (g not in no_good) and (g not in good):
        good.append(g)
    if n in good:
        good.remove(n)
    no_good.append(n)

used = set(A) | set(B)
good_num = len(good)
unused_num = N - len(used)
result = good_num + unused_num
print(result)


### FIXED CODE ###

N, M = map(int, input().split())
H = list(map(int, input().split()))
A = []
B = []

no_good = []

for i in range(M):
    t = list(map(int, input().split()))
    A.append(t[0])
    B.append(t[1])

for i in range(M):
    if H[A[i]-1] > H[B[i]-1]:
        no_good.append(B[i])
    elif H[A[i]-1] < H[B[i]-1]:
        no_good.append(A[i])
    else:
        no_good.append(A[i])
        no_good.append(B[i])

result = N - len(set(no_good))
print(result)
### BUGGY CODE ###

import sys
N, M, K = map(int, input().split())
sys.setrecursionlimit(N + 1)

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, visited):

    visited.add(v)

    for n in F[v]:
        if n in visited:
            continue
        dfs(n, visited)


for i in range(N):

    C = set()
    dfs(i, C)
    C = C - {i}
    C = C - B[i]
    C = C - F[i]

    print(len(C), end='')
    if i != N - 1:
        print(' ', end='')

print('')


### FIXED CODE ###

import sys
sys.setrecursionlimit(100001)
N, M, K = map(int, input().split())

label = [-1] * N
n_label = [0] * N

F, B = {}, {}
for i in range(N):
    F[i] = set()
    B[i] = set()

for _ in range(M):
    x, y = map(int, input().split())
    F[x - 1].add(y - 1)
    F[y - 1].add(x - 1)

for _ in range(K):
    x, y = map(int, input().split())
    B[x - 1].add(y - 1)
    B[y - 1].add(x - 1)


def dfs(v, lab):
    if label[v] != -1:
        return 0
    label[v] = lab
    n_label[lab] += 1
    for n in F[v]:
        dfs(n, lab)
    return 1


# labeling
count = 0
for i in range(N):
    count += dfs(i, count)
n_label = n_label[:count]

# calc friend candidate
blocked = 0
for b in B[0]:
    if label[b] == label[0]:
        blocked += 1
print(n_label[label[0]] - 1 - len(F[0]) - blocked, end='')
for i in range(1, N):
    print(' ', end='')
    blocked = 0
    for b in B[i]:
        if label[b] == label[i]:
            blocked += 1
    print(n_label[label[i]] - 1 - len(F[i]) - blocked, end='')
print('')
### BUGGY CODE ###


def main():
    
    
    in1 = [int(e) for e in input().split()]
    n = in1[0]
    q = in1[1]

    a = []
    b = []
    for i in range(n-1):
        in1 = [int(e) for e in input().split()]
        a.append(in1[0])
        b.append(in1[1])

    p = []
    x = []
    for i in range(q):
        in1 = [int(e) for e in input().split()]
        p.append(in1[0])
        x.append(in1[1])

    l = [0] * n

    def addval(p,x):
        l[p-1] += x

        for j in range(n-1):
            #print('j',j)
            if(a[j] == p):
                addval(b[j],x)

    for i in range(q):
        addval(p[i],x[i])

    
    for i in range(n):
        print(l[i], end="")
        print(" ", end="")
        




if __name__ == "__main__":
    main()


### FIXED CODE ###

ii = lambda : int(input())
mi = lambda : map(int,input().split())
li = lambda : list(map(int,input().split()))

import sys
sys.setrecursionlimit(40000000)

n,q = mi()
b = [[] for i in range(n)]
ans = [0]*n

# O(2n)
for i in range(n-1):
    a,c = mi()
    b[a-1].append(c-1)
    b[c-1].append(a-1)

# jun = []
# O(2n)
# def chil_pop(l,p):
#     jun.append(l)
#     for i in b[l]:
#         if i == p:
#             continue
#         chil_pop(i,l)
#     b[l] = p

# chil_pop(0,-1)


# O(q)
for i in range(q):
    p,x = mi()
    ans[p-1] += x


count = 0
q = [(0,-1)]
while q:
    c,p = q.pop()
    for i in b[c]:
        if i == p:
            continue
        ans[i] += ans[c]
        q.append((i,c))
    
    

# for i in jun[1:]:
#     ans[i] += ans[b[i]]

# ans_str = ''
# for i in range(n):
#     print(ans[i],end=' ')
#     # ans_str = ans_str + str(ans[i]) + ' '
print(*ans)
### BUGGY CODE ###

n = int(input())

count = 0

for i in range(n):
  check = True
  
  key = int(input())

  for i in range(2,key):
    if key % i == 0:
      check = False
    
  if check:
    count += 1

print(count)


### FIXED CODE ###

def isPrime(n):
    for i in range(2, n):
        if i * i > n:
            return 1
        if n % i == 0:
            return 0
    return 1
 
ans = 0
n = int(input())
for i in range(n):
    x = int(input())
    ans = ans + isPrime(x)
 
print(ans)
### BUGGY CODE ###

import heapq


def main():
    n = input()
    aa = []
    for _ in xrange(n):
        aa.append(input())
    xx = [aa.pop()]
    buf = []
    while aa:
        a = aa.pop()
        if a < xx[0]:
            heapq.heapreplace(xx, a)
        else:
            while xx and a >= xx[0]:
                heapq.heappush(buf, heapq.heappop(xx))
            if xx:
                heapq.heapreplace(xx, a)
                for b in buf:
                    heapq.heappush(xx, b)
                buf = []
            else:
                heapq.heappush(buf, a)
                xx = buf
                buf = []
    print len(xx)


if __name__ == '__main__':
    main()


### FIXED CODE ###

import bisect
 
 
def main():
    n = input()
    aa = []
    xx = [-input()]
    for _ in xrange(n - 1):
        aa.append(-input())
    for a in aa:
        if a >= xx[-1]:
            xx.append(a)
        else:
            i = bisect.bisect_right(xx, a)
            if i == len(xx):
                i -= 1
            xx[i] = a
    print len(xx)
 
 
if __name__ == '__main__':
    main()
### BUGGY CODE ###

s=input()
q=int(input())
queri=[]
rv=0

if rv==1: s=s[::-1]
forward=""
back=""
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward+=queri[2]
        else: back+=queri[2]

    else: rv=(rv+1)%2

ans=forward[::-1]+s+back
print(ans if rv==0 else ans[::-1])


### FIXED CODE ###

s=input()
q=int(input())
queri=[]
rv=0
forward=[]
back=[]
for i in range(q):
    queri=list(map(lambda x:x,input().split()))
    if queri[0]=="2":
        rvt=(rv+int(queri[1]))%2
        if rvt==1: forward.append(queri[2])
        else: back.append(queri[2])

    else: rv=(rv+1)%2

if rv==0:
    for i in range(len(forward)-1,-1,-1):
        print(forward[i],end="")
    print(s,end="")
    for i in range(len(back)):
        print(back[i],end="")
        
if rv==1:
    for i in range(len(back)-1,-1,-1):
        print(back[i],end="")
    print(s[::-1],end="")
    for i in range(len(forward)):
        print(forward[i],end="")
### BUGGY CODE ###

# -*- coding: utf-8 -*-

N, Y = map(int, input().split())
result_10000, result_5000, result_1000 = -1, -1, -1
found = False

# 効率を考えて、1万円札 → 5000円札 → 1000円札の順で求める
# 1万円札の数をY//10000から一つずつ減らして調べていく
for num_10000 in reversed(range(0, Y//10000 + 1)):
    y_10000 = Y - 10000 * num_10000
    n_10000 = N - num_10000
    if y_10000 == 0 and n_10000 == 0:
        result_10000, result_5000, result_1000 = num_10000, 0, 0
        found = True
        break
    else:
        for num_5000 in reversed(range(0, y_10000//5000 + 1)):
            y_5000 = y_10000 - 5000 * num_5000
            n_5000 = n_10000 - num_5000
            if y_5000 == 0 and n_5000 == 0 and num_10000 + num_5000 == N:
                result_10000, result_5000, result_1000 = num_10000, num_5000, 0
                found = True
                break
            else:
                for num_1000 in reversed(range(0, y_5000//1000 + 1)):
                    y_1000 = y_5000 - 1000 * num_1000
                    n_1000 = n_5000 - num_1000
                    if y_1000 == 0 and n_1000 == 0 and num_10000 + num_5000 + num_1000 == N:
                        result_10000, result_5000, result_1000 = num_10000, num_5000, num_1000
                        found = True
                        break
            if found:
                break
    if found:
        break
    
print(result_10000, result_5000, result_1000)



### FIXED CODE ###

# -*- coding: utf-8 -*-

N, Y = map(int, input().split())
result_10000, result_5000, result_1000 = -1, -1, -1
found = False

# 効率を考えて、1万円札 → 5000円札 → 1000円札の順で求める
# 1万円札の数をY//10000から一つずつ減らして調べていく
for num_10000 in reversed(range(0, Y//10000 + 1)):
    y_10000 = Y - 10000 * num_10000
    n_10000 = N - num_10000
    if y_10000 == 0 and n_10000 == 0:
        result_10000, result_5000, result_1000 = num_10000, 0, 0
        found = True
        break
    else:
        for num_5000 in reversed(range(0, y_10000//5000 + 1)):
            y_5000 = y_10000 - 5000 * num_5000
            n_5000 = n_10000 - num_5000
            if y_5000 < 0 or n_5000 < 0:
                break
            if y_5000 == 0 and n_5000 == 0 and num_10000 + num_5000 == N:
                result_10000, result_5000, result_1000 = num_10000, num_5000, 0
                found = True
                break
            else:
                # 10000円札と5000円札の枚数が決まれば必然的に1000円札の枚数は決まる
                num_1000 = y_5000 // 1000
                y_1000 = y_5000 - 1000 * num_1000
                n_1000 = n_5000 - num_1000
                if y_1000 == 0 and n_1000 == 0 and num_10000 + num_5000 + num_1000 == N:
                    result_10000, result_5000, result_1000 = num_10000, num_5000, num_1000
                    found = True
                    break
            if found:
                break
        if found:
            break
    
print(result_10000, result_5000, result_1000)
### BUGGY CODE ###

from heapq import heapify, heappop, heapreplace

n = int(input())
aaa = list(map(int, input().split()))
# print(*(f'{a:08b}' for a in aaa))

all_x = 0
for a in aaa:
    all_x ^= a
mask = ~all_x
bbb = [-(a & mask) for a in aaa]
heapify(bbb)

red = set()
while bbb and bbb[0] < 0:
    a = -heappop(bbb)
    l = a.bit_length()
    b = 1 << (l - 1)
    while bbb and (-bbb[0]).bit_length() == l:
        heapreplace(bbb, -(a ^ (-bbb[0])))
    red = {s ^ a if s & b else s for s in red}
    red.add(a)

ans = 0
for a in red:
    ans ^= a

print(2 * ans + all_x)


### FIXED CODE ###

import numpy as np

n = int(input())
aaa = np.fromiter(map(int, input().split()), np.int64)

all_x = np.bitwise_xor.reduce(aaa)
mask = ~all_x
bbb = aaa & mask

ans = 0
while any(bbb):
    a = bbb.max()
    b = 1 << (int(a).bit_length() - 1)
    bbb[bbb & b > 0] ^= a
    if ans & b == 0:
        ans ^= a

print(2 * ans + all_x)
### BUGGY CODE ###

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

e = []

for i in range(n):
  a = p[i] * (p[i] + 1) / 2
  e.append(a/p[i])

ans = 0  
for i in range(k-1,n):
  s = sum(e[i-(k-1):i+1])
  if ans < s:
    ans = s

print(ans)

### FIXED CODE ###

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

e = []

for i in range(n):
  a = p[i] * (p[i] + 1) / 2
  e.append(a/p[i])

ans = sum(e[0:k])
s = ans

for i in range(k,n):
  aaa = s + e[i] - e[i-k]
  if ans < aaa:
    ans = aaa
  s = aaa
print(ans)
### BUGGY CODE ###

H,W,N=map(int,raw_input().split())
XY=[]
for i in range(N):
    XY.append(map(int,raw_input().split()))

XY.sort()

conditions=[i-1 for i in range(H+1)]
for xy in XY:
    if xy[1]==conditions[xy[0]]+1:
        conditions=[conditions[i] if i<=xy[0] \
                   else conditions[i]-1 for i in range(H+1)]

for xy in XY:
    if conditions[xy[0]]>=xy[1]:
        print xy[0]-1
        break
else:
    print H

### FIXED CODE ###

H,W,N=map(int,raw_input().split())
XY=[]
for i in range(N):
    XY.append(map(int,raw_input().split()))

XY.sort()

conditions=[2,1]
for xy in XY:
    if xy[0]>conditions[0]:
        conditions=[xy[0],conditions[1]+xy[0]-conditions[0]]
    if conditions[1]>=xy[1]:
        print xy[0]-1
        break
    if xy[1]==conditions[1]+1:
        conditions=[conditions[0],conditions[1]-1]
else:
    print H