There are N infants registered in AtCoder, numbered 1 to N, and 2\times 10^5 kindergartens, numbered 1 to 2\times 10^5.
Infant i has a rating of A_i and initially belongs to Kindergarten B_i.
From now on, Q transfers will happen.
After the j-th transfer, Infant C_j will belong to Kindergarten D_j.
Here, we define the evenness as follows. For each kindergarten with one or more infants registered in AtCoder, let us find the highest rating of an infant in the kindergarten. The evenness is then defined as the lowest among those ratings.
For each of the Q transfers, find the evenness just after the transfer.

-----Constraints-----
 - 1 \leq N,Q \leq 2 \times 10^5
 - 1 \leq A_i \leq 10^9
 - 1 \leq C_j \leq N
 - 1 \leq B_i,D_j \leq 2 \times 10^5
 - All values in input are integers.
 - In the j-th transfer, Infant C_j changes the kindergarten it belongs to.

-----Input-----
Input is given from Standard Input in the following format:
N Q
A_1 B_1
A_2 B_2
:
A_N B_N
C_1 D_1
C_2 D_2
:
C_Q D_Q

-----Output-----
Print Q lines.
The j-th line should contain the evenness just after the j-th transfer.

-----Sample Input-----
6 3
8 1
6 2
9 3
1 1
2 2
1 3
4 3
2 1
1 2

-----Sample Output-----
6
2
6

Initially, Infant 1, 4 belongs to Kindergarten 1, Infant 2, 5 belongs to Kindergarten 2, and Infant 3, 6 belongs to Kindergarten 3.
After the 1-st transfer that makes Infant 4 belong to Kindergarten 3, Infant 1 belongs to Kindergarten 1, Infant 2, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 6, 9, respectively. The lowest among them is 6, so the 1-st line in the output should contain 6.
After the 2-nd transfer that makes Infant 2 belong to Kindergarten 1, Infant 1, 2 belong to Kindergarten 1, Infant 5 belongs to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 8, 2, 9, respectively. The lowest among them is 2, so the 2-nd line in the output should contain 2.
After the 3-rd transfer that makes Infant 1 belong to Kindergarten 2, Infant 2 belongs to Kindergarten 1, Infant 1, 5 belong to Kindergarten 2, and Infant 3, 4, 6 belong to Kindergarten 3. The highest ratings of an infant in Kindergarten 1, 2, 3 are 6, 8, 9, respectively. The lowest among them is 6, so the 3-rd line in the output should contain 6.

Difficulty: interview

Starter code:

Solutions:
from heapq import heappop, heappush
n , q = map(int,input().split())
enzi = [[0,0] for i in range(n)]
youti = [[] for i in range(2*10**5)]
saikyo = [0 for i in range(2*10**5)]
ans = []

for i in range(n):
    a , b = map(int,input().split())
    enzi[i] = [a,b-1]
    heappush(youti[b-1],(-a,i))

for i in range(2*10**5):
    if youti[i]:
        now = heappop(youti[i])
        saikyo[i] = -now[0]
        heappush(ans,(-now[0],i))
        heappush(youti[i],now)

for _ in range(q):
    c , d = map(lambda x:int(x)-1,input().split())
    heappush(youti[d],(-enzi[c][0],c))
    moto = enzi[c][1]
    enzi[c][1] = d
    
    while True:
        if youti[moto]:
            now = heappop(youti[moto])
            if enzi[now[1]][1] == moto:
                if saikyo[moto] != -now[0]:
                    saikyo[moto] = -now[0]
                    heappush(ans,(-now[0],moto))
                heappush(youti[moto],now)
                break
        else:
            saikyo[moto] = 0
            break
    while True:
        now = heappop(youti[d])
        if enzi[now[1]][1] == d:
            if saikyo[d] != -now[0]:
                saikyo[d] = -now[0]
                heappush(ans,(-now[0],d))
            heappush(youti[d],now)
            break
    
    while True:
        now = heappop(ans)
        if saikyo[now[1]] == now[0]:
            print(now[0])
            heappush(ans,now)
            break

from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t,_ in x:t and f(l,-t[0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=y and y[0]or 0;f(y,-a),f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y[0]<t:f(l,a);t and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

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

sys.setrecursionlimit(10**7)
inf = 10**20
eps = 1.0 / 10**10
mod = 10**9+7
dd = [(-1,0),(0,1),(1,0),(0,-1)]
ddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]

def LI(): return list(map(int, sys.stdin.readline().split()))
def LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]
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 pf(s): return print(s, flush=True)
def pe(s): return print(str(s), file=sys.stderr)
def JA(a, sep): return sep.join(map(str, a))
def JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)


class DQ():
    def __init__(self):
        self.q = []
        self.d = []

    def add(self, x):
        heapq.heappush(self.q, x)

    def rem(self, x):
        heapq.heappush(self.d, x)

    def top(self):
        while self.d and self.q[0] == self.d[0]:
            heapq.heappop(self.q)
            heapq.heappop(self.d)

        if self.q:
            return self.q[0]

        return None

def main():
    n,q = LI()
    ab = [LI() for _ in range(n)]
    cd = [LI() for _ in range(q)]

    m = 2 * 10**5 + 1
    r = DQ()
    t = [DQ() for _ in range(m)]
    ca = [-1] * (n+1)
    e = [-1] * (n+1)

    for c in range(1, n+1):
        a,b = ab[c-1]
        ca[c] = a
        e[c] = b
        tp = t[b].top()
        if tp:
            s = -tp
            if s < a:
                r.rem(s)
                r.add(a)
            t[b].add(-a)
        else:
            r.add(a)
            t[b].add(-a)

        # print("ab",a,b,r.q,r.d)

    rr = []
    for c, d in cd:
        a = ca[c]
        b = e[c]
        e[c] = d
        s = -t[b].top()
        t[b].rem(-a)
        if s == a:
            r.rem(a)
            u = t[b].top()
            if not u is None:
                r.add(-u)

        tp = t[d].top()
        if tp:
            s = -tp
            if s < a:
                r.rem(s)
                r.add(a)
            t[d].add(-a)
        else:
            r.add(a)
            t[d].add(-a)

        # print("cd", c,d,r.q,r.d)
        rr.append(r.top())

    return JA(rr, "\n")


print(main())




import sys
readline = sys.stdin.readline

import heapq as hq

N,Q = list(map(int,readline().split()))
NN = 2 * (10 ** 5)

# (レート, 所属園)
infants = [None] * (N + 1)
# (最強園児, 園児番号)
kinda = [[] for i in range(NN + 1)]
for i in range(N):
  a,b = list(map(int,readline().split()))
  infants[i + 1] = [a,b]
  hq.heappush(kinda[b], (-a, i + 1))

# (最弱園児, 園の番号)
all_kinda = []
for i in range(len(kinda)):
  if kinda[i]:
    hq.heappush(all_kinda, (-kinda[i][0][0], i))
  
def get_max_rate(x): # 園xの最強レートを取り出す
  q = kinda[x]
  while q:
    rate, ind = hq.heappop(q)
    if infants[ind][1] != x:
      continue
    hq.heappush(q, (rate, ind))
    return -rate
  return -1
  
for i in range(Q):
  ind,next_kinda_id = list(map(int,readline().split()))
  rate,old_kinda_id = infants[ind]
  infants[ind][1] = next_kinda_id
  hq.heappush(kinda[next_kinda_id],(-rate, ind))
  
  old_kinda_max_rate = get_max_rate(old_kinda_id)
  if old_kinda_max_rate != -1:
    hq.heappush(all_kinda, (old_kinda_max_rate, old_kinda_id))
    
  next_kinda_max_rate = get_max_rate(next_kinda_id)
  if next_kinda_max_rate != -1:
    hq.heappush(all_kinda, (next_kinda_max_rate, next_kinda_id))
    
  while all_kinda:
    rate, kinda_id = hq.heappop(all_kinda)
    cur_max_rate = get_max_rate(kinda_id)
    if rate != cur_max_rate:
      continue
    hq.heappush(all_kinda, (rate, kinda_id))
    print(rate)
    break


import sys
import heapq
from collections import defaultdict

sys.setrecursionlimit(10 ** 6)
INF = float("inf")
MOD = 10 ** 9 + 7


def input():
    return sys.stdin.readline().strip()


def main():
    MAX = 10 ** 5 * 2
    N, Q = list(map(int, input().split()))
    heap = [[] for _ in range(MAX)]
    for i in range(MAX):
        heapq.heapify(heap[i])

    rates = [0] * N
    places = [0] * N
    for i in range(N):
        a, b = list(map(int, input().split()))
        places[i] = b - 1
        rates[i] = a
        heapq.heappush(heap[b - 1], (-a, i))

    heap_all = []
    heapq.heapify(heap_all)
    m = INF
    p = None
    for i in range(MAX):
        if not heap[i]:
            continue

        m = -heap[i][0][0]
        p = i
        child = heap[i][0][1]
        heapq.heappush(heap_all, (m, p, child))

    ans = []
    for _ in range(Q):
        c, d = list(map(int, input().split()))
        child = c - 1
        cur = d - 1
        prev = places[child]
        rate = rates[child]

        # 新しいクラスへの追加
        heapq.heappush(heap[cur], (-rate, child))
        places[child] = cur

        # 最小値の検索
        while heap[prev]:
            v, i = heap[prev][0]
            if places[i] == prev:
                heapq.heappush(heap_all, (-v, prev, i))
                break
            else:
                heapq.heappop(heap[prev])

        while heap[cur]:
            v, i = heap[cur][0]
            if places[i] == cur:
                heapq.heappush(heap_all, (-v, cur, i))
                break
            else:
                heapq.heappop(heap[cur])

        while True:
            r, p, i = heap_all[0]
            if p == places[i] and heap[p][0][0] == -r:
                ans.append(r)
                break
            else:
                heapq.heappop(heap_all)

    for a in ans:
        print(a)


def __starting_point():
    main()

__starting_point()

N,Q=map(int,input().split())
where=[]
rating=[]
from heapq import heapify,heappop,heappush
garten=[[] for _ in range(2*10**5)] #大きい順(マイナス掛け)
saikyo=[] #小さい順
for i in range(N):
    A,B=map(int,input().split())
    where.append(B-1)
    rating.append(A)
    heappush(garten[B-1],(-A,i)) #(レート、園児)

for i in range(2*10**5):
    if not garten[i]:
        continue
    rate,num=garten[i][0]
    heappush(saikyo,(-rate,i)) #(レート、幼稚園)

for _ in range(Q):
    C,D=map(int,input().split())
    C,D=C-1,D-1 #幼児、転園先
    
    moto=where[C]
    where[C]=D
    heappush(garten[D],(-rating[C],C)) #転園先に追加
    if garten[D][0][1]==C:
        heappush(saikyo,(rating[C],D))


    while garten[moto]: #転園元の整理
        a,b=garten[moto][0]
        if where[b]==moto:
            break
        heappop(garten[moto])
    heappush(saikyo,(-a,moto))
    #print(garten[:5])
    while True: #最強リストの整理
        #print(saikyo)
        a,b=saikyo[0]
        if not garten[b]:
            heappop(saikyo)
            continue
        if garten[b][0][0]==-a:
            break
        heappop(saikyo)
    print(a)

import sys
import heapq as hq
readline = sys.stdin.readline

ns = lambda: readline().rstrip()
ni = lambda: int(readline().rstrip())
nm = lambda: list(map(int, readline().split()))
nl = lambda: list(map(int, readline().split()))

n, q = nm()
m = 2*10**5 + 5
cur = [-1]*n
rate = [0]*n
sec = [list() for _ in range(m)]
for i in range(n):
    a, b = nm()
    rate[i] = a
    cur[i] = b
    hq.heappush(sec[b], (-a, i))
top = list()
for i in range(m):
    if sec[i]:
        hq.heappush(top, (-sec[i][0][0], sec[i][0][1], i))
for _ in range(q):
    c, d = nm()
    c -= 1
    bef = cur[c]
    cur[c] = d
    hq.heappush(sec[d], (-rate[c], c))
    if sec[d][0][1] == c:
        hq.heappush(top, (rate[c], c, d))
    fl = 0
    while sec[bef] and cur[sec[bef][0][1]] != bef:
        hq.heappop(sec[bef])
        fl = 1
    if fl and sec[bef]:
        hq.heappush(top, (-sec[bef][0][0], sec[bef][0][1], bef))
    while not sec[top[0][2]] or sec[top[0][2]][0][1] != top[0][1]:
        hq.heappop(top)
    print((top[0][0]))


#import time 
#it = time.time()
from heapq import heapify,heappush,heappop
import sys
input = sys.stdin.readline

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

S = []
PQs = [[] for _ in range(200000)]
T = [0]*200000 #幼稚園ごとの最終更新
M = []
for n in range(N):
  a, b = list(map(int,input().split()))
  S.append([a,b-1])#レート、所属
  PQs[b-1]+=[(-a,n)]#-レート、人

for b in range(200000):
  if len(PQs[b])>0:
    heapify(PQs[b])
    M.append((-PQs[b][0][0],b,0))#レート、人、所属、更新時
heapify(M)


ans = []
for q in range(1,Q+1):#時刻。1からスタート
  c, d = list(map(int,input().split()))
  d = d-1
  d_prv = S[c-1][1]
  S[c-1][1] = d #情報の更新
  
  #転園先の幼稚園について
  heappush(PQs[d],(-S[c-1][0],c-1))#-レート、人
  while d != S[PQs[d][0][1]][1]:#所属が整合していない時（古く間違った情報である時）
    heappop(PQs[d])
  if -PQs[d][0][0] == S[c-1][0]:
  	heappush(M,(-PQs[d][0][0],d,q))
  	T[d] = q #最終更新時をアップデート
  
  #転園元の幼稚園について
  if len(PQs[d_prv])>0:
    while d_prv != S[PQs[d_prv][0][1]][1]:#所属が整合していない時（古く間違った情報である時）
      heappop(PQs[d_prv])
      if len(PQs[d_prv]) == 0:
        break
        
    if len(PQs[d_prv]) > 0 and -PQs[d_prv][0][0] < S[c-1][0]:  
      heappush(M,(-PQs[d_prv][0][0],d_prv,q))
      
    if len(PQs[d_prv]) == 0 or -PQs[d_prv][0][0] < S[c-1][0]:
      T[d_prv] = q #最終更新時をアップデート
 	
  #最強園児の集いを処理
  while M[0][2] != T[M[0][1]]:#更新時が整合していない時（古く間違った情報である時）
    heappop(M)
  
  ans.append(M[0][0])
  

  
#結果の出力
print(('\n'.join(map(str, ans))))



import heapq

#getIntList = list(map(int, input.split()))
#getFloatList = list(map(float, input.split()))

MAXEN = 2*(10**5) + 5
N, Q = list(map(int, input().split()))
kid = [0]
en = [0]
entop = [[] for _ in range(MAXEN)]
alltop = []
addAllList = []
rmvAllList = []
for i in range(N):
    a, b = list(map(int, input().split()))
    kid.append(a)
    en.append(b)
    #push to heap
    heapq.heappush(entop[b], -a)

for e in range(MAXEN):
    if entop[e]:
        vv = entop[e][0]
        heapq.heappush(alltop, -vv)
addlist = [[] for _ in range(MAXEN)]
rmvlist = [[] for _ in range(MAXEN)]


def updateEn(enID):
    # is it larger than top of enID?
    while len(addlist[enID]) > 0:
        add_top = addlist[enID][0]
        needAddNow = True
        if len(rmvlist[enID]) > 0:
            needAddNow = True
        elif entop[enID]:
            entop_old = entop[enID][0]
            needAddNow = add_top < entop_old

        if needAddNow:
            heapq.heappush(entop[enID], add_top)
            heapq.heappop(addlist[enID])
        else:
            break

    # is it top of enID?
    while (len(entop[enID]) > 0) and (len(rmvlist[enID]) > 0):
        rmv_top = rmvlist[enID][0]
        entop_old = entop[enID][0]
        if rmv_top == entop_old:
            heapq.heappop(entop[enID])
            heapq.heappop(rmvlist[enID])
        else:
            break

#query
for q in range(Q):
    c, d = list(map(int, input().split()))
    old_en = en[c]
    new_en = d
    en[c] = new_en

    #add to rmvlist
    heapq.heappush(rmvlist[old_en], -kid[c])
    #add to addlist
    heapq.heappush(addlist[new_en], -kid[c])

    if len(entop[old_en]) > 0:
        entop_old0 = entop[old_en][0]
    else: entop_old0 = 0
    if len(entop[new_en]) > 0:
        entop_new0 = entop[new_en][0]
    else: entop_new0 = 0

    updateEn(new_en)
    updateEn(old_en)
    # #is it larger than top of new_en?
    # while (len(entop[new_en]) > 0) and (len(addlist[new_en]) > 0):
    #     add_top = addlist[new_en][0]
    #     entop_old = entop[new_en][0]
    #     if add_top < entop_old:
    #         heapq.heappush(entop[new_en], add_top)
    #         heapq.heappop(addlist[new_en])
    #     else:
    #         break
    #
    # #is it top of old_en?
    # while (len(entop[old_en]) > 0) and (len(rmvlist[old_en]) > 0):
    #     rmv_top = rmvlist[old_en][0]
    #     entop_old = entop[old_en][0]
    #     if rmv_top == entop_old:
    #         heapq.heappop(entop[old_en])
    #         heapq.heappop(rmvlist[old_en])
    #     else:
    #         break

    if len(entop[old_en]) > 0:
        entop_old1 = entop[old_en][0]
    else: entop_old1 = 0
    if entop_old0 != entop_old1:#changed?
        if entop_old0 != 0: heapq.heappush(rmvAllList, -entop_old0)
        if entop_old1 != 0: heapq.heappush(addAllList, -entop_old1)

    if len(entop[new_en]) > 0:
        entop_new1 = entop[new_en][0]
    else: entop_new1 = 0
    if entop_new0 != entop_new1:#changed?
        if entop_new0 != 0: heapq.heappush(rmvAllList, -entop_new0)
        if entop_new1 != 0: heapq.heappush(addAllList, -entop_new1)

    #is it smaller than top of alltop?
    while len(addAllList) > 0:
        add_top = addAllList[0]
        if (len(alltop) == 0) or (add_top < alltop[0]) or (len(rmvAllList) > 0):
            heapq.heappush(alltop, add_top)
            heapq.heappop(addAllList)
        else:
            break

    #is it top of alltop?
    while len(rmvAllList) > 0:
        rmvTopV = rmvAllList[0]
        if rmvTopV == alltop[0]:
            heapq.heappop(alltop)
            heapq.heappop(rmvAllList)
        else:
            break

    print((alltop[0]))



import sys
import numpy as np
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 

  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res

  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  
  @staticmethod
  def gcd(a, b): return gcd(b, a%b) if b else abs(a)

  @staticmethod
  def lcm(a, b): return abs(a // gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  
  @staticmethod
  def base_convert(n, b): # return string
    if not n: return '0'
    res = ''
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res += str(r)
    return res[::-1]


class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]


class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose


def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a


class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)

  def B(): pass
  def C(): pass 
  def D(): pass 


class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))

  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)

  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))

  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))


class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)

  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')

  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)

  def D(): pass 


class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)

  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])

  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))

  def D(): pass 


class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)

  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))

  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')

  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')


class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')

  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
    
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
      
  def D():
    n, *c = map(int, sys.stdin.read().split())
    inf = float('inf')
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))


class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)

  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')

  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  
  def D(): pass 


class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)

  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)

  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
    
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s))
      
  def D(): pass 


class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)

  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)

  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)

  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())

  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')

  def D(): pass 


class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break

  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
      
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])

  def D():
    n, *a = map(int, sys.stdin.read().split())
    cand = set(a)
    cnt = 0
    for x, c in sorted(Counter(a).items()):
      cnt += c == 1 and x in cand
      cand -= set(range(x*2, 10**6+1, x))
    print(cnt)


  def E():
    n, q = map(int, sys.stdin.readline().split())
    queue = [] 
    num_kindergarten = 2*10**5
    queue_kindergarten = [[] for _ in range(num_kindergarten)]
    highest_kindergarten = [None] * num_kindergarten
    where = [None] * n
    rate = [None] * n

    def entry(i, k):
      where[i] = k
      while queue_kindergarten[k]:
        r, j = heappop(queue_kindergarten[k])
        if where[j] != k or j == i: continue 
        if rate[i] >= -r:
          highest_kindergarten[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(queue_kindergarten[k], (r, j))
        break
      else:
        highest_kindergarten[k] = rate[i]
        heappush(queue, (rate[i], k, i))
      heappush(queue_kindergarten[k], (-rate[i], i))

    def transfer(i, k):
      now = where[i]
      # while queue_kindergarten[now]:
      #   r, j = heappop(queue_kindergarten[now])
      #   if where[j] == now: break
      # if j != i:
      #   heappush(queue_kindergarten[now], (r, j))
      # else:
      while queue_kindergarten[now]:
        r, j = heappop(queue_kindergarten[now])
        if where[j] != now or j == i: continue
        if highest_kindergarten[now] != -r:
          highest_kindergarten[now] = -r
          heappush(queue, (-r, now, j))
        heappush(queue_kindergarten[now], (r, j))
        break
      else:
        highest_kindergarten[now] = None
      entry(i, k)

    def inquire():
      while True:
        r, k, i = heappop(queue)
        if where[i] != k or r != highest_kindergarten[k]: continue 
        heappush(queue, (r, k, i))
        return r

    for i in range(n):
      a, b = map(int, sys.stdin.readline().split())
      rate[i] = a 
      entry(i, b-1)
    for _ in range(q):
      c, d = map(int, sys.stdin.readline().split())
      transfer(c-1, d-1)
      print(inquire())
    

  def F(): pass 

def __starting_point():
  ABC170.E()
__starting_point()

def solve():
    from heapq import heappop, heappush
    from collections import defaultdict
    n, q = list(map(int, input().split()))
    rates = [0] * (n + 1)
    belong = [0] * (n + 1)
    en = [[] for _ in range(2 * (10 ** 5) + 1)]
    ob = [defaultdict(int) for _ in range(2 * (10 ** 5) + 1)]
    res = []
    res_gone = defaultdict(int)
    ans = []
    for i in range(1, n + 1):
        a, b = list(map(int, input().split()))
        rates[i] = a
        belong[i] = b
        heappush(en[b], -a)
    for e in en:
        if e:
            x = -heappop(e)
            heappush(res, x)
            heappush(e, -x)
    for i in range(q):
        c, d = list(map(int, input().split()))
        tmp = belong[c]
        obr = rates[c]
        ob[tmp][obr] += 1

        ox_s = -heappop(en[tmp])
        res_gone[ox_s] += 1
        heappush(en[tmp], -ox_s)

        if en[d]:
            ox_m = -heappop(en[d])
            res_gone[ox_m] += 1
            heappush(en[d], -ox_m)

        belong[c] = d
        heappush(en[d], -rates[c])

        nx_s = -heappop(en[tmp])
        while ob[tmp][nx_s] != 0:
            ob[tmp][nx_s] -= 1
            nx_s = -heappop(en[tmp]) if en[tmp] else 0
        if nx_s != 0:
            heappush(res, nx_s)
            heappush(en[tmp], -nx_s)

        nx_m = -heappop(en[d])
        heappush(res, nx_m)
        heappush(en[d], -nx_m)

        fair = heappop(res)
        while res_gone[fair] != 0:
            res_gone[fair] -= 1
            fair = heappop(res)
        ans.append(fair)
        heappush(res, fair)
    print(("\n".join(map(str, ans))))


solve()


import heapq


class HeapDict:
    def __init__(self):
        # heapqとdictを用意
        self.h = []
        self.d = dict()

    def insert(self, x):
        heapq.heappush(self.h, x)
        if x not in self.d:
            self.d[x] = 1
        else:
            self.d[x] += 1

    def erase(self, x):
        if x not in self.d or self.d[x] == 0:
            print((x, "is not in HeapDict"))
            return
        else:
            self.d[x] -= 1

        while len(self.h) != 0:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self, x):
        if x in self.d and self.d[x] != 0:
            return True
        else:
            False

    def get_min(self):
        return self.h[0]

    def size(self):
        return len(self.h)


def main():
    N, Q = list(map(int, input().split()))
    A = []  # レート
    B = []  # 所属幼稚園
    con = 2 * 10 ** 5
    INF = 10 ** 18
    youchi = [HeapDict() for _ in range(con)]  # 各幼稚園に対するHeapDict
    max_values = HeapDict()  # 各幼稚園の最大値のHeapDict
    for i in range(N):
        a, b = list(map(int, input().split()))
        b -= 1
        A.append(a)
        B.append(b)
        youchi[b].insert(-a)

    for i in range(con):  # 各幼稚園の最大値をまとめる
        if youchi[i].size() != 0:
            max_values.insert(-youchi[i].get_min())
        else:
            max_values.insert(INF)

    for i in range(Q):
        c, d = list(map(int, input().split()))
        c -= 1
        d -= 1
        rate = A[c]
        youchi_now = B[c]
        youchi_next = d

        # 最強園児のレートの集合から、転園する園児の元の幼稚園の元の最強園児のレートを、削除する
        max_values.erase(-youchi[youchi_now].get_min())

        # 転園する園児の元の幼稚園のレートの集合から、転園する園児のレートを、削除する
        youchi[youchi_now].erase(-rate)

        # 最強園児のレートの集合に、転園する園児の元の幼稚園の新しい最強園児のレートを、挿入する(園児が一人もいない場合何もしない)
        if youchi[youchi_now].size() != 0:
            max_values.insert(-youchi[youchi_now].get_min())

        # 最強園児のレートの集合から、転園する園児の新しい幼稚園の元の最強園児のレートを、削除する(園児が一人もいない場合何もしない)
        if youchi[youchi_next].size() != 0:
            max_values.erase(-youchi[youchi_next].get_min())

        # 転園する園児の新しい幼稚園のレートの集合に、転園する園児のレートを、挿入する
        youchi[youchi_next].insert(-rate)

        # 最強園児のレートの集合に、転園する園児の新しい幼稚園の新しい最強園児のレートを、挿入する
        max_values.insert(-youchi[youchi_next].get_min())

        # 転園する園児の所属する幼稚園の番号を更新する
        B[c] = youchi_next

        print((max_values.get_min()))


def __starting_point():
    main()

__starting_point()

def main():
    import sys
    input = lambda: sys.stdin.readline().rstrip("\r\n")
    mod = 10**9 + 7

    ans = []

    n, q = map(int, input().split())
    y = [[] for _ in range(2*10**5)] # i番目の幼稚園の(-rate, 幼児)
    data = [(0, 0)]*n # i番目の(rate, 所属)
    import heapq
    for i in range(n):
        a, b = map(int, input().split())
        data[i] = (a, b - 1)
        heapq.heappush(y[b - 1], (-a, i))
    max_rate = [] # (rate, 幼児, 所属)
    max_rate_list = [()]*(2*10**5)
    for i in range(2*10**5):
        if y[i]:
            s, t = heapq.heappop(y[i])
            heapq.heappush(max_rate, (-s, t, i))
            heapq.heappush(y[i], (s, t))
            max_rate_list[i] = (-s, t)
    from collections import defaultdict
    ng_num = defaultdict(set)
    for _ in range(q):
        c, d = map(int, input().split())
        c -= 1
        d -= 1
        a, b = data[c]
        data[c] = (a, d)
        heapq.heappush(y[d], (-a, c))
        ng_num[b].add(c)
        if c in ng_num[d]:
            ng_num[d].discard(c)
        #print(ng_num)
        while y[b]:
            s, t = heapq.heappop(y[b])
            if t not in ng_num[b]:
                heapq.heappush(max_rate, (-s, t, b))
                heapq.heappush(y[b], (s, t))
                max_rate_list[b] = (-s, t)
                break
        while y[d]:
            s, t = heapq.heappop(y[d])
            if t not in ng_num[d]:
                heapq.heappush(max_rate, (-s, t, d))
                heapq.heappush(y[d], (s, t))
                max_rate_list[d] = (-s, t)
                break
        #print(max_rate) 
        while max_rate:
            s, t, r = heapq.heappop(max_rate)
            if t not in ng_num[r] and (s, t) == max_rate_list[r]:
                ans.append(s)
                heapq.heappush(max_rate, (s, t, r))
                break
    print(*ans, sep="\n")
main()






import heapq
n, q = map(int, input().split())
belong = [-1 for i in range(n)]
rating = [0 for i in range(n)]
second = [[] for i in range(2 * 10 ** 5 + 5)]
for i in range(n):
    a, b = map(int, input().split())
    rating[i] = a
    belong[i] = b
    heapq.heappush(second[b], (-1 * a, i))
first = []
for i in range(2 * 10 ** 5 + 5):
    if second[i]:
        heapq.heappush(first, (-1 * second[i][0][0], second[i][0][1], i))
for i in range(q):
    c, d = map(int, input().split())
    before = belong[c - 1]
    belong[c - 1] = d
    heapq.heappush(second[d], (-1 * rating[c - 1], c - 1))
    if second[d][0][1] == c - 1:
        heapq.heappush(first, (rating[c - 1], c - 1, d))
    count = 0
    while second[before] and belong[second[before][0][1]] != before:
        heapq.heappop(second[before])
        count = 1
    if count and second[before]:
        heapq.heappush(first, (-1 * second[before][0][0], second[before][0][1], before))
    while not second[first[0][2]] or second[first[0][2]][0][1] != first[0][1]:
        heapq.heappop(first)
    print(first[0][0])

# E - Smart Infants

import heapq
M = 2*(10**5)
N, Q = list(map(int, input().split()))
enji = []
for i in range(N):
    enji.append(tuple(map(int, input().split())))

# その園児が今どこの幼稚園にいるか
belong = [0] * N
# 幼稚園Kの園児の優先キュー
K = [[] for _ in range(M)]
for i, (a, b) in enumerate(enji):
    heapq.heappush(K[b-1], (-a, i))
    belong[i] = b-1

#print(K)

# 最強園児の優先キュー
E = []
for i in range(M):
    if K[i] != []:
        heapq.heappush(E, (K[i][0][0]*-1, K[i][0][1], belong[K[i][0][1]]))

def insert_enji(x, y):
    # 新しい幼稚園の中で最強になれる場合
    if K[y] == [] or K[y][0][0] > enji[x][0]*-1:
        heapq.heappush(K[y], (enji[x][0]*-1, x))
        heapq.heappush(E, (K[y][0][0]*-1, K[y][0][1], belong[K[y][0][1]]))
    else:
        heapq.heappush(K[y], (enji[x][0]*-1, x))

def mainte_K(x, y):
    flg = False
    while K[y]:
        if belong[K[y][0][1]] == y:
            break
        else:
            heapq.heappop(K[y])
            flg = True
    if flg == True and K[y] != []:
        heapq.heappush(E, (-K[y][0][0], K[y][0][1], y))
            
def mainte_E():
    while E:
        if K[E[0][2]] != [] and K[E[0][2]][0] == (E[0][0] * -1, E[0][1]):
            break
        else:
            heapq.heappop(E)

for i in range(Q):
    c, d = list(map(int, input().split()))
    c -= 1
    d -= 1
    old = belong[c]
    belong[c] = d
    insert_enji(c, d)
    mainte_K(c, old)
    mainte_E()
    print((E[0][0]))


import heapq

N,Q=map(int,input().split())

yochien={}
rate={}
enzi_rate={}
enzi_rate_out={}
result=[]

for i in range(1,N+1):
    A,B=map(int,input().split())

    rate[i]=A
    yochien[i]=B

    if B not in enzi_rate:
        enzi_rate[B]=[]
    heapq.heappush(enzi_rate[B],-A)


max_enzi=[]
heapq.heapify(max_enzi)
max_enzi_out=[]
heapq.heapify(max_enzi_out)

for j in enzi_rate:
    heapq.heappush(max_enzi,-enzi_rate[j][0])

for _ in range(Q):
    C,D=map(int,input().split())

    if yochien[C] not in enzi_rate_out:
        enzi_rate_out[yochien[C]]=[]
    heapq.heappush(enzi_rate_out[yochien[C]],-rate[C])
    
    if len(enzi_rate_out[yochien[C]])>=1 and enzi_rate_out[yochien[C]][0]==enzi_rate[yochien[C]][0]:
        heapq.heappush(max_enzi_out,-enzi_rate_out[yochien[C]][0])
        while len(enzi_rate_out[yochien[C]])>=1 and enzi_rate_out[yochien[C]][0]==enzi_rate[yochien[C]][0]:
            heapq.heappop(enzi_rate_out[yochien[C]])
            heapq.heappop(enzi_rate[yochien[C]])
        if len(enzi_rate[yochien[C]])>=1:
            heapq.heappush(max_enzi,-enzi_rate[yochien[C]][0])
    
    yochien[C]=D

    if D not in enzi_rate or len(enzi_rate[D])==0:
        enzi_rate[D]=[]
        heapq.heappush(max_enzi,rate[C])
    elif -enzi_rate[D][0]<rate[C]:
        heapq.heappush(max_enzi,rate[C])
        heapq.heappush(max_enzi_out,-enzi_rate[D][0])
    
    heapq.heappush(enzi_rate[D],-rate[C])
    
    while len(max_enzi_out)>=1 and max_enzi[0]==max_enzi_out[0]:
        heapq.heappop(max_enzi)
        heapq.heappop(max_enzi_out)
    
    result.append(max_enzi[0])

for k in range(Q):
    print(result[k])

import sys
readline = sys.stdin.readline

import heapq as hq

N,Q = list(map(int,readline().split()))
NN = 2 * (10 ** 5)

# (レート, 所属園)
infants = [None] * (N + 1)
# (最強園児, 園児番号)
kinda = [[] for i in range(NN + 1)]
for i in range(N):
  a,b = list(map(int,readline().split()))
  infants[i + 1] = [a,b]
  hq.heappush(kinda[b], (-a, i + 1))

# (最弱園児, 園の番号)
all_kinda = []
for i in range(len(kinda)):
  if kinda[i]:
    hq.heappush(all_kinda, (-kinda[i][0][0], i))
  
def get_max_rate(x): # 園の最強レートを取り出す
  q = kinda[x]
  while q:
    rate, ind = q[0]
    if infants[ind][1] != x:
      hq.heappop(q)
      continue
    return -rate
  return -1
  
for i in range(Q):
  ind,next_kinda_id = list(map(int,readline().split()))
  rate,old_kinda_id = infants[ind]
  infants[ind][1] = next_kinda_id
  hq.heappush(kinda[next_kinda_id],(-rate, ind))
  
  old_kinda_max_rate = get_max_rate(old_kinda_id)
  if old_kinda_max_rate != -1:
    hq.heappush(all_kinda, (old_kinda_max_rate, old_kinda_id))
    
  next_kinda_max_rate = get_max_rate(next_kinda_id)
  if next_kinda_max_rate != -1:
    hq.heappush(all_kinda, (next_kinda_max_rate, next_kinda_id))

  while all_kinda:
    rate, kinda_id = all_kinda[0]
    if rate != get_max_rate(kinda_id):
      hq.heappop(all_kinda)
      continue
    print(rate)
    break


from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t,_ in x:t and f(l,-t[0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=y>[]and y[0];f(y,-a),f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y[0]<t:f(l,a);t and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

# codekata from https://atcoder.jp/contests/abc170/submissions/14456317
# by puzzlesolver

import sys
import heapq


input = sys.stdin.readline

def main():

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

    hsize = 2 * 10 ** 5 + 1

    h = [[] for _ in range(hsize)]

    # 園児が現在所属している幼稚園を保存
    C = [0] * N
    A = []

    for i in range(N):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        heapq.heappush(h[b], (-a, i))
        C[i] = b

    A = tuple(A)

    byodo = []

    for i in range(1, hsize):
        if len(h[i]) == 0:
            continue

        # 各幼稚園の最大値をbyodoに入れる

        x = h[i][0]
        heapq.heappush(byodo, (-x[0], x[1]))

    ans = []
    for _ in range(Q):
        c, d = [int(x) for x in input().split()]
        c -= 1

        # 移動元最大値チェック
        cfrom = C[c]
        # c園児の現在時をdに更新
        C[c] = d

        while h[cfrom]:
            x = h[cfrom][0]
            # 最大値の園児の現在の所属幼稚園がC[c]と異なればpopしたままにする
            if C[x[1]] != cfrom:
                heapq.heappop(h[cfrom])
                continue

            # 現在の最大値を平等にpush
            heapq.heappush(byodo, (-x[0], x[1]))
            break

        # c園児をd幼稚園にpush
        heapq.heappush(h[d], (-A[c], c))

        # 移動先最大値チェック
        while h[d]:
            x = h[d][0]
            # 最大値の園児の現在の所属幼稚園がdと異なればpopしたままにする
            if C[x[1]] != d:
                heapq.heappop(h[d])
                continue

            # 現在の最大値をbyodoにpush
            heapq.heappush(byodo, (-x[0], x[1]))
            break

        # 平等の最小値を取得

        while byodo:
            x = byodo[0]


            # 最小値が所属する幼稚園の最大値が異なっていればpopしたままにする
            y = h[C[x[1]]][0]
            if -y[0] != x[0]:
                heapq.heappop(byodo)
                continue

            ans.append(x[0])
            break

    print(('\n'.join(map(str, ans))))


def __starting_point():
    main()

__starting_point()

from heapq import *
MAX=2*10**5+1

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

I=[[] for _ in range(N+1)]
P=[[[],[]] for _ in range(MAX)]
S=[[],[]]

def heapdel(l,a):
  if l[0][0]==a:
    heappop(l[0])
    while l[1] and l[1][0]==l[0][0]:
      heappop(l[1])
      heappop(l[0])
  else:
    heappush(l[1],a)

def heapadd(l,a):
  heappush(l[0],a)

def heapmin(l):
  return l[0][0]

def main():
  for i in range(1,N+1):
    a,b=list(map(int,input().split()))
    I[i]+=[a,b]
    heapadd(P[b],-a)

  for i in range(1,MAX):
    if P[i][0]:
      heapadd(S,-heapmin(P[i]))

  for i in range(Q):
    c,d=list(map(int,input().split()))
    a,b=I[c]

    heapdel(S,-heapmin(P[b]))
    heapdel(P[b],-a)
    if P[b][0]:
      heapadd(S,-heapmin(P[b]))

    if P[d][0]:
      heapdel(S,-heapmin(P[d]))
    heapadd(P[d],-a)
    heapadd(S,-heapmin(P[d]))

    I[c][1]=d
    print((heapmin(S)))

main()


def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, q = map(int, input().split())
    from collections import defaultdict
    from heapq import heappush, heappop
    # 幼稚園ごとの園児リストをヒープで格納
    h = defaultdict(lambda: [])
    # 幼稚園後の最強園児を格納
    saikyo = []
    A, B = [], []
    for i in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        heappush(h[b], (-a, i)) 
    for i in h:
        x = h[i][0]
        heappush(saikyo, (-x[0], x[1]))       
    for i in range(q):
        c, d = map(int, input().split())
        c -= 1
        # 転園処理
        cfrom = B[c]
        B[c] = d
        # 移動元の最強園児のチェック
        while h[cfrom]:
            x = h[cfrom][0]
            if B[x[1]] != cfrom:
                heappop(h[cfrom])
                continue 
            heappush(saikyo,(-x[0],x[1]))
            break
        heappush(h[d],(-A[c],c))
        # 移動先の最強園児チェック
        while h[d]:
            x = h[d][0]
            if B[x[1]] != d:
                heappop(h[d])
                continue
            heappush(saikyo,(-x[0],x[1]))
            break

        # saikyoの最小値を求める。
        while saikyo:
            x = saikyo[0]

            y = h[B[x[1]]][0]
            if -y[0] != x[0]:
                heappop(saikyo)
                continue
            print(x[0])
            break
    
    print()
def __starting_point():
    main()
__starting_point()

import heapq

ymax = 200000
N, Q  = list(map(int, input().split()))

yo = [[] for i in range(ymax+1)]
ym = []
AB = [(0,0)]

for i in range(N):
  A, B  = list(map(int, input().split()))
  AB.append( (A, B) )
  heapq.heappush(yo[B],(-A,i+1))
#
for i in range(1,ymax+1):
  if yo[i]:
    mA, c = yo[i][0]
    heapq.heappush(ym,(-mA,c,i)) 
#
for i in range(Q):
  C, D  = list(map(int, input().split()))
  A, B = AB[C]
  AB[C] = (A, D)

  if  yo[B][0][1] == C:
    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):
      heapq.heappop(yo[B])
    if yo[B]:
      mA, c = yo[B][0]
      heapq.heappush(ym,(-mA,c,B)) 
#
  heapq.heappush(yo[D],(-A,C))
  mA, c = yo[D][0]
  if c == C:
    heapq.heappush(ym,(-mA,c,D)) 
#
  while ym:
    if AB[ ym[0][1] ][1] != ym[0][2]:
      heapq.heappop(ym)
    elif ym[0][1] != yo[ ym[0][2] ][0][1] :
      heapq.heappop(ym)
    else:
      break
#      
  print((ym[0][0]))
#


import heapq

ymax = 200000
N, Q = list(map(int, input().split()))

yo = [[] for i in range(ymax+1)]
ym = []
AB = [(0,0)]
s = set()

for i in range(N):
  A, B = list(map(int, input().split()))
  AB.append((A,B))
  heapq.heappush(yo[B], (-A,i+1))
  s.add(B)
for i in s:
  mA, c = yo[i][0]
  heapq.heappush(ym,(-mA,c,i))
for i in range(Q):
  C, D = list(map(int, input().split()))
  A, B = AB[C]
  AB[C] = (A, D)
  
  if yo[B][0][1] == C:
    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):
      heapq.heappop(yo[B])
    if yo[B]:
      mA, c = yo[B][0]
      heapq.heappush(ym,(-mA,c,B))
  heapq.heappush(yo[D],(-A,C))
  mA, c = yo[D][0]
  if c == C:
    heapq.heappush(ym,(-mA,c,D))

  while ym:
    if AB[ ym[0][1] ][1] != ym[0][2]:
      heapq.heappop(ym)
    elif ym[0][1] != yo[ ym[0][2] ][0][1]:
      heapq.heappop(ym)
    else:
      break
  print((ym[0][0]))


import heapq
import sys
input = sys.stdin.readline

class HeapDict:
    def __init__(self):
        self.h = []
        self.d = {}

    def insert(self,x):
        if x not in self.d or self.d[x] == 0:
            heapq.heappush(self.h, x)
        self.d.setdefault(x,0)
        self.d[x] += 1


    def erase(self,x):
        if x not in self.d or self.d[x] == 0:
            return
        else:
            self.d[x] -= 1

        while self.h:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break


    def get_min(self):
        return self.h[0]


    def pop(self):
        poped_val = self.h[0]
        self.erase(poped_val)
        return poped_val


    def exist(self, x):
        return (x in self.d and self.d[x] > 0)


    def show_h(self):
        elems = [v for v in self.h if self.d[v] > 0]
        print(elems)


    def show_d(self):
        print(self.d)



def main():
    n,q = map(int, input().split())
    kid_rates = [0]*(n+1)
    kid_kinders = [0]*(n+1)
    kinder_kid_rates = [HeapDict() for _ in range(2*(10**5)+1)]
    for i in range(n):
        ind = i+1
        a,b = map(int, input().split())
        kid_rates[ind] = a
        kid_kinders[ind] = b
        kinder_kid_rates[b].insert((a*(-1),ind))
    
    each_kinder_rate_maxs = HeapDict()
    for i, kkr in enumerate(kinder_kid_rates):
        if kkr.h:
            kkr_max = kkr.get_min()
            each_kinder_rate_maxs.insert( (kkr_max[0]*(-1), kkr_max[1], i) ) # max_rate, kid_index, kinder_index

    cdl = []
    for _ in range(q):
        c,d = map(int, input().split())
        cdl.append((c,d))

    for cd in cdl:
        c,d = cd
        to_kinder = d
        kid_rate = kid_rates[c]
        from_kinder = kid_kinders[c]

        from_kinder_max_rate = kinder_kid_rates[from_kinder].get_min()      
        each_kinder_rate_maxs.erase( (from_kinder_max_rate[0]*(-1), from_kinder_max_rate[1], from_kinder) )

        kinder_kid_rates[from_kinder].erase( (kid_rate*(-1), c) )

        if kinder_kid_rates[from_kinder].h:
            new_max_rate = kinder_kid_rates[from_kinder].get_min()
            each_kinder_rate_maxs.insert( (new_max_rate[0]*(-1), new_max_rate[1], from_kinder) )

        if kinder_kid_rates[to_kinder].h:
            to_kinder_max_rate = kinder_kid_rates[to_kinder].get_min()      
            each_kinder_rate_maxs.erase( (to_kinder_max_rate[0]*(-1), to_kinder_max_rate[1], to_kinder) )

        kinder_kid_rates[to_kinder].insert( (kid_rate*(-1), c) )
        new_to_kinder_max_rate = kinder_kid_rates[to_kinder].get_min()
        each_kinder_rate_maxs.insert( (new_to_kinder_max_rate[0]*(-1), new_to_kinder_max_rate[1], to_kinder) )

        print(each_kinder_rate_maxs.get_min()[0])
        kid_kinders[c] = to_kinder


def __starting_point():
    main()
__starting_point()

import sys
import numpy as np
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 

  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res

  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  
  @staticmethod
  def gcd(a, b): return gcd(b, a%b) if b else abs(a)

  @staticmethod
  def lcm(a, b): return abs(a // gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  
  @staticmethod
  def base_convert(n, b): # return string
    if not n: return '0'
    res = ''
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res += str(r)
    return res[::-1]


class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]


class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose


def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a


class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)

  def B(): pass
  def C(): pass 
  def D(): pass 


class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))

  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)

  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))

  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))


class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)

  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')

  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)

  def D(): pass 


class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)

  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])

  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))

  def D(): pass 


class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)

  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))

  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')

  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')


class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')

  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
    
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
      
  def D():
    n, *c = map(int, sys.stdin.read().split())
    inf = float('inf')
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))


class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)

  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')

  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  
  def D(): pass 


class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)

  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)

  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
    
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s))
      
  def D(): pass 


class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)

  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)

  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)

  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())

  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')

  def D(): pass 


class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break

  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
      
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])

  def D():
    n, *a = map(int, sys.stdin.read().split())
    cand = set(a)
    cnt = 0
    for x, c in sorted(Counter(a).items()):
      cnt += c == 1 and x in cand
      cand -= set(range(x*2, 10**6+1, x))
    print(cnt)


  def E():
    n, q = map(int, sys.stdin.readline().split())
    queue = [] 
    num_kindergarten = 2*10**5
    queue_kindergarten = [[] for _ in range(num_kindergarten)]
    highest_kindergarten = [None] * num_kindergarten
    where = [None] * n
    rate = [None] * n

    def entry(i, k):
      where[i] = k
      while queue_kindergarten[k]:
        r, j = heappop(queue_kindergarten[k])
        if where[j] != k or j == i: continue 
        if rate[i] > -r:
          highest_kindergarten[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(queue_kindergarten[k], (r, j))
        break
      else:
        highest_kindergarten[k] = rate[i]
        heappush(queue, (rate[i], k, i))
      heappush(queue_kindergarten[k], (-rate[i], i))

    def transfer(i, k):
      now = where[i]
      while queue_kindergarten[now]:
        r, j = heappop(queue_kindergarten[now])
        if where[j] == now: break
      if j != i:
        heappush(queue_kindergarten[now], (r, j))
      else:
        while queue_kindergarten[now]:
          r, j = heappop(queue_kindergarten[now])
          if where[j] != now or j == i: continue
          highest_kindergarten[now] = -r
          heappush(queue, (-r, now, j))
          heappush(queue_kindergarten[now], (r, j))
          break
        else:
          highest_kindergarten[now] = None
      entry(i, k)

    def inquire():
      while True:
        r, k, i = heappop(queue)
        if where[i] != k or r != highest_kindergarten[k]: continue 
        heappush(queue, (r, k, i))
        return r

    for i in range(n):
      a, b = map(int, sys.stdin.readline().split())
      rate[i] = a 
      entry(i, b-1)

    for _ in range(q):
      c, d = map(int, sys.stdin.readline().split())
      transfer(c-1, d-1)
      print(inquire())
    


  def F(): pass 

def __starting_point():
  ABC170.E()
__starting_point()

def getN():
    return int(input())
def getNM():
    return list(map(int, input().split()))
def getList():
    return list(map(int, input().split()))
def getZList():
    return [int(x) - 1 for x in input().split()]
from collections import defaultdict, deque
import math
import copy
from bisect import bisect_left, bisect_right
import heapq
import sys
input = sys.stdin.readline
# sys.setrecursionlimit(1000000)
INF = 10 ** 17
MOD = 1000000007
 
class LazyHeap():
    def __init__(self, init_arr=[]):
        self.heap = []
        self.lazy = defaultdict(int)
        self.len = 0
        for init_element in init_arr:
            heapq.heappush(self.heap, init_element)
            self.len += 1
 
    def __len__(self):
        return self.len
 
    def push(self, k):
        heapq.heappush(self.heap, k)
        self.len += 1
 
    def pop(self):
        self._clear()
        return heapq.heappop(self.heap)
        
    def get(self):
        self._clear()
        return self.heap[0]
 
    def _clear(self):
        while True:
            cand = self.heap[0]
            if cand in self.lazy and self.lazy[cand] > 0:
                heapq.heappop(self.heap)
                self.lazy[cand] -= 1
 
            else:
                return
 
    def remove(self, k):
        self.lazy[k] += 1
        self.len -= 1
 
N_KINDER = 200200
# N_KINDER = 2 * (10 ** 5) + 1
n, q = getList()
kinder = [LazyHeap() for i in range(N_KINDER)]
saikyo = LazyHeap()
saikyo_ref = []
pos_ref = [-1 for i in range(n)]
enji_ref = []

for i in range(n):
    a, b = getList()
    b -= 1
    enji_ref.append((-a, b))
    kinder[b].push(-a)

for kin in kinder:
    if kin:
        candidate = kin.get()
        saikyo.push(-candidate)
        saikyo_ref.append(candidate)
    else:
        saikyo_ref.append(0)

for i in range(q):
    c, d = getZList()
    mv_rate = enji_ref[c][0]
    prev = enji_ref[c][1]
    nxt = d
    pos_ref[c] = d
    enji_ref[c] = (mv_rate, d)
    # 移動元についての処理
    kinder[prev].remove(mv_rate)

    kp, kn = kinder[prev], kinder[nxt]
    if not kp:
        # 移動して園児0人になった場合
        saikyo_ref[prev] = 0
        saikyo.remove(-mv_rate)
    elif saikyo_ref[prev] != kp.get():
        saikyo.remove(-mv_rate)
        saikyo.push(-kp.get())
        saikyo_ref[prev] = kp.get()

    # 移動先についての処理
    kn.push(mv_rate)
    if mv_rate < saikyo_ref[nxt]:
        saikyo.remove(-saikyo_ref[nxt])
        saikyo.push(-mv_rate)
        saikyo_ref[nxt] = mv_rate

    print((saikyo.get()))
# print(rate)


from heapq import heappop, heappush


class DeletableHeapq:
    """Deletable Heapq: A heapq supporting lazy deletion of values."""

    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:
        self.is_max_heap = is_max_heap
        self.size = 0
        self._set = set()
        self._heap = []

        if initial_values:
            for v in initial_values:
                self.push(v)

    @property
    def top(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        return self._heap[0] if not self.is_max_heap else -self._heap[0]

    def pop(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        self.size -= 1
        res = heappop(self._heap)
        self._set.discard(res)
        return res if not self.is_max_heap else -res

    def push(self, value):
        if value is None:
            return
        if self.is_max_heap:
            value *= -1
        if value in self._set:
            return
        self.size += 1
        heappush(self._heap, value)
        self._set.add(value)

    def delete(self, value):
        if value is None:
            return
        if self.is_max_heap:
            value *= -1
        if value not in self._set:
            return
        self.size -= 1
        self._set.discard(value)


def main():
    # https://atcoder.jp/contests/abc170/tasks/abc170_e
    encode_kindy = lambda x, y: (x << 18) + y
    decode_kindy = lambda x: (x >> 18, x & ((1 << 18) - 1))
    encode_smarts = lambda x, y, z: (x << 36) + (y << 18) + z
    decode_smarts_rate = lambda x: x >> 36

    N, _, *X = list(map(int, open(0).read().split()))
    AB, CD = X[: 2 * N], X[2 * N :]
    rate, belonging = [0] * (N + 1), [0] * (N + 1)
    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]

    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):
        rate[i], belonging[i] = a, b
        kindy[b].push(encode_kindy(a, i))

    smart_infants = DeletableHeapq(
        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)
    )
    res = []
    for c, next_k in zip(*[iter(CD)] * 2):
        prev_k = belonging[c]
        belonging[c] = next_k

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))

        kindy[prev_k].delete(encode_kindy(rate[c], c))
        kindy[next_k].push(encode_kindy(rate[c], c))

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))

        res.append(decode_smarts_rate(smart_infants.top))

    print(("\n".join(map(str, res))))


def __starting_point():
    main()

__starting_point()

from heapq import heappop, heappush, heapify


class RemovableHeap(list):
    from heapq import heappop, heappush, heapify

    def __init__(self, *args, **kwargs):
        # super().__init__(*args, **kwargs)
        self.unremoved_elements = []

    def remove(self, value):
        heappush(self.unremoved_elements, value)
        while self.unremoved_elements and self.unremoved_elements[0] == self[0]:
            heappop(self.unremoved_elements)
            heappop(self)


N, Q = map(int, input().split())
AB = [list(map(int, input().split())) for _ in range(N)]
CD = [list(map(int, input().split())) for _ in range(Q)]
M = 2 * 10 ** 5
maxA = 10 ** 9

for i in range(N):
    AB[i][1] -= 1
for i in range(Q):
    CD[i][0] -= 1
    CD[i][1] -= 1

youchiens = [RemovableHeap() for _ in range(M)]

for a, b in AB:
    youchiens[b].append(-a)
for i in range(Q):
    heapify(youchiens[i])

saikyoenjis = RemovableHeap()
for youchien in youchiens:
    if youchien:
        saikyoenjis.append(-youchien[0])
heapify(saikyoenjis)

ans = []
for c, d in CD:
    old_youchien = AB[c][1]

    # 最強園児のレートの集合から、転園する園児の元の幼稚園の元の最強園児のレートを、削除
    # する
    saikyoenjis.remove(-youchiens[old_youchien][0])

    # 転園する園児の元の幼稚園のレートの集合から、転園する園児のレートを、削除する
    youchiens[old_youchien].remove(-AB[c][0])

    # 最強園児のレートの集合に、転園する園児の元の幼稚園の新しい最強園児のレートを、挿入
    # する（園児が一人もいない場合何もしない）
    if youchiens[old_youchien]:
        heappush(saikyoenjis, -youchiens[old_youchien][0])

    # 最強園児のレートの集合から、転園する園児の新しい幼稚園の元の最強園児のレートを、削
    # 除する（園児が一人もいない場合何もしない）
    if youchiens[d]:
        saikyoenjis.remove(-youchiens[d][0])

    # 転園する園児の新しい幼稚園のレートの集合に、転園する園児のレートを、挿入する
    heappush(youchiens[d], -AB[c][0])

    # 最強園児のレートの集合に、転園する園児の新しい幼稚園の新しい最強園児のレートを、挿
    # 入する
    heappush(saikyoenjis, -youchiens[d][0])
    ans.append(saikyoenjis[0])

    # 転園する園児の所属する幼稚園の番号を更新する
    AB[c][1] = d

print(*ans, sep="\n")


import heapq as hq
class Delheap:
    def __init__(self):
        self.heap = []
        self.deleted = {}
    def __repr__(self):
        return str(self.heap)
    def push(self, x):
        hq.heappush(self.heap, x)
    def pop(self):
        while self.heap:
            x = hq.heappop(self.heap)
            if x in self.deleted and self.deleted[x] > 0:
                self.deleted[x] -= 1
                if self.deleted[x] == 0:
                    del self.deleted[x]
                continue
            return x
        return None
    def delete(self, x):
        if x not in self.deleted:
            self.deleted[x] = 1
        else:
            self.deleted[x] += 1
    def peek(self):
        x = self.pop()
        if x != None:
            self.push(x)
        return x
def __starting_point():
    N, Q = map(int,input().split())
    shozoku = []
    rate = []
    saikyo = Delheap()
    nurs = [Delheap() for _ in range(2*10**5)]
    for _ in range(N):
        a,b = map(int,input().split())
        b -= 1
        shozoku.append(b)
        rate.append(a)
        nurs[b].push(-a)
        
    for i in range(2*10**5):
        x = nurs[i].peek()
        if x != None:
            saikyo.push(-x)
    anss = []
    for _ in range(Q):
        c,d = map(int,input().split())
        c -= 1
        d -= 1
        nur = shozoku[c]
        saikyo.delete(-nurs[nur].peek())
        nurs[nur].delete(-rate[c])
        t = nurs[nur].peek()
        if t != None:
            saikyo.push(-t)
        shozoku[c] = d
        t = nurs[d].peek()
        if t != None:
            saikyo.delete(-t)
        nurs[d].push(-rate[c])
        saikyo.push(-nurs[d].peek())
        anss.append(saikyo.peek())
    print(*anss, sep="\n")
__starting_point()

import heapq

ymax = 200000
N, Q  = list(map(int, input().split()))

yo = [[] for i in range(ymax+1)]
ym = []
AB = [(0,0)]

for i in range(N):
  A, B  = list(map(int, input().split()))
  AB.append( (A, B) )
  heapq.heappush(yo[B],(-A,i+1))
#
for i in range(1,ymax+1):
  if yo[i]:
    mA, c = yo[i][0]
    heapq.heappush(ym,(-mA,c,i)) 
#
for i in range(Q):
  C, D  = list(map(int, input().split()))
  A, B = AB[C]
  AB[C] = (A, D)
  while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):
    heapq.heappop(yo[B])
  if yo[B]:
    mA, c = yo[B][0]
    heapq.heappush(ym,(-mA,c,B)) 

  heapq.heappush(yo[D],(-A,C))
  if yo[D]:
    mA, c = yo[D][0]
    heapq.heappush(ym,(-mA,c,D)) 
#
  while ym:
    if AB[ ym[0][1] ][1] != ym[0][2]:
      heapq.heappop(ym)
    elif ym[0][1] != yo[ ym[0][2] ][0][1] :
      heapq.heappop(ym)
    else:
      break
#      
  print((ym[0][0]))
#


# coding: utf-8
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
top = []
left_top = []
infants = [[] for _ in range(2*10**5+1)]  # 1-indexed
left = [[] for _ in range(2*10**5+1)]
dic = defaultdict(tuple)
for i in range(1, N+1):
    a, b = lr()
    heappush(infants[b], (-a, i))
    dic[i] = (a, b)

for i in range(1, 2*10**5+1):
    if infants[i]:
        rate, id = infants[i][0]
        heappush(top, (-rate, id))

for _ in range(Q):
    c, next = lr()
    r, prev = dic[c]
    dic[c] = (r, next)
    r3, prev_top = infants[prev][0]
    heappush(left_top, (-r3, prev_top))
    heappush(left[prev], (-r, c))
    while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:
        heappop(infants[prev])
        heappop(left[prev])
    if infants[prev]:
        rate, id = infants[prev][0]
        heappush(top, (-rate, id))
    if infants[next]:
        heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # idをpush
    heappush(infants[next], (-r, c))  # tupleでpush
    while left[next] and infants[next][0][1] == left[next][0][1]:
        heappop(infants[next])
        heappop(left[next])
    r2, id2 = infants[next][0]
    heappush(top, (-r2, id2))
    while left_top and top[0][1] == left_top[0][1]:
        heappop(top); heappop(left_top)
    answer = top[0][0]
    print(answer)


import sys
import bisect
import heapq

N_MAX = 2*10**5
A_MAX = 10**9

A = []
B = []
BB = [[] for _ in range(N_MAX)]

BBmax = []  # 各幼稚園の最大値

def max_rate_in_a_kg(kg):
    
    # 対象の幼稚園の最大レートを更新
    while BB[kg]:
        rate, k = BB[kg][0]
        if B[k] == kg:  # いるならOK
            return -rate
        else:
            heapq.heappop(BB[kg])  # 転園していれば削除

    return 0


def max_rate():
    while BBmax:
        rate, kg_no = BBmax[0]
        if max_rate_in_a_kg(kg_no) == rate:
            return rate
        else:
            heapq.heappop(BBmax)
    return None

def p():
    for i in range(len(BB)):
        if BB[i] != []:
            print(i, BB[i])

def pp():
    print("BBmax : ", end="")
    for i in range(len(BBmax)):
        print(BBmax[i], end=" ")
    print()


def main():

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

    for i in range(N):
        a, b = map(int, sys.stdin.readline().split())
        A.append(a)  # レート
        B.append(b-1)  # 幼稚園番号も0からにする
        heapq.heappush(BB[b-1],(-a,i))  # BB は最大が最も左に来るようにする

    for kg_no in range(N_MAX):
        rate = max_rate_in_a_kg(kg_no)
        if rate > 0:
            BBmax.append((rate, kg_no))
    heapq.heapify(BBmax)

    # p()
    # pp()

    for i in range(Q):
        # print("====")
        c, d = map(int, sys.stdin.readline().split())

        kid_no = c-1  # 園児番号
        after = d-1  # 幼稚園番号

        # 転出
        before = B[kid_no]
        B[kid_no] = after  # 園児の所属を更新

        heapq.heappush(BB[after], (-A[kid_no], kid_no))  # 幼稚園の最大を更新
        # p()

        new_rate_kg = max_rate_in_a_kg(before)  # 転入元の最大を更新
        if new_rate_kg != 0:
            heapq.heappush(BBmax, (new_rate_kg, before))

        new_rate_kg = max_rate_in_a_kg(after)  # 転園先の最大レートを更新
        if new_rate_kg != 0:
            heapq.heappush(BBmax, (new_rate_kg, after))  # BBmax を更新

        # pp()
        print(max_rate())

def __starting_point():
    main()
__starting_point()

def main():
    import sys
    def input(): return sys.stdin.readline().rstrip()
    n, q = map(int, input().split())
    from collections import defaultdict
    from heapq import heappush, heappop
    # 幼稚園ごとの園児リストをヒープで格納
    h = defaultdict(lambda: [])
    # 幼稚園後の最強園児を格納
    saikyo = []
    A, B = [], []
    for i in range(n):
        a, b = map(int, input().split())
        A.append(a)
        B.append(b)
        heappush(h[b], (-a, i)) 
    for i in h:
        x = h[i][0]
        heappush(saikyo, (-x[0], x[1]))       
    for i in range(q):
        c, d = map(int, input().split())
        c -= 1
        # 転園処理
        cfrom = B[c]
        B[c] = d
        # 移動元の最強園児のチェック
        while h[cfrom]:
            x = h[cfrom][0]
            if B[x[1]] != cfrom:
                heappop(h[cfrom])
                continue
            heappush(saikyo, (-x[0], x[1]))
            break
        heappush(h[d], (-A[c], c))
        # 移動先の最強園児チェック
        while h[d]:
            x = h[d][0]
            # if B[x[1]] != d:
            #     heappop(h[d])
            #     continue
            heappush(saikyo, (-x[0], x[1]))
            break

        # saikyoの最小値を求める。
        while saikyo:
            x = saikyo[0]

            y = h[B[x[1]]][0]
            if -y[0] != x[0]:
                heappop(saikyo)
                continue
            print(x[0])
            break
    
    print()
def __starting_point():
    main()
__starting_point()

import heapq
N,Q=map(int,input().split())
M=2*(10**5)
belong=[]
rate=[]
garden=[[]for _ in range(M)]
for c in range(N):
    A,B=map(int,input().split())
    B-=1
    belong.append(B)
    rate.append(A)
    heapq.heappush(garden[B],(-A,c))
    
strong=[]

for i in range(M):
    if garden[i]:
        A,c=garden[i][0]
        heapq.heappush(strong,(-A,c,i))
        
for i in range(Q):
    C,D=map(int,input().split())
    C-=1
    D-=1
    now=belong[C]
    belong[C]=D
    
    while garden[now]:
        A,c=garden[now][0]
        if belong[c]!=now:
            heapq.heappop(garden[now])
        else:
            heapq.heappush(strong,(-A,c,now))
            break
            
    heapq.heappush(garden[D],(-rate[C],C))
    A,c=garden[D][0]
    heapq.heappush(strong,(-A,c,D))
    
    while strong:
        A,c,d=strong[0]
        if belong[c]!=d or garden[d][0][1]!=c:
            heapq.heappop(strong)
        else:
            print(A)
            break

from heapq import heappop, heappush
from typing import Optional


class DeletableHeapq:
    """Deletable Heapq: a heapq that supports lazy deletion of values."""

    __slots__ = ["_is_max_heap", "_set", "_heap"]

    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:
        self._is_max_heap = is_max_heap
        self._set = set()
        self._heap = []

        if initial_values:
            for v in initial_values:
                self.push(v)

    def __len__(self) -> int:
        return len(self._set)

    @property
    def is_empty(self) -> bool:
        """Return whether the heap has no values or not."""
        return len(self) == 0

    @property
    def top(self) -> Optional[int]:
        """Return the minimum value if is_max_heap is False;
        otherwise, return the maximum value from the heap.
        If the heap is empty, None is returned.
        """
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        return self._heap[0] if not self._is_max_heap else -self._heap[0]

    def push(self, value: int) -> None:
        """Push value into the heap."""
        if self._is_max_heap:
            value = -value
        if value in self._set:
            return
        heappush(self._heap, value)
        self._set.add(value)

    def delete(self, value: int) -> None:
        """Delete value from the heap."""
        if self._is_max_heap:
            value = -value
        if value not in self._set:
            return
        self._set.discard(value)


def main():
    # https://atcoder.jp/contests/abc170/tasks/abc170_e
    N, _, *X = list(map(int, open(0).read().split()))
    AB, CD = X[: 2 * N], X[2 * N :]
    rate, belonging = [0] * (N + 1), [0] * (N + 1)
    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]

    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):
        rate[i], belonging[i] = (a << 18) + i, b
        kindy[b].push(rate[i])

    smarts = DeletableHeapq(*(k.top for k in kindy if not k.is_empty))
    res = []
    for c, d in zip(*[iter(CD)] * 2):
        prev_k, next_k = kindy[belonging[c]], kindy[d]
        belonging[c] = d

        for k in (prev_k, next_k):
            if not k.is_empty:
                smarts.delete(k.top)

        prev_k.delete(rate[c])
        next_k.push(rate[c])

        for k in (prev_k, next_k):
            if not k.is_empty:
                smarts.push(k.top)

        res.append(smarts.top >> 18)

    print(("\n".join(map(str, res))))


def __starting_point():
    main()

__starting_point()

import heapq
import sys
input = sys.stdin.readline
 
N, Q = map(int, input().split())
AB = [tuple(map(int, input().split())) for _ in range(N)]
CD = [tuple(map(int, input().split())) for _ in range(Q)]
H = 2*10**5 # 幼稚園
 
INF = 10**18
rates = [[] for _ in range(H)]
members = [set() for _ in range(H)]
belongs = [-1]*N
for i,(a,b) in enumerate(AB):
    b -= 1
    heapq.heappush(rates[b], (-a,i))
    members[b].add(i)
    belongs[i] = b
 
mxrates = []
for num,r in enumerate(rates):
    if len(r) > 0:
        heapq.heappush(mxrates, (-r[0][0], num)) # 幼稚園ごとの最大値をいれる
 
for c,d in CD:
    c, d = c-1, d-1
    old = belongs[c]
    belongs[c] = d
    members[old].remove(c)
    members[d].add(c)
    # 転園元の最大値を最新化する
    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:
        heapq.heappop(rates[old])
    # 最新化された転園元から改めて取得
    if len(rates[old]) > 0:
        heapq.heappush(mxrates, (-rates[old][0][0], old))
    # 転園先に追加
    heapq.heappush(rates[d], (-AB[c][0], c))
    heapq.heappush(mxrates, (AB[c][0], d))
    while mxrates:
        rate, num = mxrates[0]
        # mxratesの最小が最新ではない場合
        if len(rates[num]) == 0 or -rates[num][0][0] != rate:
            heapq.heappop(mxrates)
        else:
            print(rate)
            break

import sys
sys.setrecursionlimit(10**7) #再帰関数の上限,10**5以上の場合python
import math
from copy import copy, deepcopy
from copy import deepcopy as dcp
from operator import itemgetter
from bisect import bisect_left, bisect, bisect_right#2分探索
#bisect_left(l,x), bisect(l,x)#aはソート済みである必要あり。aの中からx未満の要素数を返す。rightだと以下
from collections import deque
#deque(l), pop(), append(x), popleft(), appendleft(x)
##listでqueの代用をするとO(N)の計算量がかかってしまうので注意
from collections import Counter#文字列を個数カウント辞書に、
#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()
from itertools import accumulate#累積和
#list(accumulate(l))
from heapq import heapify,heappop,heappush
#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)としないこと、返り値はNone
#import fractions#古いatcoderコンテストの場合GCDなどはここからimportする
from functools import lru_cache#pypyでもうごく
#@lru_cache(maxsize = None)#maxsizeは保存するデータ数の最大値、2**nが最も高効率

def input(): return sys.stdin.readline()[:-1]
def printl(li): _=print(*li, sep="\n") if li else None
def argsort(s, return_sorted=False): 
    inds=sorted(range(len(s)), key=lambda k: s[k])
    if return_sorted: return inds, [s[i] for i in inds]
    return inds
def alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65
def num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)
def matmat(A,B):
    K,N,M=len(B),len(A),len(B[0])
    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]
def matvec(M,v):
    N,size=len(v),len(M)
    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]
def T(M):
    n,m=len(M),len(M[0])
    return [[M[j][i] for j in range(n)] for i in range(m)]
def main():
    mod = 1000000007
    #w.sort(key=itemgetter(1),reversed=True)  #二個目の要素で降順並び替え

    #N = int(input())
    N, Q = map(int, input().split())
    #A = tuple(map(int, input().split())) #1行ベクトル
    #L = tuple(int(input()) for i in range(N)) #改行ベクトル
    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #改行行列

    l=[Counter() for _ in range(2*10**5)]
    rates=[[] for _ in range(2*10**5)]
    dic=dict()
    for i in range(N):
        a,b=map(int, input().split())
        b-=1
        l[b][a]+=1
        dic[i]=(a,b)
        heappush(rates[b],-a)
    tot=[]
    for b,r in enumerate(rates):
        if r:
            a=-r[0]
            heappush(tot,(a,b))
    

    qs = tuple(tuple(map(int, input().split())) for i in range(Q))
    for c,d in qs:
        c-=1
        d-=1
        a,b=dic[c]
        l[b][a]-=1
        l[d][a]+=1
        dic[c]=(a,d)
        heappush(rates[d],-a)
        heappush(tot,(a,d))
        rm=-rates[b][0]
        while rates[b] and l[b][-rates[b][0]]==0:
            heappop(rates[b])

        if rates[b]:
            heappush(tot,(-rates[b][0],b))

        m,mb=tot[0]
        #print(l[0],l[1],l[2])
        while l[mb][m]<1 or m!=-rates[mb][0]:
            heappop(tot)
            
            m,mb=tot[0]
            
        print(m)
        









def __starting_point():
    main()

__starting_point()

import heapq


class HeapDict:
    def __init__(self):
        # heapqとdictを用意
        self.h = []
        self.d = dict()

    def insert(self, x):
        heapq.heappush(self.h, x)
        if x not in self.d:
            self.d[x] = 1
        else:
            self.d[x] += 1

    def erase(self, x):
        if x not in self.d or self.d[x] == 0:
            print((x, "is not in HeapDict"))
            return
        else:
            self.d[x] -= 1

        while len(self.h) != 0:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self, x):
        if x in self.d and self.d[x] != 0:
            return True
        else:
            False

    def get_min(self):
        return self.h[0]

    def size(self):
        return len(self.h)


def main():
    N, Q = list(map(int, input().split()))
    A = []  # レート
    B = []  # 所属幼稚園
    con = 2 * 10 ** 5
    INF = 10 ** 18
    youchi = [HeapDict() for _ in range(con)]  # 各幼稚園に対するHeapDict
    max_values = HeapDict()  # 各幼稚園の最大値のHeapDict
    for i in range(N):
        a, b = list(map(int, input().split()))
        b -= 1
        A.append(a)
        B.append(b)
        youchi[b].insert(-a)

    for i in range(con):  # 各幼稚園の最大値をまとめる
        if youchi[i].size() != 0:
            max_values.insert(-youchi[i].get_min())

    for i in range(Q):
        c, d = list(map(int, input().split()))
        c -= 1
        d -= 1
        rate = A[c]
        youchi_now = B[c]
        youchi_next = d

        # 最強園児のレートの集合から、転園する園児の元の幼稚園の元の最強園児のレートを、削除する
        max_values.erase(-youchi[youchi_now].get_min())

        # 転園する園児の元の幼稚園のレートの集合から、転園する園児のレートを、削除する
        youchi[youchi_now].erase(-rate)

        # 最強園児のレートの集合に、転園する園児の元の幼稚園の新しい最強園児のレートを、挿入する(園児が一人もいない場合何もしない)
        if youchi[youchi_now].size() != 0:
            max_values.insert(-youchi[youchi_now].get_min())

        # 最強園児のレートの集合から、転園する園児の新しい幼稚園の元の最強園児のレートを、削除する(園児が一人もいない場合何もしない)
        if youchi[youchi_next].size() != 0:
            max_values.erase(-youchi[youchi_next].get_min())

        # 転園する園児の新しい幼稚園のレートの集合に、転園する園児のレートを、挿入する
        youchi[youchi_next].insert(-rate)

        # 最強園児のレートの集合に、転園する園児の新しい幼稚園の新しい最強園児のレートを、挿入する
        max_values.insert(-youchi[youchi_next].get_min())

        # 転園する園児の所属する幼稚園の番号を更新する
        B[c] = youchi_next

        print((max_values.get_min()))


def __starting_point():
    main()

__starting_point()

from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t,_ in x:t and f(l,-t[0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=y and y[0]or 0;f(y,-a),f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y[0]!=t:f(l,a);t<0and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

import sys
import numpy as np
from heapq import heappush, heappop 
from bisect import bisect_left as bi_l, bisect_right as bi_r
from collections import deque, Counter, defaultdict
from itertools import combinations, product
import string 
import math 
inf = float('inf')
MOD = 10**9+7
# MOD = 998244353


class NumberTheory():
  def __init__(self, n=2*10**6, numpy=True):
    self.n = n
    self.np_flg = numpy 
    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)
  
  def sieve_of_eratosthenes(self, n):
    if self.np_flg:
      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0
      for i in range(2, int(n**.5)+1):
        if sieve[i]: sieve[i*2::i] = 0
      prime_numbers = np.flatnonzero(sieve)
    else:
      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0
      for i in range(2, int(n**.5)+1):
        if not sieve[i]: continue
        for j in range(i*2, n+1, i): sieve[j] = 0
      prime_numbers = [i for i in range(2, n+1) if sieve[i]]
    return sieve, prime_numbers 

  def prime_factorize(self, n):
    res = dict()
    if n < 2: return res
    border = int(n**.5)
    for p in self.prime_numbers:
      if p > border: break
      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p
      if n == 1: return res
    res[n] = 1; return res

  def prime_factorize_factorial(self, n):
    res = dict()
    for i in range(2, n+1):
      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c
    return res
  
  @staticmethod
  def gcd(a, b): return gcd(b, a%b) if b else abs(a)

  @staticmethod
  def lcm(a, b): return abs(a // gcd(a, b) * b)

  @staticmethod
  def find_divisors(n):
    divisors = []
    for i in range(1, int(n**.5)+1):
      if n%i: continue
      divisors.append(i)
      j = n // i
      if j != i: divisors.append(j)
    return divisors
  
  @staticmethod
  def base_convert(n, b):
    if not n: return [0]
    res = []
    while n:
      n, r = divmod(n, b)
      if r < 0: n += 1; r -= b
      res.append(r)
    return res


class UnionFind():
  def __init__(self, n=10**6):
    self.root = list(range(n))
    self.height = [0] * n 
    self.size = [1] * n 
  
  def find_root(self, u):
    if self.root[u] == u: return u
    self.root[u] = self.find_root(self.root[u])
    return self.root[u]
  
  def unite(self, u, v):
    ru = self.find_root(u)
    rv = self.find_root(v)
    if ru == rv: return 
    hu = self.height[ru]
    hv = self.height[rv]
    if hu >= hv:
      self.root[rv] = ru 
      self.size[ru] += self.size[rv]
      self.height[ru] = max(hu, hv+1)
    else:
      self.root[ru] = rv 
      self.size[rv] += self.size[ru]


class Combinatorics():
  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):
    self.mod = mod
    self.nCr = dict()
    self.np_flg=numpy
    self.make_mod_tables(N, n)

  sys.setrecursionlimit(10**6)
  def choose(self, n, r, mod=None): # no mod, or mod ≠ prime
    if r > n or r < 0: return 0
    if r == 0: return 1
    if (n, r) in self.nCr: return self.nCr[(n, r)]
    if not mod:
      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))
    else:
      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod
    return self.nCr[(n,r)]
  
  def cumprod(self, a):
    p = self.mod
    l = len(a); sql = int(np.sqrt(l)+1)
    a = np.resize(a, sql**2).reshape(sql, sql)
    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p
    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p
    return np.ravel(a)[:l]

  def make_mod_tables(self, N, n):
    p = self.mod
    if self.np_flg:
      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)
      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)
      ifac = self.cumprod(ifac)[n::-1]
      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;
      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p
    else:
      fac = [None]*(n+1); fac[0] = 1
      for i in range(n): fac[i+1] = fac[i]*(i+1)%p
      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)
      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p
      n_choose = [None] * (n+1); n_choose[0] = 1
      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p
      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p
    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose
  
  def mod_choose(self, n, r):
    return self.fac[n]*self.ifac[r]%self.mod*self.ifac[n-r]%self.mod


def z_algorithm(s):
  n = len(s)
  a = [0] * n; a[0] = n
  l = r = -1
  for i in range(1, n):
    if r >= i: a[i] = min(a[i-l], r-i)
    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1
    if i+a[i] >= r: l, r = i, i+a[i]
  return a


class ABC001():
  def A():
    h1, h2 = map(int, sys.stdin.read().split())
    print(h1-h2)

  def B(): pass
  def C(): pass 
  def D(): pass 


class ABC002():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(max(x, y))

  def B():
    vowels = set('aeiou')
    s = sys.stdin.readline().rstrip() 
    t = ''
    for c in s:
      if c in vowels: continue 
      t += c 
    print(t)

  def C():
    *coords, = map(int, sys.stdin.readline().split())
    def triangle_area(x0, y0, x1, y1, x2, y2):
      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;
      return abs(x1*y2 - x2*y1) / 2
    print(triangle_area(*coords))

  def D():
    n, m = map(int, sys.stdin.readline().split())
    edges = set()
    for _ in range(m):
      x, y = map(int, sys.stdin.readline().split())
      x -= 1; y -= 1
      edges.add((x, y))
    cand = []
    for i in range(1, 1<<n):
      s = [j for j in range(n) if i>>j & 1]
      for x, y in combinations(s, 2):
        if (x, y) not in edges: break
      else:
        cand.append(len(s))
    print(max(cand))


class ABC003():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)*5000)

  def B():
    atcoder = set('atcoder')
    s, t = sys.stdin.read().split()
    for i in range(len(s)):
      if s[i] == t[i]: continue
      if s[i] == '@' and t[i] in atcoder: continue 
      if t[i] == '@' and s[i] in atcoder: continue
      print('You will lose')
      return 
    print('You can win')

  def C():
    n, k, *r = map(int, sys.stdin.read().split())
    res = 0
    for x in sorted(r)[-k:]:
      res = (res+x) / 2
    print(res)

  def D(): pass 


class ABC004():
  def A():
    print(int(sys.stdin.readline().rstrip())*2)

  def B():
    c = [sys.stdin.readline().rstrip() for _ in range(4)]
    for l in c[::-1]:
      print(l[::-1])

  def C():
    n = int(sys.stdin.readline().rstrip())
    n %= 30
    res = list(range(1, 7))
    for i in range(n):
      i %= 5
      res[i], res[i+1] = res[i+1], res[i]
    print(''.join(map(str, res)))

  def D(): pass 


class ABC005():
  def A():
    x, y = map(int, sys.stdin.readline().split())
    print(y//x)

  def B():
    n, *t = map(int, sys.stdin.read().split())
    print(min(t))

  def C():
    t = int(sys.stdin.readline().rstrip())
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    m = int(sys.stdin.readline().rstrip())
    b = [int(x) for x in sys.stdin.readline().split()]
    i = 0
    for p in b:
      if i == n: print('no'); return 
      while p-a[i] > t:
        i += 1
        if i == n: print('no'); return 
      if a[i] > p: print('no'); return 
      i += 1
    print('yes')

  def D():
    n = int(sys.stdin.readline().rstrip())
    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)
    s = d.cumsum(axis=0).cumsum(axis=1)
    s = np.pad(s, 1)
    max_del = np.zeros((n+1, n+1), dtype=np.int64)
    for y in range(1, n+1):
      for x in range(1, n+1):
        max_del[y, x] = np.amax(s[y:n+1, x:n+1] - s[0:n-y+1, x:n+1] - s[y:n+1, 0:n-x+1] + s[0:n-y+1, 0:n-x+1])
    res = np.arange(n**2+1)[:, None]
    i = np.arange(1, n+1)
    res = max_del[i, np.minimum(res//i, n)].max(axis=1)
    q = int(sys.stdin.readline().rstrip())
    p = np.array(sys.stdin.read().split(), dtype=np.int64)
    print(*res[p], sep='\n')


class ABC006():
  def A():
    n = sys.stdin.readline().rstrip()
    if '3' in n: print('YES')
    elif int(n)%3 == 0: print('YES')
    else: print('NO')

  def B():
    mod = 10007
    t = [0, 0, 1]
    for _ in range(1001001):
      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod
    n = int(sys.stdin.readline().rstrip())
    print(t[n-1])
    
  def C():
    n, m = map(int, sys.stdin.readline().split())
    cnt = [0, 0, 0]
    if m == 1: cnt = [-1, -1, -1]
    else:
      if m & 1: m -= 3; cnt[1] += 1; n -= 1
      cnt[2] = m//2 - n 
      cnt[0] = n - cnt[2]
    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)
    else: print(*cnt, sep=' ')
      
  def D():
    n, *c = map(int, sys.stdin.read().split())
    lis = [inf]*n 
    for x in c: lis[bi_l(lis, x)] = x 
    print(n - bi_l(lis, inf))


class ABC007():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n-1)

  def B():
    s = sys.stdin.readline().rstrip()
    if s == 'a': print(-1)
    else: print('a')

  def C():
    r, c = map(int, sys.stdin.readline().split())
    sy, sx = map(int, sys.stdin.readline().split())
    gy, gx = map(int, sys.stdin.readline().split())
    sy -= 1; sx -=1; gy -= 1; gx -= 1
    maze = [sys.stdin.readline().rstrip() for _ in range(r)]
    queue = deque([(sy, sx)])
    dist = np.full((r, c), np.inf); dist[sy, sx] = 0
    while queue:
      y, x = queue.popleft()
      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:
        i += y; j += x
        if maze[i][j] == '#' or dist[i, j] != np.inf: continue 
        dist[i, j] = dist[y, x] + 1
        queue.append((i, j))
    print(int(dist[gy, gx]))
  
  def D(): pass 


class ABC008():
  def A():
    s, t = map(int, sys.stdin.readline().split())
    print(t-s+1)

  def B():
    n, *s = sys.stdin.read().split()
    res = defaultdict(int)
    for name in s: res[name] += 1
    print(sorted(res.items(), key=lambda x: x[1])[-1][0])

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    c = n - np.count_nonzero(a[:, None]%a, axis=1)
    print(np.sum((c+1)//2/c))
  
  def D(): pass

class ABC009():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((n+1)//2)

  def B():
    n, *a = map(int, sys.stdin.read().split())
    print(sorted(set(a))[-2])
    
  def C():
    n, k = map(int, sys.stdin.readline().split())
    s = list(sys.stdin.readline().rstrip())
    cost = [1]*n
    r = k
    for i in range(n-1):
      q = []
      for j in range(i+1, n):
        if s[j] < s[i] and cost[i]+cost[j] <= r:
          heappush(q, (s[j], cost[i]+cost[j], -j))
      if not q: continue
      _, c, j = heappop(q); j = -j 
      s[i], s[j] = s[j], s[i]
      r -= c 
      cost[i] = cost[j] = 0
    print(''.join(s))
      
  def D(): pass 


class ABC010():
  def A():
    print(sys.stdin.readline().rstrip()+'pp')
  def B():
    n, *a = map(int, sys.stdin.read().split())
    tot = 0
    for x in a:
      c = 0 
      while x%2==0 or x%3==2:
        x -= 1
        c += 1
      tot += c
    print(tot)

  def C():
    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())
    x, y = np.array(xy).reshape(-1, 2).T
    def dist(x1, y1, x2, y2):
      return np.sqrt((x2-x1)**2 + (y2-y1)**2)
    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'
    print(ans)

  def D(): pass 

class ABC011():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print(n%12+1)

  def B():
    s = sys.stdin.readline().rstrip() 
    print(s[0].upper()+s[1:].lower())

  def C():
    n, *ng = map(int, sys.stdin.read().split())
    ng = set(ng)
    if n in ng: print('NO')
    else:
      r = 100
      while n > 0:
        if r == 0: print('NO'); return
        for i in range(3, 0, -1):
          if (n-i) in ng: continue 
          n -= i
          r -= 1
          break 
        else: print('NO'); return 
      print('YES')

  def D(): pass 

class ABC040():
  def A():
    n, x = map(int, sys.stdin.readline().split())
    print(min(x-1, n-x))

  def B():
    n = int(sys.stdin.readline().rstrip())
    res = inf 
    for i in range(1, int(n**.5)+1):
      res = min(res, n//i-i+n%i)
    print(res)

  def C():
    n, *h = map(int, sys.stdin.read().split())
    h = [h[0]]+h
    cost = [None] * (n+1); cost[0] = cost[1] = 0
    for i in range(2, n+1):
      cost[i] = min(
        cost[i-2] + abs(h[i]-h[i-2]),
        cost[i-1] + abs(h[i]-h[i-1])
      )
    print(cost[n])

  def D(): pass


class ABC041():
  def A():
    s, i = sys.stdin.read().split()
    i = int(i)
    print(s[i-1])

  def B():
    a, b, c = map(int, sys.stdin.readline().split())
    ans = a * b % MOD * c % MOD 
    print(ans)

  def C():
    n, *a = map(int, sys.stdin.read().split())
    for i, h in sorted(enumerate(a), key=lambda x: -x[1]):
      print(i+1)

  def D():
    n, m, *xy = map(int, sys.stdin.read().split())
    *xy, = zip(*[iter(xy)]*2)
    edges = [0] * n 
    for x, y in xy:
      x -= 1; y -= 1
      edges[x] |= 1<<y
    comb = [None] * (1<<n); comb[0] = 1
    def count(edges, bit):
      if comb[bit] is not None: return comb[bit]
      comb[bit] = 0
      for i in range(n):
        if (bit>>i) & 1 and not edges[i]:
          nxt_bit = bit & ~(1<<i)
          nxt_edges = edges.copy() 
          for j in range(n):
            nxt_edges[j] &= ~(1<<i)
          cnt = count(nxt_edges, nxt_bit)
          comb[bit] += cnt
      return comb[bit]
    print(count(edges, (1<<n)-1))


class ABC042():
  def A():
    a = [int(x) for x in sys.stdin.readline().split()]
    c = Counter(a)
    print('YES' if c[5]==2 and c[7]==1 else 'NO')

  def B():
    n, l, *s = sys.stdin.read().split()
    print(''.join(sorted(s)))

  def C():
    n, k, *d = sys.stdin.read().split()
    l = len(n)
    ok = sorted(set(string.digits)-set(d))
    cand = [int(''.join(p)) for p in product(ok, repeat=l)] + [int(min(x for x in ok if x > '0')+min(ok)*l)]
    print(cand[bi_l(cand, int(n))])

  def D():
    h, w, a, b = map(int, sys.stdin.read().split())
    combinatorics = Combinatorics(n=2*10**5, mod=MOD, numpy=True)
    tot = combinatorics.mod_choose(h+w-2, h-1)
    i = np.arange(h-a, h)
    ng = np.sum(combinatorics.mod_choose(i+b-1, i) * combinatorics.mod_choose(h-i+w-b-2, h-1-i) % MOD)
    tot -= ng; tot %= MOD
    print(tot)


class ABC043():
  def A():
    n = int(sys.stdin.readline().rstrip())
    print((1+n)*n//2)

  def B():
    s = sys.stdin.readline().rstrip()
    t = ''
    for c in s:
      if c == 'B': t = t[:-1]
      else: t += c
    print(t)

  def C():
    n, *a = map(int, sys.stdin.read().split())
    a = np.array(a)
    x = np.around(a.sum()/n).astype(int)
    print(np.sum((a-x)**2))

  def D():
    s = sys.stdin.readline().rstrip()
    n = len(s)
    for i in range(n-1):
      if s[i] == s[i+1]:
        print(i+1, i+2); return 
    for i in range(n-2):
      if s[i] == s[i+2]:
        print(i+1, i+3); return 
    print(-1, -1)


class ABC170():
  def A():
    x = [int(x) for x in sys.stdin.readline().split()]
    for i in range(5):
      if x[i] != i+1:
        print(i+1)
        break

  def B():
    x, y = map(int, sys.stdin.readline().split())
    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')
      
  def C():
    x, n, *p = map(int, sys.stdin.read().split())
    a = list(set(range(102)) - set(p))
    a = [(abs(y-x), y) for y in a]
    print(sorted(a)[0][1])

  def D():
    n, *a = map(int, sys.stdin.read().split())
    cand = set(a)
    cnt = 0
    for x, c in sorted(Counter(a).items()):
      cnt += c == 1 and x in cand
      cand -= set(range(x*2, 10**6+1, x))
    print(cnt)

  def E():
    n, q = map(int, sys.stdin.readline().split())
    queue = [] 
    m = 2*10**5
    infants = [[] for _ in range(m)]
    highest_rate = [None] * m
    where = [None] * n
    rate = [None] * n

    def entry(i, k):
      where[i] = k
      while infants[k]:
        r, j = heappop(infants[k])
        if where[j] != k or j == i: continue 
        if rate[i] >= -r:
          highest_rate[k] = rate[i]
          heappush(queue, (rate[i], k, i))
        heappush(infants[k], (r, j))
        break
      else:
        highest_rate[k] = rate[i]
        heappush(queue, (rate[i], k, i))
      heappush(infants[k], (-rate[i], i))

    def transfer(i, k):
      now = where[i]
      while infants[now]:
        r, j = heappop(infants[now])
        if where[j] != now or j == i: continue
        if highest_rate[now] != -r:
          highest_rate[now] = -r
          heappush(queue, (-r, now, j))
        heappush(infants[now], (r, j))
        break
      else:
        highest_rate[now] = None
      entry(i, k)

    def inquire():
      while True:
        r, k, i = heappop(queue)
        if where[i] != k or r != highest_rate[k]: continue 
        heappush(queue, (r, k, i))
        return r

    for i in range(n):
      a, b = map(int, sys.stdin.readline().split())
      rate[i] = a 
      entry(i, b-1)
    for _ in range(q):
      c, d = map(int, sys.stdin.readline().split())
      transfer(c-1, d-1)
      print(inquire())
    
  def F(): pass 


class ABC171():
  def A():
    c = sys.stdin.readline().rstrip()
    print('A' if c < 'a' else 'a')

  def B():
    n, k, *p = map(int, sys.stdin.read().split())
    print(sum(sorted(p)[:k]))

  def C():
    n = int(sys.stdin.readline().rstrip())
    n -= 1
    l = 1
    while True:
      if n < pow(26, l):
        break 
      n -= pow(26, l)
      l += 1
    res = ''.join([chr(ord('a')+d) for d in NumberTheory.base_convert(n, 26)][::-1])
    res = 'a'*(l-len(res)) + res
    print(res)

  def D():
    n = int(sys.stdin.readline().rstrip())
    a = [int(x) for x in sys.stdin.readline().split()]
    s = sum(a)
    cnt = Counter(a)
    q = int(sys.stdin.readline().rstrip())
    for _ in range(q):
      b, c = map(int, sys.stdin.readline().split())
      s += (c-b)*cnt[b]
      print(s)
      cnt[c] += cnt[b]; cnt[b] = 0

  def E():
    n, *a = map(int, sys.stdin.read().split())
    s = 0
    for x in a: s ^= x 
    b = map(lambda x: x^s, a)
    print(*b, sep=' ')

  def F(): pass 


class ABC172():
  def A(): pass
  def B(): pass
  def C(): pass 
  def D(): pass 
  def E(): pass 
  def F(): pass 


class ABC173():
  def A():
    n = int(sys.stdin.readline().rstrip())
    charge = (n+999)//1000 * 1000 - n
    print(charge)

  def B():
    n, *s = sys.stdin.read().split() 
    c = Counter(s)
    for v in 'AC, WA, TLE, RE'.split(', '):
      print(f'{v} x {c[v]}')

  def C():
    h, w, k = map(int, sys.stdin.readline().split())
    c = [sys.stdin.readline().rstrip() for _ in range(h)]
    tot = 0
    for i in range(1<<h):
      for j in range(1<<w):
        cnt = 0
        for y in range(h):
          for x in range(w):
            if i>>y & 1 or j>>x & 1:
              continue 
            cnt += c[y][x] ==  '#'
        tot += cnt == k
    print(tot)

  def D():
    n, *a = map(int, sys.stdin.read().split())
    a.sort(reverse=True)
    res = a[0] + sum(a[1:1+(n-2)//2])*2 + a[1+(n-2)//2]*(n & 1)
    print(res)

  def E():
    MOD = 10**9+7
    n, k, *a = map(int, sys.stdin.read().split())
    minus = [x for x in a if x < 0]
    plus = [x for x in a if x > 0]
    if len(plus) + len(minus)//2*2 >= k: # plus 
      *minus, = map(abs, minus)
      minus.sort(reverse=True)
      plus.sort(reverse=True)
      cand = []
      if len(minus)&1: minus = minus[:-1]
      for i in range(0, len(minus)-1, 2):
        cand.append(minus[i]*minus[i+1]%MOD)
      if k & 1:
        res = plus[0]
        plus = plus[1:]
      else:
        res = 1
      if len(plus)&1: plus = plus[:-1]
      for i in range(0, len(plus)-1, 2):
        cand.append(plus[i]*plus[i+1]%MOD)
      cand.sort(reverse=True)
      for x in cand[:k//2]:
        res *= x
        res %= MOD 
      print(res)
    elif 0 in a:
      print(0)
    else:
      cand = sorted(map(abs, a))
      res = 1
      for i in range(k):
        res *= cand[i]
        res %= MOD
      res = MOD - res
      print(res)
      pass
  
  def F(): pass 


def __starting_point():
  # ABC040.D()
  ABC170.E()
__starting_point()

from collections import defaultdict
import heapq

INF_MAX = 10 ** 10

def set_remove(hp,dct,x):
    dct[x] += 1

def set_getmin(hp,dct):
    while True:
        if len(hp) == 0:
            return INF_MAX
        a = hp[0]
        if dct[a]:
            dct[a] -= 1
            heapq.heappop(hp)
        else:
            return a

N,Q = map(int,input().split())
A = [0]*N
B = [0]*N
C = [0]*Q
D = [0]*Q
E = [-1]*N
G = set()
hps = dict()
dcts = dict()
b,c,d,FROM,TO = 0,0,0,0,0
for i in range(N):
    A[i],b = map(int,input().split())
    b -= 1
    B[i] = b
    G.add(b)
for i in range(Q):
    c,d = map(int,input().split())
    c -= 1
    d -= 1
    C[i] = c
    D[i] = d
    G.add(d)

G.add(-1)
for g in G:
    hps[g] = list()
    dcts[g] = defaultdict(int)

for i in range(N):
    b = B[i]
    heapq.heappush(hps[b],-A[i])
    E[i] = b

hps[-1] = [-hps[b][0] for b in set(B)]
heapq.heapify(hps[-1])

for i in range(Q):
    c = C[i]
    FROM = E[c]
    TO = D[i]
    E[c] = TO
    c = A[c]
    # 転校元での処理
    b = set_getmin(hps[FROM],dcts[FROM])
    b *= -1
    if c == b:
        set_remove(hps[-1],dcts[-1],c)
        set_remove(hps[FROM],dcts[FROM],-c)
        d = set_getmin(hps[FROM],dcts[FROM])
        if d != INF_MAX:
            d *= -1
            heapq.heappush(hps[-1],d)
    else:
        set_remove(hps[FROM],dcts[FROM],-c)

    # 転校先での処理
    b = set_getmin(hps[TO],dcts[TO])
    if b != INF_MAX:
        b *= -1
        if c > b:
            set_remove(hps[-1],dcts[-1],b)
            heapq.heappush(hps[-1],c)
    else:
        heapq.heappush(hps[-1],c)
    heapq.heappush(hps[TO],-c)
    print(set_getmin(hps[-1],dcts[-1]))

import sys
from heapq import heapify, heappop, heappushpop, heappush

M = 2*10**5
input = sys.stdin.readline
N, Q = list(map(int, input().split()))
rates = [0] * N
wheres = [0] * N
kgs = [[(0, 0)] for _ in range(M)]
for i in range(N):
    a, b = list(map(int, input().split()))
    rates[i] = a
    wheres[i] = b-1
    heappush(kgs[b-1], (-a, i))
rankers = []
for kg in kgs:
    v = kg[0]
    if v[0] != 0:
        heappush(rankers, (-v[0], v[1], wheres[v[1]]))

def fetch_max(i):
    while True:
        v = kgs[i][0]
        if v[0] == 0 or wheres[v[1]] == i:
            return v
        heappop(kgs[i])

def fetch_min():
    while True:
        v = rankers[0]
        w = fetch_max(v[2])
        if w[0] != 0 and w[1] == v[1]:
            return v
        heappop(rankers)

def solve():
    for _ in range(Q):
        c, d = list(map(int, input().split()))
        ibkg, iakg = wheres[c-1], d-1
        wheres[c-1] = d-1
        heappush(kgs[iakg], (-rates[c-1], c-1))

        bef = fetch_max(ibkg)
        heappush(rankers, (-bef[0], bef[1], ibkg))

        aft = kgs[iakg][0]
        heappush(rankers, (-aft[0], aft[1], iakg))

        print((fetch_min()[0]))

def __starting_point():
    solve()

__starting_point()

from heapq import heappop, heappush

encode_kindy = lambda x, y: -((x << 18) + y)
decode_kindy = lambda x: (-x >> 18, -x & ((1 << 18) - 1))
encode_smarts = lambda x, y, z: ((x << 36) + (y << 18) + z)
decode_smarts_rate = lambda x: x >> 36


class DeletableHeapq:
    def __init__(self, *initial_values):
        self.size = 0
        self._set = set()
        self._heap = []

        if initial_values:
            for v in initial_values:
                self.push(v)

    @property
    def top(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        return self._heap[0]

    def pop(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        res = heappop(self._heap)
        self._set.discard(res)
        self.size -= 1
        return res

    def push(self, x):
        self.size += 1
        heappush(self._heap, x)
        self._set.add(x)

    def delete(self, x):
        self.size -= 1
        self._set.discard(x)


def main():
    N, _, *X = list(map(int, open(0).read().split()))
    AB, CD = X[: 2 * N], X[2 * N :]
    rate, belonging = [0] * (N + 1), [0] * (N + 1)
    kindy = [DeletableHeapq() for _ in range(200_001)]

    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):
        rate[i], belonging[i] = a, b
        kindy[b].push(encode_kindy(a, i))

    smart_infants = DeletableHeapq(
        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)
    )

    res = []
    for c, next_k in zip(*[iter(CD)] * 2):
        prev_k = belonging[c]
        belonging[c] = next_k

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))

        kindy[prev_k].delete(encode_kindy(rate[c], c))
        kindy[next_k].push(encode_kindy(rate[c], c))

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))

        res.append(decode_smarts_rate(smart_infants.top))

    print(("\n".join(map(str, res))))


def __starting_point():
    main()

__starting_point()

from heapq import heappop, heappush


class DeletableHeapq:
    """Deletable Heapq: A heapq supporting lazy deletion of values."""

    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:
        self.is_max_heap = is_max_heap
        self.size = 0
        self._set = set()
        self._heap = []

        if initial_values:
            for v in initial_values:
                self.push(v)

    @property
    def top(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        return self._heap[0] if not self.is_max_heap else -self._heap[0]

    def pop(self):
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        self.size -= 1
        res = heappop(self._heap)
        self._set.discard(res)
        return res if not self.is_max_heap else -res

    def push(self, value):
        if value is None:
            return
        if self.is_max_heap:
            value = -value
        if value in self._set:
            return
        self.size += 1
        heappush(self._heap, value)
        self._set.add(value)

    def delete(self, value):
        if value is None:
            return
        if self.is_max_heap:
            value = -value
        if value not in self._set:
            return
        self.size -= 1
        self._set.discard(value)


def main():
    # https://atcoder.jp/contests/abc170/tasks/abc170_e
    encode_kindy = lambda x, y: (x << 18) + y
    decode_kindy = lambda x: (x >> 18, x & ((1 << 18) - 1))
    encode_smarts = lambda x, y, z: (x << 36) + (y << 18) + z
    decode_smarts_rate = lambda x: x >> 36

    N, _, *X = list(map(int, open(0).read().split()))
    AB, CD = X[: 2 * N], X[2 * N :]
    rate, belonging = [0] * (N + 1), [0] * (N + 1)
    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]

    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):
        rate[i], belonging[i] = a, b
        kindy[b].push(encode_kindy(a, i))

    smart_infants = DeletableHeapq(
        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)
    )
    res = []
    for c, next_k in zip(*[iter(CD)] * 2):
        prev_k = belonging[c]
        belonging[c] = next_k

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))

        kindy[prev_k].delete(encode_kindy(rate[c], c))
        kindy[next_k].push(encode_kindy(rate[c], c))

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))

        res.append(decode_smarts_rate(smart_infants.top))

    print(("\n".join(map(str, res))))


def __starting_point():
    main()

__starting_point()


def main():
    import heapq
    import sys
    input = sys.stdin.readline
    
    N, Q = map(int, input().split())
    AB = [tuple(map(int, input().split())) for _ in range(N)]
    CD = [tuple(map(int, input().split())) for _ in range(Q)]

    maximum = 2*10**5

    B = [[] for _ in range(maximum)]
    member = [set() for _ in range(maximum)]
    belongs = [-1]*N

    for i,(a,b) in enumerate(AB):
        b -= 1
        heapq.heappush(B[b], (-a,i))
        member[b].add(i)
        belongs[i] = b


    maximum_list = []
    for i,b in enumerate(B):
        if len(b) > 0:
            heapq.heappush(maximum_list, (-b[0][0], i))
    
    Inf = [0] * maximum
    for c, d in CD:
        c -= 1
        d -= 1
        before = belongs[c]
        belongs[c] = d
        member[before].remove(c)
        member[d].add(c)
        for i in Inf:
            if len(B[before]) <= 0:
                break
            if B[before][0][1] in member[before]:
                break
            else:
                heapq.heappop(B[before])
        
        if len(B[before]) > 0:
            heapq.heappush(maximum_list, (-B[before][0][0], before))
        
        heapq.heappush(B[d], (-AB[c][0], c))
        heapq.heappush(maximum_list, (AB[c][0], d))
        for i in Inf:
            minmum, num = maximum_list[0]
            if len(B[num]) == 0 or -B[num][0][0] != minmum:
                heapq.heappop(maximum_list)
            else:
                print(minmum)
                break

main()

import sys
readline = sys.stdin.readline
from collections import defaultdict as ddict
import heapq as hq

N,Q = list(map(int,readline().split()))

# 園児の情報[レート, 現在の園]をindexで取得できるように管理する
# 転園したら、"現在の園"を常に更新する
# 全ての園について、(-rate, 園児のID)で園児情報を持つ
# heapqで最強の園児(rate * -1)を確認できるようにする（popしない）
# 取り出した園児の所属を調べて、現在の所属と異なるようであれば破棄（転園済）
# 破棄するときに初めてpopする

# 全体については、(最強園児のレート, 園の番号)を管理するheapqを持つ
# 転園があると最強レートが変わり得るため、毎回の処理ごとに
# ・転園元の園の最新の(最強園児のレート, 園の番号)
# ・転園先の園の最新の(最強園児のレート, 園の番号)
# をheapqに格納する
# 先頭の園について、園の最強レートと照合して（正負に注意）、
# 一致しなければ情報が古いので破棄(pop)

NN = 2 * (10 ** 5)
#NN = 4
infants = [None] * (N + 1)
kinda = [[] for i in range(NN + 1)] # (-1 * レート,園児ID)
for i in range(N):
  a,b = list(map(int,readline().split()))
  infants[i + 1] = [a,b]
  hq.heappush(kinda[b], (-a, i + 1))

#print("kinda",kinda)
# 全体の最強園児情報　（最強園児のレート, 園の番号）
all_kinda = [] # (レート, 園の番号)
# 最初に、現在の最強園児を全て格納する
for i in range(len(kinda)):
  if kinda[i]:
    hq.heappush(all_kinda, ((-1) * (kinda[i][0][0]), i))
    
#print("all_kinda",all_kinda)
def search_max_rate_from_kinda(x): # ある園の最強レートを正の数で返す
  q = kinda[x]
  while q:
    rate, infant_id = q[0] # レートは負の数
    # 取り出した園児が、現在もxに所属しているかを調べる
    if infants[infant_id][1] != x:
      # 転園済
      hq.heappop(q)
    else:
      # 現在も所属している
      return -rate # 正負を反転して返す
  return -1 # 全員が転園済みだった場合
  
for i in range(Q):
  target, new_kinda_id = list(map(int,readline().split())) # 園児, 転園先
  # 現在の園とレートを調べる
  rate, old_kinda_id = infants[target]
  # 現在の園を最新に保つ
  infants[target][1] = new_kinda_id
  # 転園先に園児を追加する
  hq.heappush(kinda[new_kinda_id],(-rate, target))
  
  # 転園元の園の最強レートを取り出し、全体のキューに追加
  old_kinda_rate = search_max_rate_from_kinda(old_kinda_id)
  if old_kinda_rate != -1:
    hq.heappush(all_kinda, (old_kinda_rate, old_kinda_id))
  
  # 転園先の園の最強レートを取り出し、全体のキューに追加
  new_kinda_rate = search_max_rate_from_kinda(new_kinda_id)
  if new_kinda_rate != -1:
    hq.heappush(all_kinda, (new_kinda_rate, new_kinda_id))
    
  #print("i",i,"kinda",kinda)
  #print("i",i,"all_kinda",all_kinda)
  # 全体のキューの先頭にいる(最弱レート, 園の番号)について、
  # その園の最強園児と一致していれば出力する
  while all_kinda:
    weakest_rate, kinda_id = all_kinda[0]
    current_max_rate = search_max_rate_from_kinda(kinda_id)
    if weakest_rate != current_max_rate:
      # 情報が古い
      hq.heappop(all_kinda)
    else:
      print(weakest_rate)
      break


import heapq
import sys
input = sys.stdin.readline

N, Q = list(map(int, input().split()))
AB = [tuple(map(int, input().split())) for _ in range(N)]
CD = [tuple(map(int, input().split())) for _ in range(Q)]
H = 2*10**5 # 幼稚園

INF = 10**18
rates = [[] for _ in range(H)]
members = [set() for _ in range(H)]
belongs = [-1]*N
for i,(a,b) in enumerate(AB):
    b -= 1
    heapq.heappush(rates[b], (-a,i))
    members[b].add(i)
    belongs[i] = b

mxrates = []
for num,r in enumerate(rates):
    if len(r) > 0:
        heapq.heappush(mxrates, (-r[0][0], num)) # 幼稚園ごとの最大値をいれる

for c,d in CD:
    c, d = c-1, d-1
    old = belongs[c]
    belongs[c] = d
    members[old].remove(c)
    members[d].add(c)
    # 転園元の最大値を最新化する
    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:
        heapq.heappop(rates[old])
    # 最新化された転園元から改めて取得
    if len(rates[old]) > 0:
        heapq.heappush(mxrates, (-rates[old][0][0], old))
    # 転園先に追加
    heapq.heappush(rates[d], (-AB[c][0], c))
    heapq.heappush(mxrates, (AB[c][0], d))
    while mxrates:
        rate, num = mxrates[0]
        # mxratesの最小が最新ではない場合
        if len(rates[num]) == 0 or -rates[num][0][0] != rate:
            heapq.heappop(mxrates)
        else:
            print(rate)
            break


import heapq
N,Q=map(int,input().split())
M=2*(10**5)
belong=[]
rate=[]
garden=[[]for _ in range(M)]
for c in range(N):
    A,B=map(int,input().split())
    B-=1
    belong.append(B)
    rate.append(A)
    heapq.heappush(garden[B],(-A,c))
    
strong=[]

for i in range(M):
    if garden[i]:
        A,c=garden[i][0]
        heapq.heappush(strong,(-A,c,i))
        
for i in range(Q):
    C,D=map(int,input().split())
    C-=1
    D-=1
    now=belong[C]
    belong[C]=D
    
    while garden[now]:
        A,c=garden[now][0]
        if belong[c]!=now:
            heapq.heappop(garden[now])
        else:
            heapq.heappush(strong,(-A,c,now))
            break
            
    heapq.heappush(garden[D],(-rate[C],C))
    while garden[D]:
        A,c=garden[D][0]
        heapq.heappush(strong,(-A,c,D))
        break
    
    while strong:
        A,c,d=strong[0]
        if belong[c]!=d or garden[d][0][1]!=c:
            heapq.heappop(strong)
        else:
            print(A)
            break

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

def solve():
    import heapq

    M = 2*(10**5)
    N, Q = list(map(int, input().split()))
    As, Bs = [], []
    yochien = [list() for _ in range(M)]  # 幼稚園
    for i in range(N):
        a, b = list(map(int, input().split()))
        b = b - 1
        As.append(a), Bs.append(b)
        heapq.heappush(yochien[b], (-a, i))  # 幼稚園bに、幼児iのレートaを、プライオリティキューで持つ。（先頭に最も大きいレートの幼児がくるようにする）

    # 各幼稚園のトップコーダー連中の幼児情報を、プライオリティキューtopにぶちこむ。
    # 幼児情報は(レート, 幼児, 所属幼稚園)の形式でぶちこむ
    # すなわち、top[0]にはトップコーダー連中の最低レートの幼児情報が入っている。
    # 「トップコーダー連中の最低レート幼児」は長いので、以降「平等レート幼児」と呼ぶ。
    top = []
    for m in range(M):
        if yochien[m]:
            heapq.heappush(top, (-yochien[m][0][0], yochien[m][0][1], m))

    # クエリを処理する
    for _ in range(Q):
        # 幼児cを幼稚園dに転園させたい
        c, d = list(map(int, input().split()))
        c, d = c-1, d-1

        before = Bs[c]  # 転園前の幼稚園
        Bs[c] = d

        # 幼児cを幼稚園dに転園する
        heapq.heappush(yochien[d], (-As[c], c))

        if yochien[d][0][1] == c:
            # 幼児cが転園先の幼稚園dでトップコーダーになったならば、トップを更新する
            heapq.heappush(top, (As[c], c, d))

        flag = False  # 転園前の幼稚園のトップコーダーが変わったか？
        while yochien[before] and Bs[yochien[before][0][1]] != before:
            # 「転園前の幼稚園が空じゃない」、かつ、「転園前の幼稚園のトップコーダーが変わった」ならば、
            # 転園前の幼稚園のトップコーダーを削除する
            heapq.heappop(yochien[before])
            flag = True

        if flag and yochien[before]:
            # 転園前の幼稚園のトップコーダーが変わってしまい、まだ転園前の幼稚園に幼児が存在するならば、
            # 転園前の幼稚園のトップコーダーはその幼児になる
            heapq.heappush(top, (-yochien[before][0][0], yochien[before][0][1], before))

        while not yochien[top[0][2]] or yochien[top[0][2]][0][1] != top[0][1]:
            # 「平等レート幼児の所属幼稚園が空じゃない」、または、「平等レート幼児が変わった」ならば、
            # 平等レート幼児を更新する
            heapq.heappop(top)

        # 平等さ（平等レート幼児のレート値）を表示する
        print((top[0][0]))


def __starting_point():
    solve()

__starting_point()

import sys
import  math
import fractions
import heapq
import copy
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))


class My_heapavi():
    def __init__(self):
        self.p = list()
        self.q = list()
        self.p2 = list()
        self.q2 = list()

    def insert(self,x):
        heapq.heappush(self.p, x)
        heapq.heappush(self.p2,-x)
        return

    def erase(self,x):
        heapq.heappush(self.q, x)
        heapq.heappush(self.q2,-x)
        return

    def minimum(self):
        while self.q and self.p[0] == self.q[0]:
            heapq.heappop(self.p)
            heapq.heappop(self.q)
        return self.p[0]
    
    def maximum(self):
        while self.q2 and self.p2[0] == self.q2[0]:
            heapq.heappop(self.p2)
            heapq.heappop(self.q2)
        return -self.p2[0]

    def size(self):
        return len(self.p)-len(self.q)



s=[My_heapavi() for i in range(200005)]
maxs=My_heapavi()


def getmax(i):
    if(s[i].size()==0):
        return -1 
    return s[i].maximum()

def addYouchien(i):
    x=getmax(i)
    if(x==-1):
        return
    maxs.insert(x)

def delYouchien(i):
    x=getmax(i)
    if(x==-1):
        return
    maxs.erase(x)

 
def addEnji(i,x):
    delYouchien(i)
    s[i].insert(x)
    addYouchien(i)


def delEnji(i,x):
    delYouchien(i)
    s[i].erase(x)
    addYouchien(i)

N,Q=nm()
a=[0 for i in range(200005)]
b=[0 for i in range(200005)]

for i in range(N):
    a[i],b[i]=nm()
    addEnji(b[i],a[i])

for i in range(Q):
    c,d=nm()
    c-=1
    delEnji(b[c],a[c])
    b[c]=d
    addEnji(b[c],a[c])
    print(maxs.minimum())

import sys
# import math
# import bisect
# import numpy as np
# from decimal import Decimal
# from numba import njit, i8, u1, b1 #JIT compiler
# from itertools import combinations, product
# from collections import Counter, deque, defaultdict

# sys.setrecursionlimit(10 ** 6)
MOD = 10 ** 9 + 7
INF = 10 ** 9
PI = 3.14159265358979323846

def read_str():      return sys.stdin.readline().strip()
def read_int():      return int(sys.stdin.readline().strip())
def read_ints():     return map(int, sys.stdin.readline().strip().split())
def read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())
def read_str_list(): return list(sys.stdin.readline().strip().split())
def read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))
def GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)
def LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)

from heapq import heappop, heappush
def Main():
    n, q = read_ints()
    num = 2 * (10 ** 5)
    kindergarten = [[] for _ in range(num)]
    rating = [0] * n
    now = [0] * n

    for i in range(n):
        a, b = read_ints()
        heappush(kindergarten[~-b], (-a, i))
        rating[i] = a
        now[i] = ~-b

    ranking = []
    for j in range(num):
        if kindergarten[j]:
            a, i = kindergarten[j][0]
            heappush(ranking, (-a, i))
    
    for _ in range(q):
        c, d = read_ints()
        last = now[~-c]
        now[~-c] = ~-d
        heappush(kindergarten[~-d], (-rating[~-c], ~-c))

        while kindergarten[last] and now[kindergarten[last][0][1]] != last:
            heappop(kindergarten[last])
        while kindergarten[~-d] and now[kindergarten[~-d][0][1]] != ~-d:
            heappop(kindergarten[~-d])

        if kindergarten[last]:
            a, i = kindergarten[last][0]
            heappush(ranking, (-a, i))
        if kindergarten[~-d]:
            a, i = kindergarten[~-d][0]
            heappush(ranking, (-a, i))

        while ranking and kindergarten[now[ranking[0][1]]][0][1] != ranking[0][1]:
            heappop(ranking)
        
        print(ranking[0][0])

def __starting_point():
    Main()
__starting_point()

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

import heapq
from collections import defaultdict

def remove(hq, belongs, maxs, pd):
  while hq:
    if belongs[hq[0][1]] != pd:
      heapq.heappop(hq)
    else:
      heapq.heappush(maxs, (-hq[0][0], hq[0][1], pd))
      break

def main():
  n, q = list(map(int, input().strip().split()))
  rates = defaultdict(list)
  id2rate = [0] * n
  belongs = [0] * n
  for i in range(n):
    a, b = list(map(int, input().strip().split()))
    b -= 1
    rates[b].append((-a, i))
    belongs[i] = b
    id2rate[i] = a
    
  maxs = []
  for k in list(rates.keys()):
    heapq.heapify(rates[k])
    maxs.append((-rates[k][0][0], rates[k][0][1], k))
  heapq.heapify(maxs)

  for _ in range(q):
    c, d = list(map(int, input().strip().split()))
    c -= 1
    d -= 1

    pd = belongs[c]
    belongs[c] = d
    remove(rates[pd], belongs, maxs, pd)
        
    heapq.heappush(rates[d], (-id2rate[c], c))    
    remove(rates[d], belongs, maxs, d)
    heapq.heappush(maxs, (-rates[d][0][0], rates[d][0][1], d))
    
    while maxs:
      if belongs[maxs[0][1]] != maxs[0][2] or rates[maxs[0][2]][0][1] != maxs[0][1]:
        heapq.heappop(maxs)
      else:
        print((maxs[0][0]))
        break
      

def __starting_point():
  main()


__starting_point()

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def main():
    N, Q = lr()
    top = []
    left_top = []
    infants = [[] for _ in range(2*10**5+1)]  # 1-indexed
    left = [[] for _ in range(2*10**5+1)]
    dic = defaultdict(tuple)
    for i in range(1, N+1):
        a, b = lr()
        heappush(infants[b], (-a, i))
        dic[i] = (a, b)

    for i in range(1, 2*10**5+1):
        if infants[i]:
            rate, id = infants[i][0]
            heappush(top, (-rate, id))

    for _ in range(Q):
        c, next = lr()
        r, prev = dic[c]
        dic[c] = (r, next)
        r3, prev_top = infants[prev][0]
        heappush(left_top, (-r3, prev_top))
        heappush(left[prev], (-r, c))
        while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:
            heappop(infants[prev])
            heappop(left[prev])
        if infants[prev]:
            rate, id = infants[prev][0]
            heappush(top, (-rate, id))
        if infants[next]:
            heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # idをpush
        heappush(infants[next], (-r, c))  # tupleでpush
        while left[next] and infants[next][0][1] == left[next][0][1]:
            heappop(infants[next])
            heappop(left[next])
        r2, id2 = infants[next][0]
        heappush(top, (-r2, id2))
        while left_top and top[0][1] == left_top[0][1]:
            heappop(top); heappop(left_top)
        answer = top[0][0]
        print(answer)

main()

import sys
readline = sys.stdin.readline

import heapq as hq

N,Q = list(map(int,readline().split()))
NN = 2 * (10 ** 5)

# (レート, 所属園)
infants = [None] * (N + 1)
# (最強園児, 園児番号)
kinda = [[] for i in range(NN + 1)]
for i in range(N):
  a,b = list(map(int,readline().split()))
  infants[i + 1] = [a,b]
  hq.heappush(kinda[b], (-a, i + 1))

# (最弱園児, 園の番号)
all_kinda = []
for i in range(len(kinda)):
  if kinda[i]:
    hq.heappush(all_kinda, (-kinda[i][0][0], i))
  
def get_max_rate(x): # 園の最強レートを取り出す
  q = kinda[x]
  while q:
    rate, ind = q[0]
    if infants[ind][1] != x:
      hq.heappop(q)
      continue
    return -rate
  return -1
  
for i in range(Q):
  ind,next_kinda_id = list(map(int,readline().split()))
  rate,old_kinda_id = infants[ind]
  infants[ind][1] = next_kinda_id
  hq.heappush(kinda[next_kinda_id],(-rate, ind))
  
  for target_kinda_id in (old_kinda_id,next_kinda_id):
    target_kinda_max_rate = get_max_rate(target_kinda_id)
    if target_kinda_max_rate != -1:
      hq.heappush(all_kinda, (target_kinda_max_rate, target_kinda_id))

  while all_kinda:
    rate, kinda_id = all_kinda[0]
    if rate != get_max_rate(kinda_id):
      hq.heappop(all_kinda)
      continue
    print(rate)
    break


import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    M = 2 * 10 ** 5
    p = [[] for _ in range(M)]
    p_del = [[] for _ in range(M)]
    q = []
    q_del = []

    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, readline().split())
        A[i] = a
        B[i] = b - 1
        heappush(p[b - 1], -a)

    for i in range(M):
        if p[i]:
            heappush(q, -p[i][0])

    CD = map(int, read().split())
    ans = [0] * Q
    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):
        c -= 1
        d -= 1

        b, B[c] = B[c], d

        max_prev = set()
        max_prev.add(-p[b][0])
        if p[d]:
            max_prev.add(-p[d][0])

        heappush(p_del[b], -A[c])
        heappush(p[d], -A[c])

        while p_del[b] and p[b][0] == p_del[b][0]:
            heappop(p[b])
            heappop(p_del[b])

        max_current = set()
        max_current.add(-p[d][0])
        if p[b]:
            max_current.add(-p[b][0])

        for rating in max_prev - max_current:
            heappush(q_del, rating)

        for rating in max_current - max_prev:
            heappush(q, rating)

        while q_del and q[0] == q_del[0]:
            heappop(q)
            heappop(q_del)

        ans[i] = q[0]

    print(*ans, sep='\n')

    return


def __starting_point():
    main()

__starting_point()

from heapq import heappop, heappush

MAX = 2*10**5
n, q = list(map(int, input().split()))
ab = []
k_in = [[] for _ in range(MAX)]
k_out = [[] for _ in range(MAX)]
for i in range(n):
    a, b = list(map(int, input().split()))
    b -= 1
    ab.append([a, b])
    heappush(k_in[b], -a)

k_max_in = []
k_max_out = []
for i in range(MAX):
    if k := k_in[i]:
        heappush(k_max_in, -k[0])

for _ in range(q):
    c, d = [int(x)-1 for x in input().split()]
    idx = ab[c][1]
    heappush(k_max_out, -k_in[idx][0])
    if k_in[d]:
        heappush(k_max_out, -k_in[d][0])
    while k_max_out and k_max_in[0] == k_max_out[0]:
        heappop(k_max_in)
        heappop(k_max_out)
    heappush(k_out[idx], -ab[c][0])
    while k_out[idx] and k_in[idx][0] == k_out[idx][0]:
        heappop(k_in[idx])
        heappop(k_out[idx])

    heappush(k_in[d], -ab[c][0])
    if k_in[idx]:
        heappush(k_max_in, -k_in[idx][0])
    heappush(k_max_in, -k_in[d][0])
    ab[c][1] = d

    print((k_max_in[0]))


import heapq

N,Q = map(int,input().split())
ST = [0]*(N+1) #strong,belong
kid_Add = [[] for _ in range(2*10**5+1)] #infant who is in this kinder at least one time
kid_Del = [[] for _ in range(2*10**5+1)] #infant who is no longer in this kinder
max_Add = [] #highest rate
max_Del = [] #highest rate deleted

heapq.heapify(kid_Add)
heapq.heapify(kid_Del)
heapq.heapify(max_Add)
heapq.heapify(max_Del)

for i in range(N):
    A,B = map(int,input().split())
    heapq.heappush(kid_Add[B],-1*A)
    ST[i+1] = (A,B)

for i in range(2*10**5+1):
    if kid_Add[i]:heapq.heappush(max_Add,-1*kid_Add[i][0])

def deleteHeap(x,y):
    while y and x[0] == y[0]:
        heapq.heappop(x)
        heapq.heappop(y)

for j in range(Q):
    C,D = map(int,input().split())
    s, t = ST[C]
    if not kid_Add[D]:
        Ne_S = 0
    else:
        Ne_S = kid_Add[D][0]
    Ol_S = kid_Add[t][0]
    heapq.heappush(kid_Add[D],-1*s)
    heapq.heappush(kid_Del[t],-1*s)
    deleteHeap(kid_Add[t],kid_Del[t])

    if Ne_S > -1*s:
        heapq.heappush(max_Add,s)
        if Ne_S != 0 : heapq.heappush(max_Del,-1*Ne_S)
    if Ol_S == -1*s:
        heapq.heappush(max_Del,s)
        if kid_Add[t]:heapq.heappush(max_Add,-1*kid_Add[t][0])
        
    deleteHeap(max_Add,max_Del)
    print(max_Add[0])
    ST[C] = (s,D)

from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline

n, q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(q)]

m = 2 * 10 ** 5
thq = []
top = defaultdict(int)
topcnt = defaultdict(int)
rhq = [[] for _ in range(m + 1)]
rate = [defaultdict(int) for _ in range(m + 1)]
for a, b in ab:
    top[b] = max(top[b], a)
    rate[b][a] += 1
    heapq.heappush(rhq[b], -a)
for num in list(top.values()):
    heapq.heappush(thq, num)
    topcnt[num] += 1

for c, d in cd:
    a, b = ab[c - 1]
    ab[c - 1][1] = d
    rate[b][a] -= 1
    if rate[b][a] == 0:
        del rate[b][a]
    topcnt[top[b]] -= 1
    if topcnt[top[b]] == 0:
        del topcnt[top[b]]
    del top[b]
    if len(rate[b]) > 0:
        top[b] = -heapq.heappop(rhq[b])
        while top[b] not in rate[b]:
            top[b] = -heapq.heappop(rhq[b])
        heapq.heappush(rhq[b], -top[b])
        heapq.heappush(thq, top[b])
        topcnt[top[b]] += 1

    rate[d][a] += 1
    heapq.heappush(rhq[d], -a)
    if a > top[d]:
        if top[d] > 0:
            topcnt[top[d]] -= 1
            if topcnt[top[d]] == 0:
                del topcnt[top[d]]
        top[d] = a
        topcnt[top[d]] += 1
    heapq.heappush(thq, top[d])

    ans = heapq.heappop(thq)
    while ans not in topcnt:
        ans = heapq.heappop(thq)
    heapq.heappush(thq, ans)
    print(ans)


# coding: utf-8
import sys
# from operator import itemgetter
sysread = sys.stdin.readline
read = sys.stdin.read
sys.setrecursionlimit(10 ** 7)
from heapq import heappop, heappush
#from collections import OrderedDict, defaultdict
#import math
#from itertools import product, accumulate, combinations, product
#import bisect# lower_bound etc
#import numpy as np
# from copy import deepcopy
#from collections import deque
#import numba

def binary_search(arr, operator='max'):
    _cri = {'max':max, 'min':min}
    ope = _cri[operator]
    dic = {0: arr}
    dep = 0
    while True:
        _arr = dic[dep]
        if len(_arr) == 1:break
        dic[dep+1] = []
        for i in range(0, len(_arr), 2):
            if i == len(_arr) - 1:
                dic[dep+1].append(_arr[i])
                continue
            dic[dep+1].append(ope(_arr[i], _arr[i+1]))
        dep += 1
    return _arr[0]

def eval_max(dic):
    tmp = binary_search(list(dic.keys()))
    return tmp

def run():
    N, Q = list(map(int, input().split()))
    rate = [0]
    child = [0]
    G = 2 * 10 ** 5
    group = [[] for _ in range(G + 1)]
    stocks = [[] for _ in range(G + 1)]
    for i in range(1, N+1):
        a, b = list(map(int, sysread().split()))
        rate.append(a)
        child.append(b)
        heappush(group[b], -a)

    max_vals = []
    max_stocks = []
    for i in range(1, G + 1):
        if len(group[i]) > 0:
            heappush(max_vals, -group[i][0])

    for i in range(Q):
        c,d = list(map(int, sysread().split()))
        pre_g = child[c]
        heappush(max_stocks, -group[pre_g][0])
        heappush(stocks[pre_g], -rate[c])
        while group[pre_g] and stocks[pre_g]:
            if group[pre_g][0] == stocks[pre_g][0]:
                heappop(stocks[pre_g])
                heappop(group[pre_g])
            else:
                break
        if group[pre_g]:
            heappush(max_vals, -group[pre_g][0])

        if group[d]:
            heappush(max_stocks, -group[d][0])
        heappush(group[d], -rate[c])
        heappush(max_vals, -group[d][0])


        while max_vals and max_stocks:
            if max_vals[0] == max_stocks[0]:
                heappop(max_vals)
                heappop(max_stocks)
            else:
                break

        child[c] = d

        print((max_vals[0]))



def __starting_point():
    run()


__starting_point()

import heapq


class DeletableHeap:
  def __init__(self, reversed=False, debug=False):
    self.heap = []
    self.removed = {}
    self.reversed = reversed  # get the max if True
    self.factor = -1 if reversed else 1
    self.debug = debug
  
  def push(self,x):
#    if self.debug: print('push', x, self.heap, self.removed)
    heapq.heappush(self.heap, x * self.factor)
  
  def pop(self):
#    if self.debug: print('pop', self.heap, self.removed)
    while self.heap:
      a = heapq.heappop(self.heap) * self.factor
      if a in self.removed and self.removed[a]:
        self.removed[a] -= 1
        if self.removed[a] == 0:
          del self.removed[a]
      else:
 #       if self.debug: print(a)
        return a

  def peek(self):
 #   if self.debug: print('peek', self.heap, self.removed)
    while self.heap:
      a = self.heap[0] * self.factor
      if a in self.removed and self.removed[a]:
        self.removed[a] -= 1
        if self.removed[a] == 0:
          del self.removed[a]
        heapq.heappop(self.heap)
      else:
 #       if self.debug: print(a)
        return a

  def remove(self,x):
  #  if self.debug: print('remove', x, self.heap, self.removed)
    if x not in self.removed:
      self.removed[x] = 0
    self.removed[x] += 1
    
N, Q = list(map(int, input().split()))

KG = [DeletableHeap(reversed=True) for _ in range(2*10**5)]
B = []
A = []
for _ in range(N):
  a, b = list(map(int, input().split()))
  b -= 1
  KG[b].push(a)
  B.append(b)
  A.append(a)

rates = DeletableHeap(debug=False)
for kg in KG:
  if kg.peek() is not None:
    rates.push(kg.peek())
#print(rates.heap, rates.removed)
    
for _ in range(Q):
#  print('######')
  c, d = list(map(int, input().split()))
  c -= 1
  d -= 1
  # c is at B[c]
  b = B[c]
  B[c] = d
  a = A[c] # rate
  # c moves from b to d
  rates.remove(KG[b].peek())
  KG[b].remove(a)
  if KG[b].peek() is not None:
    rates.push(KG[b].peek())
  
  if KG[d].peek() is not None:
    rates.remove(KG[d].peek())
  KG[d].push(a)
  rates.push(KG[d].peek())
  #print(rates.heap, rates.removed)
  print((rates.peek()))
  
 # for i in range(10):
 #   print('kg', i, KG[i].heap, KG[i].removed)




import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    M = 2 * 10 ** 5
    hq1 = [[] for _ in range(M)]
    hq2 = [[] for _ in range(M)]
    hq_ans1 = []
    hq_ans2 = []

    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, readline().split())
        A[i] = a
        B[i] = b - 1
        heappush(hq1[b - 1], -a)

    for i in range(M):
        if hq1[i]:
            heappush(hq_ans1, -hq1[i][0])

    CD = map(int, read().split())
    ans = [0] * Q
    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):
        c -= 1
        d -= 1

        b = B[c]
        B[c] = d

        max_from_prev = -hq1[b][0]
        if hq1[d]:
            max_to_prev = -hq1[d][0]
        else:
            max_to_prev = None

        heappush(hq2[b], -A[c])
        heappush(hq1[d], -A[c])

        while hq2[b] and hq1[b][0] == hq2[b][0]:
            heappop(hq1[b])
            heappop(hq2[b])

        if hq1[b]:
            max_from = -hq1[b][0]
        else:
            max_from = None
        max_to = -hq1[d][0]

        if max_from_prev != max_from:
            heappush(hq_ans2, max_from_prev)
            if max_from:
                heappush(hq_ans1, max_from)

        if max_to_prev != max_to:
            if max_to_prev:
                heappush(hq_ans2, max_to_prev)
            heappush(hq_ans1, max_to)

        while hq_ans2 and hq_ans1[0] == hq_ans2[0]:
            heappop(hq_ans1)
            heappop(hq_ans2)

        ans[i] = hq_ans1[0]

    print(*ans, sep='\n')

    return


def __starting_point():
    main()

__starting_point()

# -*- coding: utf-8 -*-
import heapq

N,Q = list(map(int, input().rstrip().split()))
AB_list = [list(map(int, input().rstrip().split())) for i in range(N)]
CD_list = [list(map(int, input().rstrip().split())) for i in range(Q)]
#-----

K = [ [] for _ in range(2*10**5) ]  # kindergarten
K_deleted = [ [] for _ in range(2*10**5) ]

max_K = []
max_K_deleted = []


for a,b in AB_list:
    heapq.heappush(K[b-1], -a)

for member in K:
    if member:
        heapq.heappush( max_K, -member[0] )


for c,d in CD_list:
    c_rate = AB_list[c-1][0]
    c_prev = AB_list[c-1][1]
    
    
    departure_prev_max = K[c_prev-1][0]
    
    if K[d-1]:
        destination_prev_max = K[d-1][0]
    else:
        destination_prev_max = None
    
    
    # Delete c from current position
    heapq.heappush( K_deleted[c_prev-1], -c_rate )
    
    # Add c to Destination(next position)
    AB_list[c-1][1] = d
    heapq.heappush(K[d-1], -c_rate)
    
    
    # check HeapQueue of current and destination
    for i in [c_prev, d]:
        while K_deleted[i-1] and (K[i-1][0] == K_deleted[i-1][0]):
            heapq.heappop(K[i-1])
            heapq.heappop(K_deleted[i-1])
    
    
    # check max-rank at departure.
    if (not K[c_prev-1]):
        heapq.heappush(max_K_deleted, -departure_prev_max)
    
    elif departure_prev_max != K[c_prev-1][0]:
        heapq.heappush(max_K_deleted, -departure_prev_max)
        heapq.heappush(max_K, -K[c_prev-1][0])
    
    
    # check max-rank at destination.
    if destination_prev_max != K[d-1][0]:
        if destination_prev_max:
            heapq.heappush(max_K_deleted, -destination_prev_max)
        
        heapq.heappush(max_K, -K[d-1][0])
    
    
    # check min-value among kindergarten
    while max_K_deleted and (max_K[0] == max_K_deleted[0]):
        heapq.heappop(max_K)
        heapq.heappop(max_K_deleted)
    
    
    print((max_K[0]))


import sys
from heapq import heappush, heappop

read = sys.stdin.read
readline = sys.stdin.readline
readlines = sys.stdin.readlines
sys.setrecursionlimit(10 ** 9)
INF = 1 << 60
MOD = 1000000007


def main():
    N, Q = map(int, readline().split())
    M = 2 * 10 ** 5
    hq1 = [[] for _ in range(M)]
    hq2 = [[] for _ in range(M)]
    hq_ans1 = []
    hq_ans2 = []

    A = [0] * N
    B = [0] * N
    for i in range(N):
        a, b = map(int, readline().split())
        A[i] = a
        B[i] = b - 1
        heappush(hq1[b - 1], -a)

    for i in range(M):
        if hq1[i]:
            heappush(hq_ans1, -hq1[i][0])

    CD = map(int, read().split())
    ans = [0] * Q
    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):
        c -= 1
        d -= 1

        b = B[c]
        B[c] = d

        max_from_prev = -hq1[b][0]
        if hq1[d]:
            max_to_prev = -hq1[d][0]
        else:
            max_to_prev = None

        heappush(hq2[b], -A[c])
        heappush(hq1[d], -A[c])

        while hq2[b] and hq1[b][0] == hq2[b][0]:
            heappop(hq1[b])
            heappop(hq2[b])

        if hq1[b]:
            max_from = -hq1[b][0]
        else:
            max_from = None
        max_to = -hq1[d][0]

        if max_from_prev != max_from:
            heappush(hq_ans2, max_from_prev)
            if max_from:
                heappush(hq_ans1, max_from)

        if max_to_prev != max_to:
            if max_to_prev:
                heappush(hq_ans2, max_to_prev)
            heappush(hq_ans1, max_to)

        while hq_ans2 and hq_ans1[0] == hq_ans2[0]:
            heappop(hq_ans1)
            heappop(hq_ans2)

        ans[i] = hq_ans1[0]

    print(*ans, sep='\n')

    return


def __starting_point():
    main()

__starting_point()

import sys
import heapq

sys.setrecursionlimit(10 ** 8)

input = sys.stdin.readline


def main():
    N, Q = [int(x) for x in input().split()]

    hsize = 2 * 10 ** 5 + 1

    h = [[] for _ in range(hsize)]

    # 園児が現在所属している幼稚園を保存
    C = [0] * N
    A = []
    for i in range(N):
        a, b = [int(x) for x in input().split()]
        A.append(a)
        heapq.heappush(h[b], (-a, i))
        C[i] = b

    A = tuple(A)
    byodo = []

    for i in range(1, hsize):
        if len(h[i]) == 0:
            continue
        # 各幼稚園の最大値をbyodoに入れる
        x = h[i][0]
        heapq.heappush(byodo, (-x[0], x[1]))

    ans = []
    for _ in range(Q):
        c, d = [int(x) for x in input().split()]
        c -= 1

        # 移動元最大値チェック
        cfrom = C[c]
        # c園児の現在時をdに更新
        C[c] = d
        while h[cfrom]:
            x = h[cfrom][0]
            # 最大値の園児の現在の所属幼稚園がC[c]と異なればpopしたままにする
            if C[x[1]] != cfrom:
                heapq.heappop(h[cfrom])
                continue

            # 現在の最大値を平等にpush
            heapq.heappush(byodo, (-x[0], x[1]))
            break

        # c園児をd幼稚園にpush
        heapq.heappush(h[d], (-A[c], c))

        # 移動先最大値チェック
        while h[d]:
            x = h[d][0]
            # 最大値の園児の現在の所属幼稚園がdと異なればpopしたままにする
            if C[x[1]] != d:
                heapq.heappop(h[d])
                continue

            # 現在の最大値をbyodoにpush
            heapq.heappush(byodo, (-x[0], x[1]))
            break

        # 平等の最少値を取得
        while byodo:
            x = byodo[0]

            # 最小値が所属する幼稚園の最大値が異なっていればpopしたままにする
            y = h[C[x[1]]][0]
            if -y[0] != x[0]:
                heapq.heappop(byodo)
                continue

            ans.append(x[0])
            break

    print(('\n'.join(map(str, ans))))


def __starting_point():
    main()

__starting_point()

from heapq import heappop, heappush
from typing import Optional


class DeletableHeapq:
    """Deletable Heapq: A heapq supporting lazy deletion of values."""

    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:
        self.is_max_heap = is_max_heap
        self.size = 0
        self._set = set()
        self._heap = []

        if initial_values:
            for v in initial_values:
                self.push(v)

    @property
    def top(self) -> Optional[int]:
        """Return the minimum value if is_max_heap is False;
        otherwise, return the maximum value from the heap.
        If the heap is empty, None is returned.
        """
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        return self._heap[0] if not self.is_max_heap else -self._heap[0]

    def pop(self) -> Optional[int]:
        """Pop and return the minimum value if is_max_heap is False;
        otherwise, return the maximum value from the heap.
        If the heap is empty, None is returned.
        """
        while self._heap and self._heap[0] not in self._set:
            heappop(self._heap)
        if not self._heap:
            return None
        self.size -= 1
        res = heappop(self._heap)
        self._set.discard(res)
        return res if not self.is_max_heap else -res

    def push(self, value: int) -> None:
        """Push value into the heap."""
        if self.is_max_heap:
            value = -value
        if value in self._set:
            return
        self.size += 1
        heappush(self._heap, value)
        self._set.add(value)

    def delete(self, value: int) -> None:
        """Delete value from the heap."""
        if self.is_max_heap:
            value = -value
        if value not in self._set:
            return
        self.size -= 1
        self._set.discard(value)


def main():
    # https://atcoder.jp/contests/abc170/tasks/abc170_e
    N, _, *X = list(map(int, open(0).read().split()))
    AB, CD = X[: 2 * N], X[2 * N :]
    rate, belonging = [0] * (N + 1), [0] * (N + 1)
    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]

    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):
        rate[i], belonging[i] = (a << 18) + i, b
        kindy[b].push(rate[i])

    smart_infants = DeletableHeapq(*(k.top for k in kindy if k.size))
    res = []
    for c, next_k in zip(*[iter(CD)] * 2):
        prev_k = belonging[c]
        belonging[c] = next_k

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.delete(kindy[k].top)

        kindy[prev_k].delete(rate[c])
        kindy[next_k].push(rate[c])

        for k in (prev_k, next_k):
            if kindy[k].size:
                smart_infants.push(kindy[k].top)

        res.append(smart_infants.top >> 18)

    print(("\n".join(map(str, res))))


def __starting_point():
    main()

__starting_point()

# coding: utf-8
import sys
from heapq import heapify, heappop, heappush
from collections import defaultdict

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

N, Q = lr()
top = []
left_top = []
infants = [[] for _ in range(2*10**5+1)]  # 1-indexed
left = [[] for _ in range(2*10**5+1)]
dic = defaultdict(list)
for i in range(1, N+1):
    a, b = lr()
    heappush(infants[b], (-a, i))
    dic[i] = (a, b)

for i in range(1, 2*10**5+1):
    if infants[i]:
        rate, id = infants[i][0]
        heappush(top, (-rate, id))

for _ in range(Q):
    c, next = lr()
    r, prev = dic[c]
    dic[c] = (r, next)
    r3, prev_top = infants[prev][0]
    heappush(left_top, (-r3, prev_top))
    heappush(left[prev], (-r, c))
    while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:
        heappop(infants[prev])
        heappop(left[prev])
    if infants[prev]:
        rate, id = infants[prev][0]
        heappush(top, (-rate, id))
    if infants[next]:
        heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # idをpush
    heappush(infants[next], (-r, c))  # tupleでpush
    while left[next] and infants[next][0][1] == left[next][0][1]:
        heappop(infants[next])
        heappop(left[next])
    r2, id2 = infants[next][0]
    heappush(top, (-r2, id2))
    while left_top and top[0][1] == left_top[0][1]:
        heappop(top); heappop(left_top)
    answer = top[0][0]
    print(answer)


from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t,_ in x:t and f(l,-t[0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=y and y[0]or 0;f(y,-a),f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y[0]<t:f(l,a);t<0and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

import sys
def input():return sys.stdin.readline().strip()
from collections import defaultdict
from heapq import heappop, heappush, heapify

def main():
    N, Q = map(int, input().split())
    infant_info = [tuple(map(int, input().split())) for _ in range(N)]
    queries = [tuple(map(int, input().split())) for _ in range(Q)]
    
    num_kd = 2 * 10 ** 5
    nums = [0] * num_kd
    h = [[] for _ in range(num_kd)]
    pos = [-1] * N
    kd_max = defaultdict(int)
    min_max_timestamp = [0] * num_kd

    # init
    for i, (a, b) in enumerate(infant_info):
        b -= 1

        heappush(h[b], (-a, i))
        pos[i] = b
        nums[b] += 1

        kd_max[b] = max(kd_max[b], a)
    
    # rate, id, timestamp
    min_max_h = [(val, kd, 0) for kd, val in kd_max.items()]

    heapify(min_max_h)

    # query
    for t, (c, to_kd) in enumerate(queries, 1):
        c -= 1
        to_kd -= 1

        from_kd = pos[c]
        pos[c] = to_kd

        # from
        nums[from_kd] -= 1
        if nums[from_kd] > 0:
            while True:
                rate, infant = heappop(h[from_kd])
                if pos[infant] == from_kd:
                    heappush(h[from_kd], (rate, infant))
                    heappush(min_max_h, (-rate, from_kd, t))
                    break
        
        min_max_timestamp[from_kd] = t

        
        # to
        nums[to_kd] += 1

        rate_c, _ = infant_info[c]
        heappush(h[to_kd], (-rate_c, c))

        while True:
            rate, infant = heappop(h[to_kd])
            if pos[infant] == to_kd:
                heappush(h[to_kd], (rate, infant))
                heappush(min_max_h, (-rate, to_kd, t))
                break
        
        min_max_timestamp[to_kd] = t



        # equality
        # print("pos", pos)
        while True:
            rate, kd, ts = heappop(min_max_h) 
            if min_max_timestamp[kd] == ts:
                print(rate)
                heappush(min_max_h, (rate, kd, ts))
                break
    
def __starting_point():
    main()
__starting_point()

from heapq import *
import sys
input = sys.stdin.readline

def main():
    n, q = list(map(int, input().split()))
    children = [[int(x) for x in input().split()] for _ in range(n)]
    
    m = int(2*1e5)
    heap_each = [[] for _ in range(m)]
    each_moved = [dict() for _ in range(m)]
    heap_all = []
    all_moved = dict()
    for i in range(n):
        a, b = children[i]
        heappush(heap_each[b-1], -a)
    for i in range(m):
        if heap_each[i]:
            heappush(heap_all, -heap_each[i][0])
    
    ans = []
    for i in range(q):
        c, d = list(map(int, input().split()))#幼児Cが幼稚園Dに移動
        a, b = children[c-1]#幼児のレート：A、元の幼稚園：B
        if a == -heap_each[b-1][0]:#幼児がその園のトップだったとき
            if a in all_moved:#全体リストから削除
                all_moved[a] += 1
            else:
                all_moved[a] = 1
            heappop(heap_each[b-1])#その幼稚園のリストから削除
            while heap_each[b-1]:#値が削除済みの園児かどうか判定:そうでないなら全体リストに値を追加
                if heap_each[b-1][0] in each_moved[b-1] and each_moved[b-1][heap_each[b-1][0]] > 0:
                    each_moved[b-1][heap_each[b-1][0]] -= 1
                    heappop(heap_each[b-1])
                    continue
                heappush(heap_all, -heap_each[b-1][0])
                break
        else:#幼児がその園のトップでないときは、削除リストに追加するのみ
            if -a in each_moved[b-1]:
                each_moved[b-1][-a] += 1
            else:
                each_moved[b-1][-a] = 1
        #転園先での話
        if not heap_each[d-1]:#新しい園がひとりぼっちなら
            heappush(heap_each[d-1], -a)
            heappush(heap_all, a)
        elif -a < heap_each[d-1][0]:#新しい園でトップなら
            if -heap_each[d-1][0] in all_moved:#旧一位を全体リストから削除
                all_moved[-heap_each[d-1][0]] += 1
            else:
                all_moved[-heap_each[d-1][0]] = 1
            heappush(heap_each[d-1], -a)
            heappush(heap_all, a)
        else:#新しい園でただの人なら
            heappush(heap_each[d-1], -a)
        while heap_all:
            if heap_all[0] in all_moved and all_moved[heap_all[0]] > 0:
                all_moved[heap_all[0]] -= 1
                heappop(heap_all)
                continue
            break
        children[c-1][1] = d
        ans.append(heap_all[0])
    
    
    for answer in ans:
        print(answer)

            
def __starting_point():
    main()        

__starting_point()

from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t in x:t[0]and f(l,-t[0][0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1][1]=d;v,w=x[b];y,_=x[d];t=0;f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y:t=y[0]
 f(y,-a)
 if y[0]!=t:f(l,a);t<0and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

import sys
from heapq import heappop, heappush, heapify

sys.setrecursionlimit(10 ** 7)
input = sys.stdin.readline
f_inf = float('inf')
mod = 10 ** 9 + 7
MAX = 2 * 10 ** 5 + 1


def resolve():
    def max_rate_in_cls(c):
        q = class_rate[c]
        while q:
            x, enj = q[0]
            if enji_cls[enj] == c:
                return -x
            else:
                heappop(q)
        return 0

    def get_ans():
        q = max_rate
        while True:
            x, c = q[0]
            if max_rate_in_cls(c) == x:
                return x
            heappop(q)

    def max_rate_in_cls(c):
        q = class_rate[c]
        while q:
            x, enj = q[0]
            if enji_cls[enj] == c:
                return -x
            else:
                heappop(q)
        return 0

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

    enji_rate = [0] * (n + 1)
    enji_cls = [0] * (n + 1)
    class_rate = [[] for _ in range(MAX)]
    for i in range(1, n + 1):
        rate, cls = list(map(int, input().split()))
        enji_rate[i] = rate
        enji_cls[i] = cls
        heappush(class_rate[cls], (-rate, i))

    max_rate = []
    for c in range(MAX):
        x = max_rate_in_cls(c)
        if x:
            max_rate.append((x, c))
    heapify(max_rate)

    for _ in range(q):
        enj, after_cls = list(map(int, input().split()))
        before_cls = enji_cls[enj]
        heappush(class_rate[after_cls], (-enji_rate[enj], enj))
        enji_cls[enj] = after_cls
        for c in (before_cls, after_cls):
            x = max_rate_in_cls(c)
            if x != 0:
                heappush(max_rate, (x, c))
        print((get_ans()))


def __starting_point():
    resolve()

__starting_point()

from collections import defaultdict
import heapq
import sys
input = sys.stdin.readline

n, q = list(map(int, input().split()))
ab = [list(map(int, input().split())) for _ in range(n)]
cd = [list(map(int, input().split())) for _ in range(q)]

thq = []
top = defaultdict(int)
topcnt = defaultdict(int)
rhq = [[] for _ in range(2 * 10 ** 5 + 1)]
rate = [defaultdict(int) for _ in range(2 * 10 ** 5 + 1)]
for a, b in ab:
    top[b] = max(top[b], a)
    rate[b][a] += 1
    heapq.heappush(rhq[b], -a)
for num in list(top.values()):
    heapq.heappush(thq, num)
    topcnt[num] += 1

for c, d in cd:
    a, b = ab[c - 1]
    ab[c - 1][1] = d

    # 元の園について
    rate[b][a] -= 1
    if rate[b][a] == 0:
        del rate[b][a]
    topcnt[top[b]] -= 1
    if topcnt[top[b]] == 0:
        del topcnt[top[b]]
    del top[b]
    if len(rate[b]) > 0:
        top[b] = -heapq.heappop(rhq[b])
        while top[b] not in rate[b]:
            top[b] = -heapq.heappop(rhq[b])
        heapq.heappush(rhq[b], -top[b])
        heapq.heappush(thq, top[b])
        topcnt[top[b]] += 1

    # 新しい園について
    rate[d][a] += 1
    heapq.heappush(rhq[d], -a)
    if a > top[d]:
        if top[d] > 0:
            topcnt[top[d]] -= 1
            if topcnt[top[d]] == 0:
                del topcnt[top[d]]
        top[d] = a
        topcnt[top[d]] += 1
        heapq.heappush(thq, top[d])

    # 最小値について
    ans = heapq.heappop(thq)
    while ans not in topcnt:
        ans = heapq.heappop(thq)
    heapq.heappush(thq, ans)
    print(ans)


import heapq
import sys
def input(): return sys.stdin.readline().rstrip()


def main():
    n, q = map(int, input().split())
    syozoku = [0]*(n+1)
    rate = [0]*(n+1)
    enrate = [0]*(2*10**5+1)
    saikyourate = HeapDict()
    for i in range(1, 2*10**5+1):
        enrate[i] = HeapDict()
    for i in range(1, n+1):
        a, b = map(int, input().split())
        syozoku[i] = b
        rate[i] = a
        enrate[b].insert(-a)
    for i in range(1, 2*10**5+1):
        if len(enrate[i].h) != 0:
            saikyourate.insert(-(enrate[i].get_min()))
    for _ in range(q):
        c,d=map(int, input().split()) #移動 syozoku[c]→d
        saikyourate.erase(-(enrate[syozoku[c]].get_min()))
        enrate[syozoku[c]].erase(-rate[c])
        if len(enrate[syozoku[c]].h) != 0:
            saikyourate.insert(-(enrate[syozoku[c]].get_min()))
        if len(enrate[d].h) != 0:
            saikyourate.erase(-(enrate[d].get_min()))
        enrate[d].insert(-rate[c])
        saikyourate.insert(-(enrate[d].get_min()))
        syozoku[c]=d
        print(saikyourate.get_min())


        


class HeapDict:  # 実装https://tsubo.hatenablog.jp/entry/2020/06/15/124657
    def __init__(self):
        self.h = []
        self.d = dict()

    def insert(self, x):
        heapq.heappush(self.h, x)
        if x not in self.d:
            self.d[x] = 1
        else:
            self.d[x] += 1

    def erase(self, x):
        if x not in self.d or self.d[x] == 0:
            print(x, "is not in HeapDict")
            return
        else:
            self.d[x] -= 1

        while len(self.h) != 0:
            if self.d[self.h[0]] == 0:
                heapq.heappop(self.h)
            else:
                break

    def is_exist(self, x):
        if x in self.d and self.d[x] != 0:
            return True
        else:
            return False

    def get_min(self):
        return self.h[0]


def __starting_point():
    main()
__starting_point()

import heapq

class BalancingTree:
    def __init__(self):
        self.p = []
        self.q = []

    def insert(self, x):
        heapq.heappush(self.p, x)

    def erase(self, x):
        heapq.heappush(self.q, x)

    def minimum(self):
        while self.q and self.p[0] == self.q[0]:
            heapq.heappop(self.p)
            heapq.heappop(self.q)
        return self.p[0] if self.p else None


MAX = 2*10**5
n, q = list(map(int, input().split()))
ab = []
k = [BalancingTree() for _ in range(MAX)]
for i in range(n):
    a, b = list(map(int, input().split()))
    b -= 1
    ab.append([a, b])
    k[b].insert(-a)

k_max = BalancingTree()
for i in range(MAX):
    if v := k[i].minimum():
        k_max.insert(-v)

for _ in range(q):
    c, d = [int(x)-1 for x in input().split()]
    a, b = ab[c]
    k_max.erase(-k[b].minimum())
    if v := k[d].minimum():
        k_max.erase(-v)
    k[b].erase(-a)

    k[d].insert(-a)
    if v := k[b].minimum():
        k_max.insert(-v)
    k_max.insert(-k[d].minimum())
    ab[c][1] = d

    print((k_max.minimum()))


import heapq

N, Q = map(int, input().split())

M = 2 * 10**5

rate_list = []
rates = [[] for _ in range(M)]
members = [set() for _ in range(M)]
belongs = [-1] * N

for i in range(N):
    A, B = map(int, input().split())
    B = B - 1
    heapq.heappush(rates[B], (-A, i))
    members[B].add(i)
    belongs[i] = B
    rate_list.append(A)

max_rates = []
for num, rate in enumerate(rates):
    if len(rate) > 0:
        heapq.heappush(max_rates, (-rate[0][0], num))

for i in range(Q):
    C, D = map(int, input().split())
    C = C - 1
    D = D - 1
    old = belongs[C]
    belongs[C] = D
    members[old].remove(C)
    members[D].add(C)
    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:
        heapq.heappop(rates[old])
    
    if len(rates[old]) > 0:
        heapq.heappush(max_rates, (-rates[old][0][0], old))
        
    heapq.heappush(rates[D], (-rate_list[C], C))
    heapq.heappush(max_rates, (rate_list[C], D))

    while max_rates:
        rate, num = max_rates[0]
        if len(rates[num])==0 or - rates[num][0][0] != rate:
            heapq.heappop(max_rates)
        else:
            print(rate)
            break

from heapq import heappop, heappush
# プライオリティキュー
# 要素の挿入、最小値（最大値）の取り出しが速い
# 園児の転園による削除がボトルネック
# 削除しなければ良いと考える（勿論チェックは必要）

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

# 幼稚園の数
M = 2 * (10 ** 5)
# 幼児iの所属先の幼稚園
belong = [None] * N
# 幼児iのレート
rate = [None] * N
# 幼稚園キュー。(マイナスレート, 幼児番号)
# KinDerGarTen
kdgt = [[] for _ in range(M)]

for c in range(N):
    A, B = list(map(int, input().split()))
    # 幼稚園番号を0-indexにする
    B -= 1
    # 所属
    belong[c] = B
    # レート
    rate[c] = A
    # 幼稚園の箱に対して、(マイナスレート、幼児番号)
    heappush(kdgt[B], (-A, c))

# 最強園児キュー。(プラスレート, 幼児番号, 園番号)
q = []

# 各幼稚園について
for i in range(M):
    # 一人も所属していなければパス
    if kdgt[i]:
        # マイナスがかかっているので最大値が取り出せる
        A, c = kdgt[i][0]
        # (プラスレート、幼児番号、園番号)
        heappush(q, (-A, c, i))

for _ in range(Q):
    C, D = list(map(int, input().split()))
    # 幼児番号、園番号を0-indexに
    C -= 1
    D -= 1
    # 移動元の幼稚園
    pd = belong[C]
    # 幼児のbelongを更新
    belong[C] = D

    # 移動元の幼稚園キューを更新
    while kdgt[pd]:
        # その園での最強園児（仮）
        A, c = kdgt[pd][0]
        # 既に存在しないとき、取り除く
        # 存在するとき, 最強園児キューへ追加
        if belong[c] != pd:
            heappop(kdgt[pd])
        else:
            heappush(q, (-A, c, pd))
            break

    # 移動先の幼稚園キューを更新
    # 対象の幼児を追加
    heappush(kdgt[D], (-rate[C], C))
    while kdgt[D]:
        # その園での最強園児（仮）
        A, c = kdgt[D][0]
        # 既に存在しないとき取り除く
        # 存在するとき, 最強園児キューへ追加
        if belong[c] != D:
            heappop(kdgt[D])
        else:
            heappush(q, (-A, c, D))
            break

    while q:
        # 最強の中の最弱（仮）
        # (プラスレート、園児番号、園番号)
        A, c, d = q[0]
        # キューの先頭の幼児が既に去っている or 所属する幼稚園キューの先頭では無い時取り除く
        # そうではないとき、これが答え
        # if belong[c] != d or kdgt[d][0][1] != c:
        if belong[c] != d or kdgt[d][0][1] != c:
            heappop(q)
        else:
            print(A)
            break


from heapq import heappush, heappop

n, q = map(int, input().split())
rate = [0]*n
belong = [-1]*n
yochien_rates = [[] for i in range(2 * 10 ** 5 + 10)]
delete_yochien_rates = [[] for i in range(2 * 10 ** 5 + 10)]
yochiens = set()
for i in range(n):
    a, b = map(int, input().split())
    b -= 1
    rate[i] = a
    belong[i] = b
    yochiens.add(b)
    heappush(yochien_rates[b], -a)

maxs = []
delete_maxs = []

for i in yochiens:
    heappush(maxs, -yochien_rates[i][0])
ans = []
for _ in range(q):
    c, d = map(int, input().split())
    c -= 1
    d -= 1

    old = belong[c]
    belong[c] = d

    # 元いた幼稚園と新しい幼稚園の最強園児を削除キューに入れる
    heappush(delete_maxs, -yochien_rates[old][0])
    if yochien_rates[d]:
        heappush(delete_maxs, -yochien_rates[d][0])

    # 新しい幼稚園のratesと全体のratesの更新
    heappush(yochien_rates[d], -rate[c])
    heappush(maxs, -yochien_rates[d][0])

    # oldの更新
    heappush(delete_yochien_rates[old], -rate[c])
    while delete_yochien_rates[old] and yochien_rates[old][0] == delete_yochien_rates[old][0]:
        heappop(yochien_rates[old])
        heappop(delete_yochien_rates[old])
    if yochien_rates[old]:
        heappush(maxs, -yochien_rates[old][0])

    # 最小値計算
    while delete_maxs and maxs[0] == delete_maxs[0]:
        heappop(maxs)
        heappop(delete_maxs)
    ans.append(maxs[0])

print(*ans, sep='\n')



import heapq

ymax = 200000
N, Q  = list(map(int, input().split()))

yo = [[] for i in range(ymax+1)]
ym = []
AB = [(0,0)]
s = set()

for i in range(N):
  A, B  = list(map(int, input().split()))
  AB.append( (A, B) )
  heapq.heappush(yo[B],(-A,i+1))
  s.add(B)
#
for i in s:
  mA, c = yo[i][0]
  heapq.heappush(ym,(-mA,c,i)) 
#
for i in range(Q):
  C, D  = list(map(int, input().split()))
  A, B = AB[C]
  AB[C] = (A, D)

  if  yo[B][0][1] == C:
    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):
      heapq.heappop(yo[B])
    if yo[B]:
      mA, c = yo[B][0]
      heapq.heappush(ym,(-mA,c,B)) 
#
  heapq.heappush(yo[D],(-A,C))
  mA, c = yo[D][0]
  if c == C:
    heapq.heappush(ym,(-mA,c,D)) 
#
  while ym:
    if AB[ ym[0][1] ][1] != ym[0][2]:
      heapq.heappop(ym)
    elif ym[0][1] != yo[ ym[0][2] ][0][1] :
      heapq.heappop(ym)
    else:
      break
#      
  print((ym[0][0]))
#


from heapq import *
n,q = map(int,input().split())
kg = [[] for _ in range(2*10**5)]
pos = [0]*n
rate = [0]*n
for i in range(n):
    a,b = map(int,input().split())
    b-=1
    heappush(kg[b], (-a,i))
    pos[i] = b
    rate[i] = a

evenness = []
for i in range(2*10**5):
    if kg[i]:
        a,c = kg[i][0]
        heappush(evenness, (-a,c))

for _ in range(q):
    c,d = map(int,input().split())
    c,d = c-1,d-1
    prev = pos[c]
    pos[c] = d
    heappush(kg[d], (-rate[c],c))
    while kg[prev] and pos[kg[prev][0][1]]!=prev:
        heappop(kg[prev])
    while kg[d] and pos[kg[d][0][1]]!=d:
        heappop(kg[d])
    if kg[prev]:
        a,c = kg[prev][0]
        heappush(evenness, (-a,c))
    if kg[d]:
        a,c = kg[d][0]
        heappush(evenness, (-a,c))
    while evenness and kg[pos[evenness[0][1]]][0][1]!=evenness[0][1]:
        heappop(evenness)
    print(evenness[0][0])

from collections import defaultdict
import heapq

n, q = map(int, input().split())
kindergarten = defaultdict(lambda : [])

best = []
A, B = [], []

for i in range(n):
    a, b = map(int, input().split())
    A.append(a)  # スコア
    B.append(b)  # 幼稚園番号
    heapq.heappush(kindergarten[b], (-a, i))

for i in kindergarten:
    tmp = kindergarten[i][0]
    heapq.heappush(best, (-tmp[0], tmp[1]))

for i in range(q):
    c, d = map(int, input().split())  # c: 幼児の番号, d: 転園先の幼稚園番号
    kd_ori = B[c-1]
    B[c-1] = d

    while kindergarten[kd_ori]:
        x = kindergarten[kd_ori][0]
        if B[x[1]] != kd_ori:
            heapq.heappop(kindergarten[kd_ori])
            continue
        heapq.heappush(best, (-x[0], x[1]))
        break
    heapq.heappush(kindergarten[d], (-A[c-1], c-1))

    while kindergarten[d]:
        tmp = kindergarten[d][0]
        heapq.heappush(best, (-tmp[0], tmp[1]))
        break

    while best:
        tmp = best[0]

        tmp2 = kindergarten[B[tmp[1]]][0]
        if -tmp2[0] != tmp[0]:
            heapq.heappop(best)
            continue
        print(tmp[0])
        break

    print()

from heapq import*
f,g=heappush,heappop
(n,q),*z=[[*map(int,t.split())]for t in open(0)]
*x,(l,r)=eval('[[],[]],'*8**6)
for a,b in z[:n]:f(x[b][0],-a)
for t,_ in x:t and f(l,-t[0])
for c,d in z[n:]:
 a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=0;f(w,-a)
 if-v[0]==a:
  while w and w[0]==v[0]:g(w),g(v)
  f(r,a);v and f(l,-v[0])
 if y:t=y[0]
 f(y,-a)
 if y[0]!=t:f(l,a);t<0and f(r,-t)
 while r and l[0]==r[0]:g(l),g(r)
 print(l[0])

from heapq import heappop, heappush
# プライオリティキュー
# 要素の挿入、最小値（最大値）の取り出しが速い
# 園児の転園による削除がボトルネック
# 削除しなければ良いと考える（勿論チェックは必要）

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

# 幼稚園の数
M = 2 * (10 ** 5)
# 幼児iの所属先の幼稚園
belong = [None] * N
# 幼児iのレート
rate = [None] * N
# 幼稚園キュー。(マイナスレート, 幼児番号)
# KinDerGarTen
kdgt = [[] for _ in range(M)]

for c in range(N):
    A, B = list(map(int, input().split()))
    # 幼稚園番号を0-indexにする
    B -= 1
    # 所属
    belong[c] = B
    # レート
    rate[c] = A
    # 幼稚園の箱に対して、(マイナスレート、幼児番号)
    heappush(kdgt[B], (-A, c))

# 最強園児キュー。(プラスレート, 幼児番号, 園番号)
q = []

# 各幼稚園について
for i in range(M):
    # 一人も所属していなければパス
    if kdgt[i]:
        # マイナスがかかっているので最大値が取り出せる
        A, c = kdgt[i][0]
        # (プラスレート、幼児番号、園番号)
        heappush(q, (-A, c, i))

for _ in range(Q):
    C, D = list(map(int, input().split()))
    # 幼児番号、園番号を0-indexに
    C -= 1
    D -= 1
    # 移動元の幼稚園
    pd = belong[C]
    # 幼児のbelongを更新
    belong[C] = D

    # 移動元の幼稚園キューを更新
    while kdgt[pd]:
        # その園での最強園児（仮）
        A, c = kdgt[pd][0]
        # 既に存在しないとき、取り除く
        # 存在するとき, 最強園児キューへ追加
        if belong[c] != pd:
            heappop(kdgt[pd])
        else:
            heappush(q, (-A, c, pd))
            break

    # 移動先の幼稚園キューを更新
    # 対象の幼児を追加
    heappush(kdgt[D], (-rate[C], C))
    while kdgt[D]:
        # その園での最強園児（仮）
        A, c = kdgt[D][0]
        # 既に存在しないとき取り除く
        # 存在するとき, 最強園児キューへ追加
        if belong[c] != D:
            heappop(kdgt[D])
        else:
            heappush(q, (-A, c, D))
            break

    while q:
        # 最強の中の最弱（仮）
        # (プラスレート、園児番号、園番号)
        A, c, d = q[0]
        # キューの先頭の園児が既に去っている or 所属する幼稚園キューの先頭では無い時取り除く
        # （後者について）最強の中の最弱を探したいのに、既に最強ではない園児が紛れ込む場合がある？

        # 2つの条件を確認する部分があまり理解できていない、後日改めて考える
        if belong[c] != d or kdgt[d][0][1] != c:
            heappop(q)
        else:
            print(A)
            break


import heapq
N,Q=list(map(int,input().split()))
A=[0 for i in range(N)];B=[0 for i in range(N)]
C=[0 for i in range(Q)];D=[0 for i in range(Q)]
for i in range(N):
    A[i],B[i]=list(map(int,input().split()));B[i]-=1
for i in range(Q):
    C[i],D[i]=list(map(int,input().split()));C[i]-=1;D[i]-=1
#print([(A[i],B[i]) for i in range(N)])
#print([(C[i],D[i]) for i in range(Q)])
nowbelongs=[B[i] for i in range(N)]
maxrate=[]
kindergarden=[[] for i in range(2*10**5)]
for i in range(N):
    heapq.heappush(kindergarden[B[i]],(-A[i],i))
#range(2*10**5) to range(N)
def saikyo_enji(k):
    while(kindergarden[k]):
        minusrate,index=kindergarden[k][0]
        if nowbelongs[index]==k:
            return index
        else:
            heapq.heappop(kindergarden[k])
    return -1
for k in range(2*10**5):
    i=saikyo_enji(k)
    if i!=-1:
        heapq.heappush(maxrate,(A[i],i))
#print(-1,maxrate,[A[saikyo_enji(i)] for i in range(3)],kindergarden[:3])
for j in range(Q):
    i=C[j]
    #print("#"*30)
    #print([(A[i],nowbelongs[i]) for i in range(N)],nowbelongs[C[j]],D[j])
    oldbelongs=nowbelongs[i]
    nowbelongs[i]=-1
    if saikyo_enji(oldbelongs)!=-1:
        heapq.heappush(maxrate,(A[saikyo_enji(oldbelongs)],saikyo_enji(oldbelongs)))
    heapq.heappush(kindergarden[D[j]],(-A[C[j]],C[j]))
    nowbelongs[C[j]]=D[j]
    heapq.heappush(maxrate,(A[saikyo_enji(D[j])],saikyo_enji(D[j])))
    #print(j,maxrate,[A[saikyo_enji(i)] for i in range(3)])
    #print([(A[i],nowbelongs[i]) for i in range(N)])
    while(maxrate):
        rate,index=maxrate[0]
        if saikyo_enji(nowbelongs[index])==index:
            print(rate)
            break
        else:
            heapq.heappop(maxrate)