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\nn , q = map(int,input().split())\nenzi = [[0,0] for i in range(n)]\nyouti = [[] for i in range(2*10**5)]\nsaikyo = [0 for i in range(2*10**5)]\nans = []\n\nfor i in range(n):\n    a , b = map(int,input().split())\n    enzi[i] = [a,b-1]\n    heappush(youti[b-1],(-a,i))\n\nfor i in range(2*10**5):\n    if youti[i]:\n        now = heappop(youti[i])\n        saikyo[i] = -now[0]\n        heappush(ans,(-now[0],i))\n        heappush(youti[i],now)\n\nfor _ in range(q):\n    c , d = map(lambda x:int(x)-1,input().split())\n    heappush(youti[d],(-enzi[c][0],c))\n    moto = enzi[c][1]\n    enzi[c][1] = d\n    \n    while True:\n        if youti[moto]:\n            now = heappop(youti[moto])\n            if enzi[now[1]][1] == moto:\n                if saikyo[moto] != -now[0]:\n                    saikyo[moto] = -now[0]\n                    heappush(ans,(-now[0],moto))\n                heappush(youti[moto],now)\n                break\n        else:\n            saikyo[moto] = 0\n            break\n    while True:\n        now = heappop(youti[d])\n        if enzi[now[1]][1] == d:\n            if saikyo[d] != -now[0]:\n                saikyo[d] = -now[0]\n                heappush(ans,(-now[0],d))\n            heappush(youti[d],now)\n            break\n    \n    while True:\n        now = heappop(ans)\n        if saikyo[now[1]] == now[0]:\n            print(now[0])\n            heappush(ans,now)\n            break", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t,_ in x:t and f(l,-t[0])\nfor c,d in z[n:]:\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)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y[0]<t:f(l,a);t and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools\nimport time,random,resource\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**10\nmod = 10**9+7\ndd = [(-1,0),(0,1),(1,0),(0,-1)]\nddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]\n\ndef LI(): return list(map(int, sys.stdin.readline().split()))\ndef LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\ndef pe(s): return print(str(s), file=sys.stderr)\ndef JA(a, sep): return sep.join(map(str, a))\ndef JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)\n\n\nclass DQ():\n    def __init__(self):\n        self.q = []\n        self.d = []\n\n    def add(self, x):\n        heapq.heappush(self.q, x)\n\n    def rem(self, x):\n        heapq.heappush(self.d, x)\n\n    def top(self):\n        while self.d and self.q[0] == self.d[0]:\n            heapq.heappop(self.q)\n            heapq.heappop(self.d)\n\n        if self.q:\n            return self.q[0]\n\n        return None\n\ndef main():\n    n,q = LI()\n    ab = [LI() for _ in range(n)]\n    cd = [LI() for _ in range(q)]\n\n    m = 2 * 10**5 + 1\n    r = DQ()\n    t = [DQ() for _ in range(m)]\n    ca = [-1] * (n+1)\n    e = [-1] * (n+1)\n\n    for c in range(1, n+1):\n        a,b = ab[c-1]\n        ca[c] = a\n        e[c] = b\n        tp = t[b].top()\n        if tp:\n            s = -tp\n            if s < a:\n                r.rem(s)\n                r.add(a)\n            t[b].add(-a)\n        else:\n            r.add(a)\n            t[b].add(-a)\n\n        # print(\"ab\",a,b,r.q,r.d)\n\n    rr = []\n    for c, d in cd:\n        a = ca[c]\n        b = e[c]\n        e[c] = d\n        s = -t[b].top()\n        t[b].rem(-a)\n        if s == a:\n            r.rem(a)\n            u = t[b].top()\n            if not u is None:\n                r.add(-u)\n\n        tp = t[d].top()\n        if tp:\n            s = -tp\n            if s < a:\n                r.rem(s)\n                r.add(a)\n            t[d].add(-a)\n        else:\n            r.add(a)\n            t[d].add(-a)\n\n        # print(\"cd\", c,d,r.q,r.d)\n        rr.append(r.top())\n\n    return JA(rr, \"\\n\")\n\n\nprint(main())\n\n\n", "import sys\nreadline = sys.stdin.readline\n\nimport heapq as hq\n\nN,Q = list(map(int,readline().split()))\nNN = 2 * (10 ** 5)\n\n# (\u30ec\u30fc\u30c8, \u6240\u5c5e\u5712)\ninfants = [None] * (N + 1)\n# (\u6700\u5f37\u5712\u5150, \u5712\u5150\u756a\u53f7)\nkinda = [[] for i in range(NN + 1)]\nfor i in range(N):\n  a,b = list(map(int,readline().split()))\n  infants[i + 1] = [a,b]\n  hq.heappush(kinda[b], (-a, i + 1))\n\n# (\u6700\u5f31\u5712\u5150, \u5712\u306e\u756a\u53f7)\nall_kinda = []\nfor i in range(len(kinda)):\n  if kinda[i]:\n    hq.heappush(all_kinda, (-kinda[i][0][0], i))\n  \ndef get_max_rate(x): # \u5712x\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u53d6\u308a\u51fa\u3059\n  q = kinda[x]\n  while q:\n    rate, ind = hq.heappop(q)\n    if infants[ind][1] != x:\n      continue\n    hq.heappush(q, (rate, ind))\n    return -rate\n  return -1\n  \nfor i in range(Q):\n  ind,next_kinda_id = list(map(int,readline().split()))\n  rate,old_kinda_id = infants[ind]\n  infants[ind][1] = next_kinda_id\n  hq.heappush(kinda[next_kinda_id],(-rate, ind))\n  \n  old_kinda_max_rate = get_max_rate(old_kinda_id)\n  if old_kinda_max_rate != -1:\n    hq.heappush(all_kinda, (old_kinda_max_rate, old_kinda_id))\n    \n  next_kinda_max_rate = get_max_rate(next_kinda_id)\n  if next_kinda_max_rate != -1:\n    hq.heappush(all_kinda, (next_kinda_max_rate, next_kinda_id))\n    \n  while all_kinda:\n    rate, kinda_id = hq.heappop(all_kinda)\n    cur_max_rate = get_max_rate(kinda_id)\n    if rate != cur_max_rate:\n      continue\n    hq.heappush(all_kinda, (rate, kinda_id))\n    print(rate)\n    break\n", "import sys\nimport heapq\nfrom collections import defaultdict\n\nsys.setrecursionlimit(10 ** 6)\nINF = float(\"inf\")\nMOD = 10 ** 9 + 7\n\n\ndef input():\n    return sys.stdin.readline().strip()\n\n\ndef main():\n    MAX = 10 ** 5 * 2\n    N, Q = list(map(int, input().split()))\n    heap = [[] for _ in range(MAX)]\n    for i in range(MAX):\n        heapq.heapify(heap[i])\n\n    rates = [0] * N\n    places = [0] * N\n    for i in range(N):\n        a, b = list(map(int, input().split()))\n        places[i] = b - 1\n        rates[i] = a\n        heapq.heappush(heap[b - 1], (-a, i))\n\n    heap_all = []\n    heapq.heapify(heap_all)\n    m = INF\n    p = None\n    for i in range(MAX):\n        if not heap[i]:\n            continue\n\n        m = -heap[i][0][0]\n        p = i\n        child = heap[i][0][1]\n        heapq.heappush(heap_all, (m, p, child))\n\n    ans = []\n    for _ in range(Q):\n        c, d = list(map(int, input().split()))\n        child = c - 1\n        cur = d - 1\n        prev = places[child]\n        rate = rates[child]\n\n        # \u65b0\u3057\u3044\u30af\u30e9\u30b9\u3078\u306e\u8ffd\u52a0\n        heapq.heappush(heap[cur], (-rate, child))\n        places[child] = cur\n\n        # \u6700\u5c0f\u5024\u306e\u691c\u7d22\n        while heap[prev]:\n            v, i = heap[prev][0]\n            if places[i] == prev:\n                heapq.heappush(heap_all, (-v, prev, i))\n                break\n            else:\n                heapq.heappop(heap[prev])\n\n        while heap[cur]:\n            v, i = heap[cur][0]\n            if places[i] == cur:\n                heapq.heappush(heap_all, (-v, cur, i))\n                break\n            else:\n                heapq.heappop(heap[cur])\n\n        while True:\n            r, p, i = heap_all[0]\n            if p == places[i] and heap[p][0][0] == -r:\n                ans.append(r)\n                break\n            else:\n                heapq.heappop(heap_all)\n\n    for a in ans:\n        print(a)\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "N,Q=map(int,input().split())\nwhere=[]\nrating=[]\nfrom heapq import heapify,heappop,heappush\ngarten=[[] for _ in range(2*10**5)] #\u5927\u304d\u3044\u9806(\u30de\u30a4\u30ca\u30b9\u639b\u3051)\nsaikyo=[] #\u5c0f\u3055\u3044\u9806\nfor i in range(N):\n    A,B=map(int,input().split())\n    where.append(B-1)\n    rating.append(A)\n    heappush(garten[B-1],(-A,i)) #(\u30ec\u30fc\u30c8\u3001\u5712\u5150)\n\nfor i in range(2*10**5):\n    if not garten[i]:\n        continue\n    rate,num=garten[i][0]\n    heappush(saikyo,(-rate,i)) #(\u30ec\u30fc\u30c8\u3001\u5e7c\u7a1a\u5712)\n\nfor _ in range(Q):\n    C,D=map(int,input().split())\n    C,D=C-1,D-1 #\u5e7c\u5150\u3001\u8ee2\u5712\u5148\n    \n    moto=where[C]\n    where[C]=D\n    heappush(garten[D],(-rating[C],C)) #\u8ee2\u5712\u5148\u306b\u8ffd\u52a0\n    if garten[D][0][1]==C:\n        heappush(saikyo,(rating[C],D))\n\n\n    while garten[moto]: #\u8ee2\u5712\u5143\u306e\u6574\u7406\n        a,b=garten[moto][0]\n        if where[b]==moto:\n            break\n        heappop(garten[moto])\n    heappush(saikyo,(-a,moto))\n    #print(garten[:5])\n    while True: #\u6700\u5f37\u30ea\u30b9\u30c8\u306e\u6574\u7406\n        #print(saikyo)\n        a,b=saikyo[0]\n        if not garten[b]:\n            heappop(saikyo)\n            continue\n        if garten[b][0][0]==-a:\n            break\n        heappop(saikyo)\n    print(a)", "import sys\nimport heapq as hq\nreadline = sys.stdin.readline\n\nns = lambda: readline().rstrip()\nni = lambda: int(readline().rstrip())\nnm = lambda: list(map(int, readline().split()))\nnl = lambda: list(map(int, readline().split()))\n\nn, q = nm()\nm = 2*10**5 + 5\ncur = [-1]*n\nrate = [0]*n\nsec = [list() for _ in range(m)]\nfor i in range(n):\n    a, b = nm()\n    rate[i] = a\n    cur[i] = b\n    hq.heappush(sec[b], (-a, i))\ntop = list()\nfor i in range(m):\n    if sec[i]:\n        hq.heappush(top, (-sec[i][0][0], sec[i][0][1], i))\nfor _ in range(q):\n    c, d = nm()\n    c -= 1\n    bef = cur[c]\n    cur[c] = d\n    hq.heappush(sec[d], (-rate[c], c))\n    if sec[d][0][1] == c:\n        hq.heappush(top, (rate[c], c, d))\n    fl = 0\n    while sec[bef] and cur[sec[bef][0][1]] != bef:\n        hq.heappop(sec[bef])\n        fl = 1\n    if fl and sec[bef]:\n        hq.heappush(top, (-sec[bef][0][0], sec[bef][0][1], bef))\n    while not sec[top[0][2]] or sec[top[0][2]][0][1] != top[0][1]:\n        hq.heappop(top)\n    print((top[0][0]))\n", "#import time \n#it = time.time()\nfrom heapq import heapify,heappush,heappop\nimport sys\ninput = sys.stdin.readline\n\nN, Q = list(map(int,input().split()))\n\nS = []\nPQs = [[] for _ in range(200000)]\nT = [0]*200000 #\u5e7c\u7a1a\u5712\u3054\u3068\u306e\u6700\u7d42\u66f4\u65b0\nM = []\nfor n in range(N):\n  a, b = list(map(int,input().split()))\n  S.append([a,b-1])#\u30ec\u30fc\u30c8\u3001\u6240\u5c5e\n  PQs[b-1]+=[(-a,n)]#-\u30ec\u30fc\u30c8\u3001\u4eba\n\nfor b in range(200000):\n  if len(PQs[b])>0:\n    heapify(PQs[b])\n    M.append((-PQs[b][0][0],b,0))#\u30ec\u30fc\u30c8\u3001\u4eba\u3001\u6240\u5c5e\u3001\u66f4\u65b0\u6642\nheapify(M)\n\n\nans = []\nfor q in range(1,Q+1):#\u6642\u523b\u30021\u304b\u3089\u30b9\u30bf\u30fc\u30c8\n  c, d = list(map(int,input().split()))\n  d = d-1\n  d_prv = S[c-1][1]\n  S[c-1][1] = d #\u60c5\u5831\u306e\u66f4\u65b0\n  \n  #\u8ee2\u5712\u5148\u306e\u5e7c\u7a1a\u5712\u306b\u3064\u3044\u3066\n  heappush(PQs[d],(-S[c-1][0],c-1))#-\u30ec\u30fc\u30c8\u3001\u4eba\n  while d != S[PQs[d][0][1]][1]:#\u6240\u5c5e\u304c\u6574\u5408\u3057\u3066\u3044\u306a\u3044\u6642\uff08\u53e4\u304f\u9593\u9055\u3063\u305f\u60c5\u5831\u3067\u3042\u308b\u6642\uff09\n    heappop(PQs[d])\n  if -PQs[d][0][0] == S[c-1][0]:\n  \theappush(M,(-PQs[d][0][0],d,q))\n  \tT[d] = q #\u6700\u7d42\u66f4\u65b0\u6642\u3092\u30a2\u30c3\u30d7\u30c7\u30fc\u30c8\n  \n  #\u8ee2\u5712\u5143\u306e\u5e7c\u7a1a\u5712\u306b\u3064\u3044\u3066\n  if len(PQs[d_prv])>0:\n    while d_prv != S[PQs[d_prv][0][1]][1]:#\u6240\u5c5e\u304c\u6574\u5408\u3057\u3066\u3044\u306a\u3044\u6642\uff08\u53e4\u304f\u9593\u9055\u3063\u305f\u60c5\u5831\u3067\u3042\u308b\u6642\uff09\n      heappop(PQs[d_prv])\n      if len(PQs[d_prv]) == 0:\n        break\n        \n    if len(PQs[d_prv]) > 0 and -PQs[d_prv][0][0] < S[c-1][0]:  \n      heappush(M,(-PQs[d_prv][0][0],d_prv,q))\n      \n    if len(PQs[d_prv]) == 0 or -PQs[d_prv][0][0] < S[c-1][0]:\n      T[d_prv] = q #\u6700\u7d42\u66f4\u65b0\u6642\u3092\u30a2\u30c3\u30d7\u30c7\u30fc\u30c8\n \t\n  #\u6700\u5f37\u5712\u5150\u306e\u96c6\u3044\u3092\u51e6\u7406\n  while M[0][2] != T[M[0][1]]:#\u66f4\u65b0\u6642\u304c\u6574\u5408\u3057\u3066\u3044\u306a\u3044\u6642\uff08\u53e4\u304f\u9593\u9055\u3063\u305f\u60c5\u5831\u3067\u3042\u308b\u6642\uff09\n    heappop(M)\n  \n  ans.append(M[0][0])\n  \n\n  \n#\u7d50\u679c\u306e\u51fa\u529b\nprint(('\\n'.join(map(str, ans))))\n\n", "import heapq\n\n#getIntList = list(map(int, input.split()))\n#getFloatList = list(map(float, input.split()))\n\nMAXEN = 2*(10**5) + 5\nN, Q = list(map(int, input().split()))\nkid = [0]\nen = [0]\nentop = [[] for _ in range(MAXEN)]\nalltop = []\naddAllList = []\nrmvAllList = []\nfor i in range(N):\n    a, b = list(map(int, input().split()))\n    kid.append(a)\n    en.append(b)\n    #push to heap\n    heapq.heappush(entop[b], -a)\n\nfor e in range(MAXEN):\n    if entop[e]:\n        vv = entop[e][0]\n        heapq.heappush(alltop, -vv)\naddlist = [[] for _ in range(MAXEN)]\nrmvlist = [[] for _ in range(MAXEN)]\n\n\ndef updateEn(enID):\n    # is it larger than top of enID?\n    while len(addlist[enID]) > 0:\n        add_top = addlist[enID][0]\n        needAddNow = True\n        if len(rmvlist[enID]) > 0:\n            needAddNow = True\n        elif entop[enID]:\n            entop_old = entop[enID][0]\n            needAddNow = add_top < entop_old\n\n        if needAddNow:\n            heapq.heappush(entop[enID], add_top)\n            heapq.heappop(addlist[enID])\n        else:\n            break\n\n    # is it top of enID?\n    while (len(entop[enID]) > 0) and (len(rmvlist[enID]) > 0):\n        rmv_top = rmvlist[enID][0]\n        entop_old = entop[enID][0]\n        if rmv_top == entop_old:\n            heapq.heappop(entop[enID])\n            heapq.heappop(rmvlist[enID])\n        else:\n            break\n\n#query\nfor q in range(Q):\n    c, d = list(map(int, input().split()))\n    old_en = en[c]\n    new_en = d\n    en[c] = new_en\n\n    #add to rmvlist\n    heapq.heappush(rmvlist[old_en], -kid[c])\n    #add to addlist\n    heapq.heappush(addlist[new_en], -kid[c])\n\n    if len(entop[old_en]) > 0:\n        entop_old0 = entop[old_en][0]\n    else: entop_old0 = 0\n    if len(entop[new_en]) > 0:\n        entop_new0 = entop[new_en][0]\n    else: entop_new0 = 0\n\n    updateEn(new_en)\n    updateEn(old_en)\n    # #is it larger than top of new_en?\n    # while (len(entop[new_en]) > 0) and (len(addlist[new_en]) > 0):\n    #     add_top = addlist[new_en][0]\n    #     entop_old = entop[new_en][0]\n    #     if add_top < entop_old:\n    #         heapq.heappush(entop[new_en], add_top)\n    #         heapq.heappop(addlist[new_en])\n    #     else:\n    #         break\n    #\n    # #is it top of old_en?\n    # while (len(entop[old_en]) > 0) and (len(rmvlist[old_en]) > 0):\n    #     rmv_top = rmvlist[old_en][0]\n    #     entop_old = entop[old_en][0]\n    #     if rmv_top == entop_old:\n    #         heapq.heappop(entop[old_en])\n    #         heapq.heappop(rmvlist[old_en])\n    #     else:\n    #         break\n\n    if len(entop[old_en]) > 0:\n        entop_old1 = entop[old_en][0]\n    else: entop_old1 = 0\n    if entop_old0 != entop_old1:#changed?\n        if entop_old0 != 0: heapq.heappush(rmvAllList, -entop_old0)\n        if entop_old1 != 0: heapq.heappush(addAllList, -entop_old1)\n\n    if len(entop[new_en]) > 0:\n        entop_new1 = entop[new_en][0]\n    else: entop_new1 = 0\n    if entop_new0 != entop_new1:#changed?\n        if entop_new0 != 0: heapq.heappush(rmvAllList, -entop_new0)\n        if entop_new1 != 0: heapq.heappush(addAllList, -entop_new1)\n\n    #is it smaller than top of alltop?\n    while len(addAllList) > 0:\n        add_top = addAllList[0]\n        if (len(alltop) == 0) or (add_top < alltop[0]) or (len(rmvAllList) > 0):\n            heapq.heappush(alltop, add_top)\n            heapq.heappop(addAllList)\n        else:\n            break\n\n    #is it top of alltop?\n    while len(rmvAllList) > 0:\n        rmvTopV = rmvAllList[0]\n        if rmvTopV == alltop[0]:\n            heapq.heappop(alltop)\n            heapq.heappop(rmvAllList)\n        else:\n            break\n\n    print((alltop[0]))\n\n", "import sys\nimport numpy as np\nfrom heapq import heappush, heappop \nfrom bisect import bisect_left as bi_l, bisect_right as bi_r\nfrom collections import deque, Counter, defaultdict\nfrom itertools import combinations, product\ninf = float('inf')\nMOD = 10**9+7\n# MOD = 998244353\n\n\nclass NumberTheory():\n  def __init__(self, n=2*10**6, numpy=True):\n    self.n = n\n    self.np_flg = numpy \n    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)\n  \n  def sieve_of_eratosthenes(self, n):\n    if self.np_flg:\n      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0\n      for i in range(2, int(n**.5)+1):\n        if sieve[i]: sieve[i*2::i] = 0\n      prime_numbers = np.flatnonzero(sieve)\n    else:\n      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0\n      for i in range(2, int(n**.5)+1):\n        if not sieve[i]: continue\n        for j in range(i*2, n+1, i): sieve[j] = 0\n      prime_numbers = [i for i in range(2, n+1) if sieve[i]]\n    return sieve, prime_numbers \n\n  def prime_factorize(self, n):\n    res = dict()\n    if n < 2: return res\n    border = int(n**.5)\n    for p in self.prime_numbers:\n      if p > border: break\n      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p\n      if n == 1: return res\n    res[n] = 1; return res\n\n  def prime_factorize_factorial(self, n):\n    res = dict()\n    for i in range(2, n+1):\n      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c\n    return res\n  \n  @staticmethod\n  def gcd(a, b): return gcd(b, a%b) if b else abs(a)\n\n  @staticmethod\n  def lcm(a, b): return abs(a // gcd(a, b) * b)\n\n  @staticmethod\n  def find_divisors(n):\n    divisors = []\n    for i in range(1, int(n**.5)+1):\n      if n%i: continue\n      divisors.append(i)\n      j = n // i\n      if j != i: divisors.append(j)\n    return divisors\n  \n  @staticmethod\n  def base_convert(n, b): # return string\n    if not n: return '0'\n    res = ''\n    while n:\n      n, r = divmod(n, b)\n      if r < 0: n += 1; r -= b\n      res += str(r)\n    return res[::-1]\n\n\nclass UnionFind():\n  def __init__(self, n=10**6):\n    self.root = list(range(n))\n    self.height = [0] * n \n    self.size = [1] * n \n  \n  def find_root(self, u):\n    if self.root[u] == u: return u\n    self.root[u] = self.find_root(self.root[u])\n    return self.root[u]\n  \n  def unite(self, u, v):\n    ru = self.find_root(u)\n    rv = self.find_root(v)\n    if ru == rv: return \n    hu = self.height[ru]\n    hv = self.height[rv]\n    if hu >= hv:\n      self.root[rv] = ru \n      self.size[ru] += self.size[rv]\n      self.height[ru] = max(hu, hv+1)\n    else:\n      self.root[ru] = rv \n      self.size[rv] += self.size[ru]\n\n\nclass Combinatorics():\n  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):\n    self.mod = mod\n    self.nCr = dict()\n    self.np_flg=numpy\n    self.make_mod_tables(N, n)\n\n  sys.setrecursionlimit(10**6)\n  def choose(self, n, r, mod=None): # no mod, or mod \u2260 prime\n    if r > n or r < 0: return 0\n    if r == 0: return 1\n    if (n, r) in self.nCr: return self.nCr[(n, r)]\n    if not mod:\n      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))\n    else:\n      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod\n    return self.nCr[(n,r)]\n  \n  def cumprod(self, a):\n    p = self.mod\n    l = len(a); sql = int(np.sqrt(l)+1)\n    a = np.resize(a, sql**2).reshape(sql, sql)\n    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p\n    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p\n    return np.ravel(a)[:l]\n\n  def make_mod_tables(self, N, n):\n    p = self.mod\n    if self.np_flg:\n      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)\n      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)\n      ifac = self.cumprod(ifac)[n::-1]\n      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;\n      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p\n    else:\n      fac = [None]*(n+1); fac[0] = 1\n      for i in range(n): fac[i+1] = fac[i]*(i+1)%p\n      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)\n      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p\n      n_choose = [None] * (n+1); n_choose[0] = 1\n      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p\n      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p\n    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose\n\n\ndef z_algorithm(s):\n  n = len(s)\n  a = [0] * n; a[0] = n\n  l = r = -1\n  for i in range(1, n):\n    if r >= i: a[i] = min(a[i-l], r-i)\n    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1\n    if i+a[i] >= r: l, r = i, i+a[i]\n  return a\n\n\nclass ABC001():\n  def A():\n    h1, h2 = map(int, sys.stdin.read().split())\n    print(h1-h2)\n\n  def B(): pass\n  def C(): pass \n  def D(): pass \n\n\nclass ABC002():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(max(x, y))\n\n  def B():\n    vowels = set('aeiou')\n    s = sys.stdin.readline().rstrip() \n    t = ''\n    for c in s:\n      if c in vowels: continue \n      t += c \n    print(t)\n\n  def C():\n    *coords, = map(int, sys.stdin.readline().split())\n    def triangle_area(x0, y0, x1, y1, x2, y2):\n      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;\n      return abs(x1*y2 - x2*y1) / 2\n    print(triangle_area(*coords))\n\n  def D():\n    n, m = map(int, sys.stdin.readline().split())\n    edges = set()\n    for _ in range(m):\n      x, y = map(int, sys.stdin.readline().split())\n      x -= 1; y -= 1\n      edges.add((x, y))\n    cand = []\n    for i in range(1, 1<<n):\n      s = [j for j in range(n) if i>>j & 1]\n      for x, y in combinations(s, 2):\n        if (x, y) not in edges: break\n      else:\n        cand.append(len(s))\n    print(max(cand))\n\n\nclass ABC003():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)*5000)\n\n  def B():\n    atcoder = set('atcoder')\n    s, t = sys.stdin.read().split()\n    for i in range(len(s)):\n      if s[i] == t[i]: continue\n      if s[i] == '@' and t[i] in atcoder: continue \n      if t[i] == '@' and s[i] in atcoder: continue\n      print('You will lose')\n      return \n    print('You can win')\n\n  def C():\n    n, k, *r = map(int, sys.stdin.read().split())\n    res = 0\n    for x in sorted(r)[-k:]:\n      res = (res+x) / 2\n    print(res)\n\n  def D(): pass \n\n\nclass ABC004():\n  def A():\n    print(int(sys.stdin.readline().rstrip())*2)\n\n  def B():\n    c = [sys.stdin.readline().rstrip() for _ in range(4)]\n    for l in c[::-1]:\n      print(l[::-1])\n\n  def C():\n    n = int(sys.stdin.readline().rstrip())\n    n %= 30\n    res = list(range(1, 7))\n    for i in range(n):\n      i %= 5\n      res[i], res[i+1] = res[i+1], res[i]\n    print(''.join(map(str, res)))\n\n  def D(): pass \n\n\nclass ABC005():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(y//x)\n\n  def B():\n    n, *t = map(int, sys.stdin.read().split())\n    print(min(t))\n\n  def C():\n    t = int(sys.stdin.readline().rstrip())\n    n = int(sys.stdin.readline().rstrip())\n    a = [int(x) for x in sys.stdin.readline().split()]\n    m = int(sys.stdin.readline().rstrip())\n    b = [int(x) for x in sys.stdin.readline().split()]\n    i = 0\n    for p in b:\n      if i == n: print('no'); return \n      while p-a[i] > t:\n        i += 1\n        if i == n: print('no'); return \n      if a[i] > p: print('no'); return \n      i += 1\n    print('yes')\n\n  def D():\n    n = int(sys.stdin.readline().rstrip())\n    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)\n    s = d.cumsum(axis=0).cumsum(axis=1)\n    s = np.pad(s, 1)\n    max_del = np.zeros((n+1, n+1), dtype=np.int64)\n    for y in range(1, n+1):\n      for x in range(1, n+1):\n        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])\n    res = np.arange(n**2+1)[:, None]\n    i = np.arange(1, n+1)\n    res = max_del[i, np.minimum(res//i, n)].max(axis=1)\n    q = int(sys.stdin.readline().rstrip())\n    p = np.array(sys.stdin.read().split(), dtype=np.int64)\n    print(*res[p], sep='\\n')\n\n\nclass ABC006():\n  def A():\n    n = sys.stdin.readline().rstrip()\n    if '3' in n: print('YES')\n    elif int(n)%3 == 0: print('YES')\n    else: print('NO')\n\n  def B():\n    mod = 10007\n    t = [0, 0, 1]\n    for _ in range(1001001):\n      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod\n    n = int(sys.stdin.readline().rstrip())\n    print(t[n-1])\n    \n  def C():\n    n, m = map(int, sys.stdin.readline().split())\n    cnt = [0, 0, 0]\n    if m == 1: cnt = [-1, -1, -1]\n    else:\n      if m & 1: m -= 3; cnt[1] += 1; n -= 1\n      cnt[2] = m//2 - n \n      cnt[0] = n - cnt[2]\n    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)\n    else: print(*cnt, sep=' ')\n      \n  def D():\n    n, *c = map(int, sys.stdin.read().split())\n    inf = float('inf')\n    lis = [inf]*n \n    for x in c: lis[bi_l(lis, x)] = x \n    print(n - bi_l(lis, inf))\n\n\nclass ABC007():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n-1)\n\n  def B():\n    s = sys.stdin.readline().rstrip()\n    if s == 'a': print(-1)\n    else: print('a')\n\n  def C():\n    r, c = map(int, sys.stdin.readline().split())\n    sy, sx = map(int, sys.stdin.readline().split())\n    gy, gx = map(int, sys.stdin.readline().split())\n    sy -= 1; sx -=1; gy -= 1; gx -= 1\n    maze = [sys.stdin.readline().rstrip() for _ in range(r)]\n    queue = deque([(sy, sx)])\n    dist = np.full((r, c), np.inf); dist[sy, sx] = 0\n    while queue:\n      y, x = queue.popleft()\n      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n        i += y; j += x\n        if maze[i][j] == '#' or dist[i, j] != np.inf: continue \n        dist[i, j] = dist[y, x] + 1\n        queue.append((i, j))\n    print(int(dist[gy, gx]))\n  \n  def D(): pass \n\n\nclass ABC008():\n  def A():\n    s, t = map(int, sys.stdin.readline().split())\n    print(t-s+1)\n\n  def B():\n    n, *s = sys.stdin.read().split()\n    res = defaultdict(int)\n    for name in s: res[name] += 1\n    print(sorted(res.items(), key=lambda x: x[1])[-1][0])\n\n  def C():\n    n, *a = map(int, sys.stdin.read().split())\n    a = np.array(a)\n    c = n - np.count_nonzero(a[:, None]%a, axis=1)\n    print(np.sum((c+1)//2/c))\n  \n  def D(): pass\n\nclass ABC009():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)//2)\n\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    print(sorted(set(a))[-2])\n    \n  def C():\n    n, k = map(int, sys.stdin.readline().split())\n    s = list(sys.stdin.readline().rstrip())\n    cost = [1]*n\n    r = k\n    for i in range(n-1):\n      q = []\n      for j in range(i+1, n):\n        if s[j] < s[i] and cost[i]+cost[j] <= r:\n          heappush(q, (s[j], cost[i]+cost[j], -j))\n      if not q: continue\n      _, c, j = heappop(q); j = -j \n      s[i], s[j] = s[j], s[i]\n      r -= c \n      cost[i] = cost[j] = 0\n    print(''.join(s))\n      \n  def D(): pass \n\n\nclass ABC010():\n  def A():\n    print(sys.stdin.readline().rstrip()+'pp')\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    tot = 0\n    for x in a:\n      c = 0 \n      while x%2==0 or x%3==2:\n        x -= 1\n        c += 1\n      tot += c\n    print(tot)\n\n  def C():\n    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())\n    x, y = np.array(xy).reshape(-1, 2).T\n    def dist(x1, y1, x2, y2):\n      return np.sqrt((x2-x1)**2 + (y2-y1)**2)\n    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'\n    print(ans)\n\n  def D(): pass \n\nclass ABC011():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n%12+1)\n\n  def B():\n    s = sys.stdin.readline().rstrip() \n    print(s[0].upper()+s[1:].lower())\n\n  def C():\n    n, *ng = map(int, sys.stdin.read().split())\n    ng = set(ng)\n    if n in ng: print('NO')\n    else:\n      r = 100\n      while n > 0:\n        if r == 0: print('NO'); return\n        for i in range(3, 0, -1):\n          if (n-i) in ng: continue \n          n -= i\n          r -= 1\n          break \n        else: print('NO'); return \n      print('YES')\n\n  def D(): pass \n\n\nclass ABC170():\n  def A():\n    x = [int(x) for x in sys.stdin.readline().split()]\n    for i in range(5):\n      if x[i] != i+1:\n        print(i+1)\n        break\n\n  def B():\n    x, y = map(int, sys.stdin.readline().split())\n    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')\n      \n  def C():\n    x, n, *p = map(int, sys.stdin.read().split())\n    a = list(set(range(102)) - set(p))\n    a = [(abs(y-x), y) for y in a]\n    print(sorted(a)[0][1])\n\n  def D():\n    n, *a = map(int, sys.stdin.read().split())\n    cand = set(a)\n    cnt = 0\n    for x, c in sorted(Counter(a).items()):\n      cnt += c == 1 and x in cand\n      cand -= set(range(x*2, 10**6+1, x))\n    print(cnt)\n\n\n  def E():\n    n, q = map(int, sys.stdin.readline().split())\n    queue = [] \n    num_kindergarten = 2*10**5\n    queue_kindergarten = [[] for _ in range(num_kindergarten)]\n    highest_kindergarten = [None] * num_kindergarten\n    where = [None] * n\n    rate = [None] * n\n\n    def entry(i, k):\n      where[i] = k\n      while queue_kindergarten[k]:\n        r, j = heappop(queue_kindergarten[k])\n        if where[j] != k or j == i: continue \n        if rate[i] >= -r:\n          highest_kindergarten[k] = rate[i]\n          heappush(queue, (rate[i], k, i))\n        heappush(queue_kindergarten[k], (r, j))\n        break\n      else:\n        highest_kindergarten[k] = rate[i]\n        heappush(queue, (rate[i], k, i))\n      heappush(queue_kindergarten[k], (-rate[i], i))\n\n    def transfer(i, k):\n      now = where[i]\n      # while queue_kindergarten[now]:\n      #   r, j = heappop(queue_kindergarten[now])\n      #   if where[j] == now: break\n      # if j != i:\n      #   heappush(queue_kindergarten[now], (r, j))\n      # else:\n      while queue_kindergarten[now]:\n        r, j = heappop(queue_kindergarten[now])\n        if where[j] != now or j == i: continue\n        if highest_kindergarten[now] != -r:\n          highest_kindergarten[now] = -r\n          heappush(queue, (-r, now, j))\n        heappush(queue_kindergarten[now], (r, j))\n        break\n      else:\n        highest_kindergarten[now] = None\n      entry(i, k)\n\n    def inquire():\n      while True:\n        r, k, i = heappop(queue)\n        if where[i] != k or r != highest_kindergarten[k]: continue \n        heappush(queue, (r, k, i))\n        return r\n\n    for i in range(n):\n      a, b = map(int, sys.stdin.readline().split())\n      rate[i] = a \n      entry(i, b-1)\n    for _ in range(q):\n      c, d = map(int, sys.stdin.readline().split())\n      transfer(c-1, d-1)\n      print(inquire())\n    \n\n  def F(): pass \n\ndef __starting_point():\n  ABC170.E()\n__starting_point()", "def solve():\n    from heapq import heappop, heappush\n    from collections import defaultdict\n    n, q = list(map(int, input().split()))\n    rates = [0] * (n + 1)\n    belong = [0] * (n + 1)\n    en = [[] for _ in range(2 * (10 ** 5) + 1)]\n    ob = [defaultdict(int) for _ in range(2 * (10 ** 5) + 1)]\n    res = []\n    res_gone = defaultdict(int)\n    ans = []\n    for i in range(1, n + 1):\n        a, b = list(map(int, input().split()))\n        rates[i] = a\n        belong[i] = b\n        heappush(en[b], -a)\n    for e in en:\n        if e:\n            x = -heappop(e)\n            heappush(res, x)\n            heappush(e, -x)\n    for i in range(q):\n        c, d = list(map(int, input().split()))\n        tmp = belong[c]\n        obr = rates[c]\n        ob[tmp][obr] += 1\n\n        ox_s = -heappop(en[tmp])\n        res_gone[ox_s] += 1\n        heappush(en[tmp], -ox_s)\n\n        if en[d]:\n            ox_m = -heappop(en[d])\n            res_gone[ox_m] += 1\n            heappush(en[d], -ox_m)\n\n        belong[c] = d\n        heappush(en[d], -rates[c])\n\n        nx_s = -heappop(en[tmp])\n        while ob[tmp][nx_s] != 0:\n            ob[tmp][nx_s] -= 1\n            nx_s = -heappop(en[tmp]) if en[tmp] else 0\n        if nx_s != 0:\n            heappush(res, nx_s)\n            heappush(en[tmp], -nx_s)\n\n        nx_m = -heappop(en[d])\n        heappush(res, nx_m)\n        heappush(en[d], -nx_m)\n\n        fair = heappop(res)\n        while res_gone[fair] != 0:\n            res_gone[fair] -= 1\n            fair = heappop(res)\n        ans.append(fair)\n        heappush(res, fair)\n    print((\"\\n\".join(map(str, ans))))\n\n\nsolve()\n", "import heapq\n\n\nclass HeapDict:\n    def __init__(self):\n        # heapq\u3068dict\u3092\u7528\u610f\n        self.h = []\n        self.d = dict()\n\n    def insert(self, x):\n        heapq.heappush(self.h, x)\n        if x not in self.d:\n            self.d[x] = 1\n        else:\n            self.d[x] += 1\n\n    def erase(self, x):\n        if x not in self.d or self.d[x] == 0:\n            print((x, \"is not in HeapDict\"))\n            return\n        else:\n            self.d[x] -= 1\n\n        while len(self.h) != 0:\n            if self.d[self.h[0]] == 0:\n                heapq.heappop(self.h)\n            else:\n                break\n\n    def is_exist(self, x):\n        if x in self.d and self.d[x] != 0:\n            return True\n        else:\n            False\n\n    def get_min(self):\n        return self.h[0]\n\n    def size(self):\n        return len(self.h)\n\n\ndef main():\n    N, Q = list(map(int, input().split()))\n    A = []  # \u30ec\u30fc\u30c8\n    B = []  # \u6240\u5c5e\u5e7c\u7a1a\u5712\n    con = 2 * 10 ** 5\n    INF = 10 ** 18\n    youchi = [HeapDict() for _ in range(con)]  # \u5404\u5e7c\u7a1a\u5712\u306b\u5bfe\u3059\u308bHeapDict\n    max_values = HeapDict()  # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u306eHeapDict\n    for i in range(N):\n        a, b = list(map(int, input().split()))\n        b -= 1\n        A.append(a)\n        B.append(b)\n        youchi[b].insert(-a)\n\n    for i in range(con):  # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u3092\u307e\u3068\u3081\u308b\n        if youchi[i].size() != 0:\n            max_values.insert(-youchi[i].get_min())\n        else:\n            max_values.insert(INF)\n\n    for i in range(Q):\n        c, d = list(map(int, input().split()))\n        c -= 1\n        d -= 1\n        rate = A[c]\n        youchi_now = B[c]\n        youchi_next = d\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b\n        max_values.erase(-youchi[youchi_now].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b\n        youchi[youchi_now].erase(-rate)\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b(\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044)\n        if youchi[youchi_now].size() != 0:\n            max_values.insert(-youchi[youchi_now].get_min())\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b(\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044)\n        if youchi[youchi_next].size() != 0:\n            max_values.erase(-youchi[youchi_next].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b\n        youchi[youchi_next].insert(-rate)\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b\n        max_values.insert(-youchi[youchi_next].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u306e\u756a\u53f7\u3092\u66f4\u65b0\u3059\u308b\n        B[c] = youchi_next\n\n        print((max_values.get_min()))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "def main():\n    import sys\n    input = lambda: sys.stdin.readline().rstrip(\"\\r\\n\")\n    mod = 10**9 + 7\n\n    ans = []\n\n    n, q = map(int, input().split())\n    y = [[] for _ in range(2*10**5)] # i\u756a\u76ee\u306e\u5e7c\u7a1a\u5712\u306e(-rate, \u5e7c\u5150)\n    data = [(0, 0)]*n # i\u756a\u76ee\u306e(rate, \u6240\u5c5e)\n    import heapq\n    for i in range(n):\n        a, b = map(int, input().split())\n        data[i] = (a, b - 1)\n        heapq.heappush(y[b - 1], (-a, i))\n    max_rate = [] # (rate, \u5e7c\u5150, \u6240\u5c5e)\n    max_rate_list = [()]*(2*10**5)\n    for i in range(2*10**5):\n        if y[i]:\n            s, t = heapq.heappop(y[i])\n            heapq.heappush(max_rate, (-s, t, i))\n            heapq.heappush(y[i], (s, t))\n            max_rate_list[i] = (-s, t)\n    from collections import defaultdict\n    ng_num = defaultdict(set)\n    for _ in range(q):\n        c, d = map(int, input().split())\n        c -= 1\n        d -= 1\n        a, b = data[c]\n        data[c] = (a, d)\n        heapq.heappush(y[d], (-a, c))\n        ng_num[b].add(c)\n        if c in ng_num[d]:\n            ng_num[d].discard(c)\n        #print(ng_num)\n        while y[b]:\n            s, t = heapq.heappop(y[b])\n            if t not in ng_num[b]:\n                heapq.heappush(max_rate, (-s, t, b))\n                heapq.heappush(y[b], (s, t))\n                max_rate_list[b] = (-s, t)\n                break\n        while y[d]:\n            s, t = heapq.heappop(y[d])\n            if t not in ng_num[d]:\n                heapq.heappush(max_rate, (-s, t, d))\n                heapq.heappush(y[d], (s, t))\n                max_rate_list[d] = (-s, t)\n                break\n        #print(max_rate) \n        while max_rate:\n            s, t, r = heapq.heappop(max_rate)\n            if t not in ng_num[r] and (s, t) == max_rate_list[r]:\n                ans.append(s)\n                heapq.heappush(max_rate, (s, t, r))\n                break\n    print(*ans, sep=\"\\n\")\nmain()\n\n\n\n\n", "import heapq\nn, q = map(int, input().split())\nbelong = [-1 for i in range(n)]\nrating = [0 for i in range(n)]\nsecond = [[] for i in range(2 * 10 ** 5 + 5)]\nfor i in range(n):\n    a, b = map(int, input().split())\n    rating[i] = a\n    belong[i] = b\n    heapq.heappush(second[b], (-1 * a, i))\nfirst = []\nfor i in range(2 * 10 ** 5 + 5):\n    if second[i]:\n        heapq.heappush(first, (-1 * second[i][0][0], second[i][0][1], i))\nfor i in range(q):\n    c, d = map(int, input().split())\n    before = belong[c - 1]\n    belong[c - 1] = d\n    heapq.heappush(second[d], (-1 * rating[c - 1], c - 1))\n    if second[d][0][1] == c - 1:\n        heapq.heappush(first, (rating[c - 1], c - 1, d))\n    count = 0\n    while second[before] and belong[second[before][0][1]] != before:\n        heapq.heappop(second[before])\n        count = 1\n    if count and second[before]:\n        heapq.heappush(first, (-1 * second[before][0][0], second[before][0][1], before))\n    while not second[first[0][2]] or second[first[0][2]][0][1] != first[0][1]:\n        heapq.heappop(first)\n    print(first[0][0])", "# E - Smart Infants\n\nimport heapq\nM = 2*(10**5)\nN, Q = list(map(int, input().split()))\nenji = []\nfor i in range(N):\n    enji.append(tuple(map(int, input().split())))\n\n# \u305d\u306e\u5712\u5150\u304c\u4eca\u3069\u3053\u306e\u5e7c\u7a1a\u5712\u306b\u3044\u308b\u304b\nbelong = [0] * N\n# \u5e7c\u7a1a\u5712K\u306e\u5712\u5150\u306e\u512a\u5148\u30ad\u30e5\u30fc\nK = [[] for _ in range(M)]\nfor i, (a, b) in enumerate(enji):\n    heapq.heappush(K[b-1], (-a, i))\n    belong[i] = b-1\n\n#print(K)\n\n# \u6700\u5f37\u5712\u5150\u306e\u512a\u5148\u30ad\u30e5\u30fc\nE = []\nfor i in range(M):\n    if K[i] != []:\n        heapq.heappush(E, (K[i][0][0]*-1, K[i][0][1], belong[K[i][0][1]]))\n\ndef insert_enji(x, y):\n    # \u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u4e2d\u3067\u6700\u5f37\u306b\u306a\u308c\u308b\u5834\u5408\n    if K[y] == [] or K[y][0][0] > enji[x][0]*-1:\n        heapq.heappush(K[y], (enji[x][0]*-1, x))\n        heapq.heappush(E, (K[y][0][0]*-1, K[y][0][1], belong[K[y][0][1]]))\n    else:\n        heapq.heappush(K[y], (enji[x][0]*-1, x))\n\ndef mainte_K(x, y):\n    flg = False\n    while K[y]:\n        if belong[K[y][0][1]] == y:\n            break\n        else:\n            heapq.heappop(K[y])\n            flg = True\n    if flg == True and K[y] != []:\n        heapq.heappush(E, (-K[y][0][0], K[y][0][1], y))\n            \ndef mainte_E():\n    while E:\n        if K[E[0][2]] != [] and K[E[0][2]][0] == (E[0][0] * -1, E[0][1]):\n            break\n        else:\n            heapq.heappop(E)\n\nfor i in range(Q):\n    c, d = list(map(int, input().split()))\n    c -= 1\n    d -= 1\n    old = belong[c]\n    belong[c] = d\n    insert_enji(c, d)\n    mainte_K(c, old)\n    mainte_E()\n    print((E[0][0]))\n", "import heapq\n\nN,Q=map(int,input().split())\n\nyochien={}\nrate={}\nenzi_rate={}\nenzi_rate_out={}\nresult=[]\n\nfor i in range(1,N+1):\n    A,B=map(int,input().split())\n\n    rate[i]=A\n    yochien[i]=B\n\n    if B not in enzi_rate:\n        enzi_rate[B]=[]\n    heapq.heappush(enzi_rate[B],-A)\n\n\nmax_enzi=[]\nheapq.heapify(max_enzi)\nmax_enzi_out=[]\nheapq.heapify(max_enzi_out)\n\nfor j in enzi_rate:\n    heapq.heappush(max_enzi,-enzi_rate[j][0])\n\nfor _ in range(Q):\n    C,D=map(int,input().split())\n\n    if yochien[C] not in enzi_rate_out:\n        enzi_rate_out[yochien[C]]=[]\n    heapq.heappush(enzi_rate_out[yochien[C]],-rate[C])\n    \n    if len(enzi_rate_out[yochien[C]])>=1 and enzi_rate_out[yochien[C]][0]==enzi_rate[yochien[C]][0]:\n        heapq.heappush(max_enzi_out,-enzi_rate_out[yochien[C]][0])\n        while len(enzi_rate_out[yochien[C]])>=1 and enzi_rate_out[yochien[C]][0]==enzi_rate[yochien[C]][0]:\n            heapq.heappop(enzi_rate_out[yochien[C]])\n            heapq.heappop(enzi_rate[yochien[C]])\n        if len(enzi_rate[yochien[C]])>=1:\n            heapq.heappush(max_enzi,-enzi_rate[yochien[C]][0])\n    \n    yochien[C]=D\n\n    if D not in enzi_rate or len(enzi_rate[D])==0:\n        enzi_rate[D]=[]\n        heapq.heappush(max_enzi,rate[C])\n    elif -enzi_rate[D][0]<rate[C]:\n        heapq.heappush(max_enzi,rate[C])\n        heapq.heappush(max_enzi_out,-enzi_rate[D][0])\n    \n    heapq.heappush(enzi_rate[D],-rate[C])\n    \n    while len(max_enzi_out)>=1 and max_enzi[0]==max_enzi_out[0]:\n        heapq.heappop(max_enzi)\n        heapq.heappop(max_enzi_out)\n    \n    result.append(max_enzi[0])\n\nfor k in range(Q):\n    print(result[k])", "import sys\nreadline = sys.stdin.readline\n\nimport heapq as hq\n\nN,Q = list(map(int,readline().split()))\nNN = 2 * (10 ** 5)\n\n# (\u30ec\u30fc\u30c8, \u6240\u5c5e\u5712)\ninfants = [None] * (N + 1)\n# (\u6700\u5f37\u5712\u5150, \u5712\u5150\u756a\u53f7)\nkinda = [[] for i in range(NN + 1)]\nfor i in range(N):\n  a,b = list(map(int,readline().split()))\n  infants[i + 1] = [a,b]\n  hq.heappush(kinda[b], (-a, i + 1))\n\n# (\u6700\u5f31\u5712\u5150, \u5712\u306e\u756a\u53f7)\nall_kinda = []\nfor i in range(len(kinda)):\n  if kinda[i]:\n    hq.heappush(all_kinda, (-kinda[i][0][0], i))\n  \ndef get_max_rate(x): # \u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u53d6\u308a\u51fa\u3059\n  q = kinda[x]\n  while q:\n    rate, ind = q[0]\n    if infants[ind][1] != x:\n      hq.heappop(q)\n      continue\n    return -rate\n  return -1\n  \nfor i in range(Q):\n  ind,next_kinda_id = list(map(int,readline().split()))\n  rate,old_kinda_id = infants[ind]\n  infants[ind][1] = next_kinda_id\n  hq.heappush(kinda[next_kinda_id],(-rate, ind))\n  \n  old_kinda_max_rate = get_max_rate(old_kinda_id)\n  if old_kinda_max_rate != -1:\n    hq.heappush(all_kinda, (old_kinda_max_rate, old_kinda_id))\n    \n  next_kinda_max_rate = get_max_rate(next_kinda_id)\n  if next_kinda_max_rate != -1:\n    hq.heappush(all_kinda, (next_kinda_max_rate, next_kinda_id))\n\n  while all_kinda:\n    rate, kinda_id = all_kinda[0]\n    if rate != get_max_rate(kinda_id):\n      hq.heappop(all_kinda)\n      continue\n    print(rate)\n    break\n", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t,_ in x:t and f(l,-t[0])\nfor c,d in z[n:]:\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)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y[0]<t:f(l,a);t and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "# codekata from https://atcoder.jp/contests/abc170/submissions/14456317\n# by puzzlesolver\n\nimport sys\nimport heapq\n\n\ninput = sys.stdin.readline\n\ndef main():\n\n    N, Q = [int(x) for x in input().split()]\n\n    hsize = 2 * 10 ** 5 + 1\n\n    h = [[] for _ in range(hsize)]\n\n    # \u5712\u5150\u304c\u73fe\u5728\u6240\u5c5e\u3057\u3066\u3044\u308b\u5e7c\u7a1a\u5712\u3092\u4fdd\u5b58\n    C = [0] * N\n    A = []\n\n    for i in range(N):\n        a, b = [int(x) for x in input().split()]\n        A.append(a)\n        heapq.heappush(h[b], (-a, i))\n        C[i] = b\n\n    A = tuple(A)\n\n    byodo = []\n\n    for i in range(1, hsize):\n        if len(h[i]) == 0:\n            continue\n\n        # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u3092byodo\u306b\u5165\u308c\u308b\n\n        x = h[i][0]\n        heapq.heappush(byodo, (-x[0], x[1]))\n\n    ans = []\n    for _ in range(Q):\n        c, d = [int(x) for x in input().split()]\n        c -= 1\n\n        # \u79fb\u52d5\u5143\u6700\u5927\u5024\u30c1\u30a7\u30c3\u30af\n        cfrom = C[c]\n        # c\u5712\u5150\u306e\u73fe\u5728\u6642\u3092d\u306b\u66f4\u65b0\n        C[c] = d\n\n        while h[cfrom]:\n            x = h[cfrom][0]\n            # \u6700\u5927\u5024\u306e\u5712\u5150\u306e\u73fe\u5728\u306e\u6240\u5c5e\u5e7c\u7a1a\u5712\u304cC[c]\u3068\u7570\u306a\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            if C[x[1]] != cfrom:\n                heapq.heappop(h[cfrom])\n                continue\n\n            # \u73fe\u5728\u306e\u6700\u5927\u5024\u3092\u5e73\u7b49\u306bpush\n            heapq.heappush(byodo, (-x[0], x[1]))\n            break\n\n        # c\u5712\u5150\u3092d\u5e7c\u7a1a\u5712\u306bpush\n        heapq.heappush(h[d], (-A[c], c))\n\n        # \u79fb\u52d5\u5148\u6700\u5927\u5024\u30c1\u30a7\u30c3\u30af\n        while h[d]:\n            x = h[d][0]\n            # \u6700\u5927\u5024\u306e\u5712\u5150\u306e\u73fe\u5728\u306e\u6240\u5c5e\u5e7c\u7a1a\u5712\u304cd\u3068\u7570\u306a\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            if C[x[1]] != d:\n                heapq.heappop(h[d])\n                continue\n\n            # \u73fe\u5728\u306e\u6700\u5927\u5024\u3092byodo\u306bpush\n            heapq.heappush(byodo, (-x[0], x[1]))\n            break\n\n        # \u5e73\u7b49\u306e\u6700\u5c0f\u5024\u3092\u53d6\u5f97\n\n        while byodo:\n            x = byodo[0]\n\n\n            # \u6700\u5c0f\u5024\u304c\u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u304c\u7570\u306a\u3063\u3066\u3044\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            y = h[C[x[1]]][0]\n            if -y[0] != x[0]:\n                heapq.heappop(byodo)\n                continue\n\n            ans.append(x[0])\n            break\n\n    print(('\\n'.join(map(str, ans))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import *\nMAX=2*10**5+1\n\nN,Q=list(map(int,input().split()))\n\nI=[[] for _ in range(N+1)]\nP=[[[],[]] for _ in range(MAX)]\nS=[[],[]]\n\ndef heapdel(l,a):\n  if l[0][0]==a:\n    heappop(l[0])\n    while l[1] and l[1][0]==l[0][0]:\n      heappop(l[1])\n      heappop(l[0])\n  else:\n    heappush(l[1],a)\n\ndef heapadd(l,a):\n  heappush(l[0],a)\n\ndef heapmin(l):\n  return l[0][0]\n\ndef main():\n  for i in range(1,N+1):\n    a,b=list(map(int,input().split()))\n    I[i]+=[a,b]\n    heapadd(P[b],-a)\n\n  for i in range(1,MAX):\n    if P[i][0]:\n      heapadd(S,-heapmin(P[i]))\n\n  for i in range(Q):\n    c,d=list(map(int,input().split()))\n    a,b=I[c]\n\n    heapdel(S,-heapmin(P[b]))\n    heapdel(P[b],-a)\n    if P[b][0]:\n      heapadd(S,-heapmin(P[b]))\n\n    if P[d][0]:\n      heapdel(S,-heapmin(P[d]))\n    heapadd(P[d],-a)\n    heapadd(S,-heapmin(P[d]))\n\n    I[c][1]=d\n    print((heapmin(S)))\n\nmain()\n", "def main():\n    import sys\n    def input(): return sys.stdin.readline().rstrip()\n    n, q = map(int, input().split())\n    from collections import defaultdict\n    from heapq import heappush, heappop\n    # \u5e7c\u7a1a\u5712\u3054\u3068\u306e\u5712\u5150\u30ea\u30b9\u30c8\u3092\u30d2\u30fc\u30d7\u3067\u683c\u7d0d\n    h = defaultdict(lambda: [])\n    # \u5e7c\u7a1a\u5712\u5f8c\u306e\u6700\u5f37\u5712\u5150\u3092\u683c\u7d0d\n    saikyo = []\n    A, B = [], []\n    for i in range(n):\n        a, b = map(int, input().split())\n        A.append(a)\n        B.append(b)\n        heappush(h[b], (-a, i)) \n    for i in h:\n        x = h[i][0]\n        heappush(saikyo, (-x[0], x[1]))       \n    for i in range(q):\n        c, d = map(int, input().split())\n        c -= 1\n        # \u8ee2\u5712\u51e6\u7406\n        cfrom = B[c]\n        B[c] = d\n        # \u79fb\u52d5\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30c1\u30a7\u30c3\u30af\n        while h[cfrom]:\n            x = h[cfrom][0]\n            if B[x[1]] != cfrom:\n                heappop(h[cfrom])\n                continue \n            heappush(saikyo,(-x[0],x[1]))\n            break\n        heappush(h[d],(-A[c],c))\n        # \u79fb\u52d5\u5148\u306e\u6700\u5f37\u5712\u5150\u30c1\u30a7\u30c3\u30af\n        while h[d]:\n            x = h[d][0]\n            if B[x[1]] != d:\n                heappop(h[d])\n                continue\n            heappush(saikyo,(-x[0],x[1]))\n            break\n\n        # saikyo\u306e\u6700\u5c0f\u5024\u3092\u6c42\u3081\u308b\u3002\n        while saikyo:\n            x = saikyo[0]\n\n            y = h[B[x[1]]][0]\n            if -y[0] != x[0]:\n                heappop(saikyo)\n                continue\n            print(x[0])\n            break\n    \n    print()\ndef __starting_point():\n    main()\n__starting_point()", "import heapq\n\nymax = 200000\nN, Q  = list(map(int, input().split()))\n\nyo = [[] for i in range(ymax+1)]\nym = []\nAB = [(0,0)]\n\nfor i in range(N):\n  A, B  = list(map(int, input().split()))\n  AB.append( (A, B) )\n  heapq.heappush(yo[B],(-A,i+1))\n#\nfor i in range(1,ymax+1):\n  if yo[i]:\n    mA, c = yo[i][0]\n    heapq.heappush(ym,(-mA,c,i)) \n#\nfor i in range(Q):\n  C, D  = list(map(int, input().split()))\n  A, B = AB[C]\n  AB[C] = (A, D)\n\n  if  yo[B][0][1] == C:\n    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):\n      heapq.heappop(yo[B])\n    if yo[B]:\n      mA, c = yo[B][0]\n      heapq.heappush(ym,(-mA,c,B)) \n#\n  heapq.heappush(yo[D],(-A,C))\n  mA, c = yo[D][0]\n  if c == C:\n    heapq.heappush(ym,(-mA,c,D)) \n#\n  while ym:\n    if AB[ ym[0][1] ][1] != ym[0][2]:\n      heapq.heappop(ym)\n    elif ym[0][1] != yo[ ym[0][2] ][0][1] :\n      heapq.heappop(ym)\n    else:\n      break\n#      \n  print((ym[0][0]))\n#\n", "import heapq\n\nymax = 200000\nN, Q = list(map(int, input().split()))\n\nyo = [[] for i in range(ymax+1)]\nym = []\nAB = [(0,0)]\ns = set()\n\nfor i in range(N):\n  A, B = list(map(int, input().split()))\n  AB.append((A,B))\n  heapq.heappush(yo[B], (-A,i+1))\n  s.add(B)\nfor i in s:\n  mA, c = yo[i][0]\n  heapq.heappush(ym,(-mA,c,i))\nfor i in range(Q):\n  C, D = list(map(int, input().split()))\n  A, B = AB[C]\n  AB[C] = (A, D)\n  \n  if yo[B][0][1] == C:\n    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):\n      heapq.heappop(yo[B])\n    if yo[B]:\n      mA, c = yo[B][0]\n      heapq.heappush(ym,(-mA,c,B))\n  heapq.heappush(yo[D],(-A,C))\n  mA, c = yo[D][0]\n  if c == C:\n    heapq.heappush(ym,(-mA,c,D))\n\n  while ym:\n    if AB[ ym[0][1] ][1] != ym[0][2]:\n      heapq.heappop(ym)\n    elif ym[0][1] != yo[ ym[0][2] ][0][1]:\n      heapq.heappop(ym)\n    else:\n      break\n  print((ym[0][0]))\n", "import heapq\nimport sys\ninput = sys.stdin.readline\n\nclass HeapDict:\n    def __init__(self):\n        self.h = []\n        self.d = {}\n\n    def insert(self,x):\n        if x not in self.d or self.d[x] == 0:\n            heapq.heappush(self.h, x)\n        self.d.setdefault(x,0)\n        self.d[x] += 1\n\n\n    def erase(self,x):\n        if x not in self.d or self.d[x] == 0:\n            return\n        else:\n            self.d[x] -= 1\n\n        while self.h:\n            if self.d[self.h[0]] == 0:\n                heapq.heappop(self.h)\n            else:\n                break\n\n\n    def get_min(self):\n        return self.h[0]\n\n\n    def pop(self):\n        poped_val = self.h[0]\n        self.erase(poped_val)\n        return poped_val\n\n\n    def exist(self, x):\n        return (x in self.d and self.d[x] > 0)\n\n\n    def show_h(self):\n        elems = [v for v in self.h if self.d[v] > 0]\n        print(elems)\n\n\n    def show_d(self):\n        print(self.d)\n\n\n\ndef main():\n    n,q = map(int, input().split())\n    kid_rates = [0]*(n+1)\n    kid_kinders = [0]*(n+1)\n    kinder_kid_rates = [HeapDict() for _ in range(2*(10**5)+1)]\n    for i in range(n):\n        ind = i+1\n        a,b = map(int, input().split())\n        kid_rates[ind] = a\n        kid_kinders[ind] = b\n        kinder_kid_rates[b].insert((a*(-1),ind))\n    \n    each_kinder_rate_maxs = HeapDict()\n    for i, kkr in enumerate(kinder_kid_rates):\n        if kkr.h:\n            kkr_max = kkr.get_min()\n            each_kinder_rate_maxs.insert( (kkr_max[0]*(-1), kkr_max[1], i) ) # max_rate, kid_index, kinder_index\n\n    cdl = []\n    for _ in range(q):\n        c,d = map(int, input().split())\n        cdl.append((c,d))\n\n    for cd in cdl:\n        c,d = cd\n        to_kinder = d\n        kid_rate = kid_rates[c]\n        from_kinder = kid_kinders[c]\n\n        from_kinder_max_rate = kinder_kid_rates[from_kinder].get_min()      \n        each_kinder_rate_maxs.erase( (from_kinder_max_rate[0]*(-1), from_kinder_max_rate[1], from_kinder) )\n\n        kinder_kid_rates[from_kinder].erase( (kid_rate*(-1), c) )\n\n        if kinder_kid_rates[from_kinder].h:\n            new_max_rate = kinder_kid_rates[from_kinder].get_min()\n            each_kinder_rate_maxs.insert( (new_max_rate[0]*(-1), new_max_rate[1], from_kinder) )\n\n        if kinder_kid_rates[to_kinder].h:\n            to_kinder_max_rate = kinder_kid_rates[to_kinder].get_min()      \n            each_kinder_rate_maxs.erase( (to_kinder_max_rate[0]*(-1), to_kinder_max_rate[1], to_kinder) )\n\n        kinder_kid_rates[to_kinder].insert( (kid_rate*(-1), c) )\n        new_to_kinder_max_rate = kinder_kid_rates[to_kinder].get_min()\n        each_kinder_rate_maxs.insert( (new_to_kinder_max_rate[0]*(-1), new_to_kinder_max_rate[1], to_kinder) )\n\n        print(each_kinder_rate_maxs.get_min()[0])\n        kid_kinders[c] = to_kinder\n\n\ndef __starting_point():\n    main()\n__starting_point()", "import sys\nimport numpy as np\nfrom heapq import heappush, heappop \nfrom bisect import bisect_left as bi_l, bisect_right as bi_r\nfrom collections import deque, Counter, defaultdict\nfrom itertools import combinations, product\ninf = float('inf')\nMOD = 10**9+7\n# MOD = 998244353\n\n\nclass NumberTheory():\n  def __init__(self, n=2*10**6, numpy=True):\n    self.n = n\n    self.np_flg = numpy \n    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)\n  \n  def sieve_of_eratosthenes(self, n):\n    if self.np_flg:\n      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0\n      for i in range(2, int(n**.5)+1):\n        if sieve[i]: sieve[i*2::i] = 0\n      prime_numbers = np.flatnonzero(sieve)\n    else:\n      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0\n      for i in range(2, int(n**.5)+1):\n        if not sieve[i]: continue\n        for j in range(i*2, n+1, i): sieve[j] = 0\n      prime_numbers = [i for i in range(2, n+1) if sieve[i]]\n    return sieve, prime_numbers \n\n  def prime_factorize(self, n):\n    res = dict()\n    if n < 2: return res\n    border = int(n**.5)\n    for p in self.prime_numbers:\n      if p > border: break\n      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p\n      if n == 1: return res\n    res[n] = 1; return res\n\n  def prime_factorize_factorial(self, n):\n    res = dict()\n    for i in range(2, n+1):\n      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c\n    return res\n  \n  @staticmethod\n  def gcd(a, b): return gcd(b, a%b) if b else abs(a)\n\n  @staticmethod\n  def lcm(a, b): return abs(a // gcd(a, b) * b)\n\n  @staticmethod\n  def find_divisors(n):\n    divisors = []\n    for i in range(1, int(n**.5)+1):\n      if n%i: continue\n      divisors.append(i)\n      j = n // i\n      if j != i: divisors.append(j)\n    return divisors\n  \n  @staticmethod\n  def base_convert(n, b): # return string\n    if not n: return '0'\n    res = ''\n    while n:\n      n, r = divmod(n, b)\n      if r < 0: n += 1; r -= b\n      res += str(r)\n    return res[::-1]\n\n\nclass UnionFind():\n  def __init__(self, n=10**6):\n    self.root = list(range(n))\n    self.height = [0] * n \n    self.size = [1] * n \n  \n  def find_root(self, u):\n    if self.root[u] == u: return u\n    self.root[u] = self.find_root(self.root[u])\n    return self.root[u]\n  \n  def unite(self, u, v):\n    ru = self.find_root(u)\n    rv = self.find_root(v)\n    if ru == rv: return \n    hu = self.height[ru]\n    hv = self.height[rv]\n    if hu >= hv:\n      self.root[rv] = ru \n      self.size[ru] += self.size[rv]\n      self.height[ru] = max(hu, hv+1)\n    else:\n      self.root[ru] = rv \n      self.size[rv] += self.size[ru]\n\n\nclass Combinatorics():\n  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):\n    self.mod = mod\n    self.nCr = dict()\n    self.np_flg=numpy\n    self.make_mod_tables(N, n)\n\n  sys.setrecursionlimit(10**6)\n  def choose(self, n, r, mod=None): # no mod, or mod \u2260 prime\n    if r > n or r < 0: return 0\n    if r == 0: return 1\n    if (n, r) in self.nCr: return self.nCr[(n, r)]\n    if not mod:\n      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))\n    else:\n      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod\n    return self.nCr[(n,r)]\n  \n  def cumprod(self, a):\n    p = self.mod\n    l = len(a); sql = int(np.sqrt(l)+1)\n    a = np.resize(a, sql**2).reshape(sql, sql)\n    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p\n    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p\n    return np.ravel(a)[:l]\n\n  def make_mod_tables(self, N, n):\n    p = self.mod\n    if self.np_flg:\n      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)\n      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)\n      ifac = self.cumprod(ifac)[n::-1]\n      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;\n      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p\n    else:\n      fac = [None]*(n+1); fac[0] = 1\n      for i in range(n): fac[i+1] = fac[i]*(i+1)%p\n      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)\n      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p\n      n_choose = [None] * (n+1); n_choose[0] = 1\n      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p\n      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p\n    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose\n\n\ndef z_algorithm(s):\n  n = len(s)\n  a = [0] * n; a[0] = n\n  l = r = -1\n  for i in range(1, n):\n    if r >= i: a[i] = min(a[i-l], r-i)\n    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1\n    if i+a[i] >= r: l, r = i, i+a[i]\n  return a\n\n\nclass ABC001():\n  def A():\n    h1, h2 = map(int, sys.stdin.read().split())\n    print(h1-h2)\n\n  def B(): pass\n  def C(): pass \n  def D(): pass \n\n\nclass ABC002():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(max(x, y))\n\n  def B():\n    vowels = set('aeiou')\n    s = sys.stdin.readline().rstrip() \n    t = ''\n    for c in s:\n      if c in vowels: continue \n      t += c \n    print(t)\n\n  def C():\n    *coords, = map(int, sys.stdin.readline().split())\n    def triangle_area(x0, y0, x1, y1, x2, y2):\n      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;\n      return abs(x1*y2 - x2*y1) / 2\n    print(triangle_area(*coords))\n\n  def D():\n    n, m = map(int, sys.stdin.readline().split())\n    edges = set()\n    for _ in range(m):\n      x, y = map(int, sys.stdin.readline().split())\n      x -= 1; y -= 1\n      edges.add((x, y))\n    cand = []\n    for i in range(1, 1<<n):\n      s = [j for j in range(n) if i>>j & 1]\n      for x, y in combinations(s, 2):\n        if (x, y) not in edges: break\n      else:\n        cand.append(len(s))\n    print(max(cand))\n\n\nclass ABC003():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)*5000)\n\n  def B():\n    atcoder = set('atcoder')\n    s, t = sys.stdin.read().split()\n    for i in range(len(s)):\n      if s[i] == t[i]: continue\n      if s[i] == '@' and t[i] in atcoder: continue \n      if t[i] == '@' and s[i] in atcoder: continue\n      print('You will lose')\n      return \n    print('You can win')\n\n  def C():\n    n, k, *r = map(int, sys.stdin.read().split())\n    res = 0\n    for x in sorted(r)[-k:]:\n      res = (res+x) / 2\n    print(res)\n\n  def D(): pass \n\n\nclass ABC004():\n  def A():\n    print(int(sys.stdin.readline().rstrip())*2)\n\n  def B():\n    c = [sys.stdin.readline().rstrip() for _ in range(4)]\n    for l in c[::-1]:\n      print(l[::-1])\n\n  def C():\n    n = int(sys.stdin.readline().rstrip())\n    n %= 30\n    res = list(range(1, 7))\n    for i in range(n):\n      i %= 5\n      res[i], res[i+1] = res[i+1], res[i]\n    print(''.join(map(str, res)))\n\n  def D(): pass \n\n\nclass ABC005():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(y//x)\n\n  def B():\n    n, *t = map(int, sys.stdin.read().split())\n    print(min(t))\n\n  def C():\n    t = int(sys.stdin.readline().rstrip())\n    n = int(sys.stdin.readline().rstrip())\n    a = [int(x) for x in sys.stdin.readline().split()]\n    m = int(sys.stdin.readline().rstrip())\n    b = [int(x) for x in sys.stdin.readline().split()]\n    i = 0\n    for p in b:\n      if i == n: print('no'); return \n      while p-a[i] > t:\n        i += 1\n        if i == n: print('no'); return \n      if a[i] > p: print('no'); return \n      i += 1\n    print('yes')\n\n  def D():\n    n = int(sys.stdin.readline().rstrip())\n    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)\n    s = d.cumsum(axis=0).cumsum(axis=1)\n    s = np.pad(s, 1)\n    max_del = np.zeros((n+1, n+1), dtype=np.int64)\n    for y in range(1, n+1):\n      for x in range(1, n+1):\n        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])\n    res = np.arange(n**2+1)[:, None]\n    i = np.arange(1, n+1)\n    res = max_del[i, np.minimum(res//i, n)].max(axis=1)\n    q = int(sys.stdin.readline().rstrip())\n    p = np.array(sys.stdin.read().split(), dtype=np.int64)\n    print(*res[p], sep='\\n')\n\n\nclass ABC006():\n  def A():\n    n = sys.stdin.readline().rstrip()\n    if '3' in n: print('YES')\n    elif int(n)%3 == 0: print('YES')\n    else: print('NO')\n\n  def B():\n    mod = 10007\n    t = [0, 0, 1]\n    for _ in range(1001001):\n      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod\n    n = int(sys.stdin.readline().rstrip())\n    print(t[n-1])\n    \n  def C():\n    n, m = map(int, sys.stdin.readline().split())\n    cnt = [0, 0, 0]\n    if m == 1: cnt = [-1, -1, -1]\n    else:\n      if m & 1: m -= 3; cnt[1] += 1; n -= 1\n      cnt[2] = m//2 - n \n      cnt[0] = n - cnt[2]\n    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)\n    else: print(*cnt, sep=' ')\n      \n  def D():\n    n, *c = map(int, sys.stdin.read().split())\n    inf = float('inf')\n    lis = [inf]*n \n    for x in c: lis[bi_l(lis, x)] = x \n    print(n - bi_l(lis, inf))\n\n\nclass ABC007():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n-1)\n\n  def B():\n    s = sys.stdin.readline().rstrip()\n    if s == 'a': print(-1)\n    else: print('a')\n\n  def C():\n    r, c = map(int, sys.stdin.readline().split())\n    sy, sx = map(int, sys.stdin.readline().split())\n    gy, gx = map(int, sys.stdin.readline().split())\n    sy -= 1; sx -=1; gy -= 1; gx -= 1\n    maze = [sys.stdin.readline().rstrip() for _ in range(r)]\n    queue = deque([(sy, sx)])\n    dist = np.full((r, c), np.inf); dist[sy, sx] = 0\n    while queue:\n      y, x = queue.popleft()\n      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n        i += y; j += x\n        if maze[i][j] == '#' or dist[i, j] != np.inf: continue \n        dist[i, j] = dist[y, x] + 1\n        queue.append((i, j))\n    print(int(dist[gy, gx]))\n  \n  def D(): pass \n\n\nclass ABC008():\n  def A():\n    s, t = map(int, sys.stdin.readline().split())\n    print(t-s+1)\n\n  def B():\n    n, *s = sys.stdin.read().split()\n    res = defaultdict(int)\n    for name in s: res[name] += 1\n    print(sorted(res.items(), key=lambda x: x[1])[-1][0])\n\n  def C():\n    n, *a = map(int, sys.stdin.read().split())\n    a = np.array(a)\n    c = n - np.count_nonzero(a[:, None]%a, axis=1)\n    print(np.sum((c+1)//2/c))\n  \n  def D(): pass\n\nclass ABC009():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)//2)\n\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    print(sorted(set(a))[-2])\n    \n  def C():\n    n, k = map(int, sys.stdin.readline().split())\n    s = list(sys.stdin.readline().rstrip())\n    cost = [1]*n\n    r = k\n    for i in range(n-1):\n      q = []\n      for j in range(i+1, n):\n        if s[j] < s[i] and cost[i]+cost[j] <= r:\n          heappush(q, (s[j], cost[i]+cost[j], -j))\n      if not q: continue\n      _, c, j = heappop(q); j = -j \n      s[i], s[j] = s[j], s[i]\n      r -= c \n      cost[i] = cost[j] = 0\n    print(''.join(s))\n      \n  def D(): pass \n\n\nclass ABC010():\n  def A():\n    print(sys.stdin.readline().rstrip()+'pp')\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    tot = 0\n    for x in a:\n      c = 0 \n      while x%2==0 or x%3==2:\n        x -= 1\n        c += 1\n      tot += c\n    print(tot)\n\n  def C():\n    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())\n    x, y = np.array(xy).reshape(-1, 2).T\n    def dist(x1, y1, x2, y2):\n      return np.sqrt((x2-x1)**2 + (y2-y1)**2)\n    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'\n    print(ans)\n\n  def D(): pass \n\nclass ABC011():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n%12+1)\n\n  def B():\n    s = sys.stdin.readline().rstrip() \n    print(s[0].upper()+s[1:].lower())\n\n  def C():\n    n, *ng = map(int, sys.stdin.read().split())\n    ng = set(ng)\n    if n in ng: print('NO')\n    else:\n      r = 100\n      while n > 0:\n        if r == 0: print('NO'); return\n        for i in range(3, 0, -1):\n          if (n-i) in ng: continue \n          n -= i\n          r -= 1\n          break \n        else: print('NO'); return \n      print('YES')\n\n  def D(): pass \n\n\nclass ABC170():\n  def A():\n    x = [int(x) for x in sys.stdin.readline().split()]\n    for i in range(5):\n      if x[i] != i+1:\n        print(i+1)\n        break\n\n  def B():\n    x, y = map(int, sys.stdin.readline().split())\n    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')\n      \n  def C():\n    x, n, *p = map(int, sys.stdin.read().split())\n    a = list(set(range(102)) - set(p))\n    a = [(abs(y-x), y) for y in a]\n    print(sorted(a)[0][1])\n\n  def D():\n    n, *a = map(int, sys.stdin.read().split())\n    cand = set(a)\n    cnt = 0\n    for x, c in sorted(Counter(a).items()):\n      cnt += c == 1 and x in cand\n      cand -= set(range(x*2, 10**6+1, x))\n    print(cnt)\n\n\n  def E():\n    n, q = map(int, sys.stdin.readline().split())\n    queue = [] \n    num_kindergarten = 2*10**5\n    queue_kindergarten = [[] for _ in range(num_kindergarten)]\n    highest_kindergarten = [None] * num_kindergarten\n    where = [None] * n\n    rate = [None] * n\n\n    def entry(i, k):\n      where[i] = k\n      while queue_kindergarten[k]:\n        r, j = heappop(queue_kindergarten[k])\n        if where[j] != k or j == i: continue \n        if rate[i] > -r:\n          highest_kindergarten[k] = rate[i]\n          heappush(queue, (rate[i], k, i))\n        heappush(queue_kindergarten[k], (r, j))\n        break\n      else:\n        highest_kindergarten[k] = rate[i]\n        heappush(queue, (rate[i], k, i))\n      heappush(queue_kindergarten[k], (-rate[i], i))\n\n    def transfer(i, k):\n      now = where[i]\n      while queue_kindergarten[now]:\n        r, j = heappop(queue_kindergarten[now])\n        if where[j] == now: break\n      if j != i:\n        heappush(queue_kindergarten[now], (r, j))\n      else:\n        while queue_kindergarten[now]:\n          r, j = heappop(queue_kindergarten[now])\n          if where[j] != now or j == i: continue\n          highest_kindergarten[now] = -r\n          heappush(queue, (-r, now, j))\n          heappush(queue_kindergarten[now], (r, j))\n          break\n        else:\n          highest_kindergarten[now] = None\n      entry(i, k)\n\n    def inquire():\n      while True:\n        r, k, i = heappop(queue)\n        if where[i] != k or r != highest_kindergarten[k]: continue \n        heappush(queue, (r, k, i))\n        return r\n\n    for i in range(n):\n      a, b = map(int, sys.stdin.readline().split())\n      rate[i] = a \n      entry(i, b-1)\n\n    for _ in range(q):\n      c, d = map(int, sys.stdin.readline().split())\n      transfer(c-1, d-1)\n      print(inquire())\n    \n\n\n  def F(): pass \n\ndef __starting_point():\n  ABC170.E()\n__starting_point()", "def getN():\n    return int(input())\ndef getNM():\n    return list(map(int, input().split()))\ndef getList():\n    return list(map(int, input().split()))\ndef getZList():\n    return [int(x) - 1 for x in input().split()]\nfrom collections import defaultdict, deque\nimport math\nimport copy\nfrom bisect import bisect_left, bisect_right\nimport heapq\nimport sys\ninput = sys.stdin.readline\n# sys.setrecursionlimit(1000000)\nINF = 10 ** 17\nMOD = 1000000007\n \nclass LazyHeap():\n    def __init__(self, init_arr=[]):\n        self.heap = []\n        self.lazy = defaultdict(int)\n        self.len = 0\n        for init_element in init_arr:\n            heapq.heappush(self.heap, init_element)\n            self.len += 1\n \n    def __len__(self):\n        return self.len\n \n    def push(self, k):\n        heapq.heappush(self.heap, k)\n        self.len += 1\n \n    def pop(self):\n        self._clear()\n        return heapq.heappop(self.heap)\n        \n    def get(self):\n        self._clear()\n        return self.heap[0]\n \n    def _clear(self):\n        while True:\n            cand = self.heap[0]\n            if cand in self.lazy and self.lazy[cand] > 0:\n                heapq.heappop(self.heap)\n                self.lazy[cand] -= 1\n \n            else:\n                return\n \n    def remove(self, k):\n        self.lazy[k] += 1\n        self.len -= 1\n \nN_KINDER = 200200\n# N_KINDER = 2 * (10 ** 5) + 1\nn, q = getList()\nkinder = [LazyHeap() for i in range(N_KINDER)]\nsaikyo = LazyHeap()\nsaikyo_ref = []\npos_ref = [-1 for i in range(n)]\nenji_ref = []\n\nfor i in range(n):\n    a, b = getList()\n    b -= 1\n    enji_ref.append((-a, b))\n    kinder[b].push(-a)\n\nfor kin in kinder:\n    if kin:\n        candidate = kin.get()\n        saikyo.push(-candidate)\n        saikyo_ref.append(candidate)\n    else:\n        saikyo_ref.append(0)\n\nfor i in range(q):\n    c, d = getZList()\n    mv_rate = enji_ref[c][0]\n    prev = enji_ref[c][1]\n    nxt = d\n    pos_ref[c] = d\n    enji_ref[c] = (mv_rate, d)\n    # \u79fb\u52d5\u5143\u306b\u3064\u3044\u3066\u306e\u51e6\u7406\n    kinder[prev].remove(mv_rate)\n\n    kp, kn = kinder[prev], kinder[nxt]\n    if not kp:\n        # \u79fb\u52d5\u3057\u3066\u5712\u51500\u4eba\u306b\u306a\u3063\u305f\u5834\u5408\n        saikyo_ref[prev] = 0\n        saikyo.remove(-mv_rate)\n    elif saikyo_ref[prev] != kp.get():\n        saikyo.remove(-mv_rate)\n        saikyo.push(-kp.get())\n        saikyo_ref[prev] = kp.get()\n\n    # \u79fb\u52d5\u5148\u306b\u3064\u3044\u3066\u306e\u51e6\u7406\n    kn.push(mv_rate)\n    if mv_rate < saikyo_ref[nxt]:\n        saikyo.remove(-saikyo_ref[nxt])\n        saikyo.push(-mv_rate)\n        saikyo_ref[nxt] = mv_rate\n\n    print((saikyo.get()))\n# print(rate)\n", "from heapq import heappop, heappush\n\n\nclass DeletableHeapq:\n    \"\"\"Deletable Heapq: A heapq supporting lazy deletion of values.\"\"\"\n\n    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:\n        self.is_max_heap = is_max_heap\n        self.size = 0\n        self._set = set()\n        self._heap = []\n\n        if initial_values:\n            for v in initial_values:\n                self.push(v)\n\n    @property\n    def top(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        return self._heap[0] if not self.is_max_heap else -self._heap[0]\n\n    def pop(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        self.size -= 1\n        res = heappop(self._heap)\n        self._set.discard(res)\n        return res if not self.is_max_heap else -res\n\n    def push(self, value):\n        if value is None:\n            return\n        if self.is_max_heap:\n            value *= -1\n        if value in self._set:\n            return\n        self.size += 1\n        heappush(self._heap, value)\n        self._set.add(value)\n\n    def delete(self, value):\n        if value is None:\n            return\n        if self.is_max_heap:\n            value *= -1\n        if value not in self._set:\n            return\n        self.size -= 1\n        self._set.discard(value)\n\n\ndef main():\n    # https://atcoder.jp/contests/abc170/tasks/abc170_e\n    encode_kindy = lambda x, y: (x << 18) + y\n    decode_kindy = lambda x: (x >> 18, x & ((1 << 18) - 1))\n    encode_smarts = lambda x, y, z: (x << 36) + (y << 18) + z\n    decode_smarts_rate = lambda x: x >> 36\n\n    N, _, *X = list(map(int, open(0).read().split()))\n    AB, CD = X[: 2 * N], X[2 * N :]\n    rate, belonging = [0] * (N + 1), [0] * (N + 1)\n    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]\n\n    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):\n        rate[i], belonging[i] = a, b\n        kindy[b].push(encode_kindy(a, i))\n\n    smart_infants = DeletableHeapq(\n        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)\n    )\n    res = []\n    for c, next_k in zip(*[iter(CD)] * 2):\n        prev_k = belonging[c]\n        belonging[c] = next_k\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        kindy[prev_k].delete(encode_kindy(rate[c], c))\n        kindy[next_k].push(encode_kindy(rate[c], c))\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        res.append(decode_smarts_rate(smart_infants.top))\n\n    print((\"\\n\".join(map(str, res))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import heappop, heappush, heapify\n\n\nclass RemovableHeap(list):\n    from heapq import heappop, heappush, heapify\n\n    def __init__(self, *args, **kwargs):\n        # super().__init__(*args, **kwargs)\n        self.unremoved_elements = []\n\n    def remove(self, value):\n        heappush(self.unremoved_elements, value)\n        while self.unremoved_elements and self.unremoved_elements[0] == self[0]:\n            heappop(self.unremoved_elements)\n            heappop(self)\n\n\nN, Q = map(int, input().split())\nAB = [list(map(int, input().split())) for _ in range(N)]\nCD = [list(map(int, input().split())) for _ in range(Q)]\nM = 2 * 10 ** 5\nmaxA = 10 ** 9\n\nfor i in range(N):\n    AB[i][1] -= 1\nfor i in range(Q):\n    CD[i][0] -= 1\n    CD[i][1] -= 1\n\nyouchiens = [RemovableHeap() for _ in range(M)]\n\nfor a, b in AB:\n    youchiens[b].append(-a)\nfor i in range(Q):\n    heapify(youchiens[i])\n\nsaikyoenjis = RemovableHeap()\nfor youchien in youchiens:\n    if youchien:\n        saikyoenjis.append(-youchien[0])\nheapify(saikyoenjis)\n\nans = []\nfor c, d in CD:\n    old_youchien = AB[c][1]\n\n    # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\n    # \u3059\u308b\n    saikyoenjis.remove(-youchiens[old_youchien][0])\n\n    # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b\n    youchiens[old_youchien].remove(-AB[c][0])\n\n    # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\n    # \u3059\u308b\uff08\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044\uff09\n    if youchiens[old_youchien]:\n        heappush(saikyoenjis, -youchiens[old_youchien][0])\n\n    # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\n    # \u9664\u3059\u308b\uff08\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044\uff09\n    if youchiens[d]:\n        saikyoenjis.remove(-youchiens[d][0])\n\n    # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b\n    heappush(youchiens[d], -AB[c][0])\n\n    # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\n    # \u5165\u3059\u308b\n    heappush(saikyoenjis, -youchiens[d][0])\n    ans.append(saikyoenjis[0])\n\n    # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u306e\u756a\u53f7\u3092\u66f4\u65b0\u3059\u308b\n    AB[c][1] = d\n\nprint(*ans, sep=\"\\n\")\n", "import heapq as hq\nclass Delheap:\n    def __init__(self):\n        self.heap = []\n        self.deleted = {}\n    def __repr__(self):\n        return str(self.heap)\n    def push(self, x):\n        hq.heappush(self.heap, x)\n    def pop(self):\n        while self.heap:\n            x = hq.heappop(self.heap)\n            if x in self.deleted and self.deleted[x] > 0:\n                self.deleted[x] -= 1\n                if self.deleted[x] == 0:\n                    del self.deleted[x]\n                continue\n            return x\n        return None\n    def delete(self, x):\n        if x not in self.deleted:\n            self.deleted[x] = 1\n        else:\n            self.deleted[x] += 1\n    def peek(self):\n        x = self.pop()\n        if x != None:\n            self.push(x)\n        return x\ndef __starting_point():\n    N, Q = map(int,input().split())\n    shozoku = []\n    rate = []\n    saikyo = Delheap()\n    nurs = [Delheap() for _ in range(2*10**5)]\n    for _ in range(N):\n        a,b = map(int,input().split())\n        b -= 1\n        shozoku.append(b)\n        rate.append(a)\n        nurs[b].push(-a)\n        \n    for i in range(2*10**5):\n        x = nurs[i].peek()\n        if x != None:\n            saikyo.push(-x)\n    anss = []\n    for _ in range(Q):\n        c,d = map(int,input().split())\n        c -= 1\n        d -= 1\n        nur = shozoku[c]\n        saikyo.delete(-nurs[nur].peek())\n        nurs[nur].delete(-rate[c])\n        t = nurs[nur].peek()\n        if t != None:\n            saikyo.push(-t)\n        shozoku[c] = d\n        t = nurs[d].peek()\n        if t != None:\n            saikyo.delete(-t)\n        nurs[d].push(-rate[c])\n        saikyo.push(-nurs[d].peek())\n        anss.append(saikyo.peek())\n    print(*anss, sep=\"\\n\")\n__starting_point()", "import heapq\n\nymax = 200000\nN, Q  = list(map(int, input().split()))\n\nyo = [[] for i in range(ymax+1)]\nym = []\nAB = [(0,0)]\n\nfor i in range(N):\n  A, B  = list(map(int, input().split()))\n  AB.append( (A, B) )\n  heapq.heappush(yo[B],(-A,i+1))\n#\nfor i in range(1,ymax+1):\n  if yo[i]:\n    mA, c = yo[i][0]\n    heapq.heappush(ym,(-mA,c,i)) \n#\nfor i in range(Q):\n  C, D  = list(map(int, input().split()))\n  A, B = AB[C]\n  AB[C] = (A, D)\n  while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):\n    heapq.heappop(yo[B])\n  if yo[B]:\n    mA, c = yo[B][0]\n    heapq.heappush(ym,(-mA,c,B)) \n\n  heapq.heappush(yo[D],(-A,C))\n  if yo[D]:\n    mA, c = yo[D][0]\n    heapq.heappush(ym,(-mA,c,D)) \n#\n  while ym:\n    if AB[ ym[0][1] ][1] != ym[0][2]:\n      heapq.heappop(ym)\n    elif ym[0][1] != yo[ ym[0][2] ][0][1] :\n      heapq.heappop(ym)\n    else:\n      break\n#      \n  print((ym[0][0]))\n#\n", "# coding: utf-8\nimport sys\nfrom heapq import heapify, heappop, heappush\nfrom collections import defaultdict\n\nsr = lambda: sys.stdin.readline().rstrip()\nir = lambda: int(sr())\nlr = lambda: list(map(int, sr().split()))\n\nN, Q = lr()\ntop = []\nleft_top = []\ninfants = [[] for _ in range(2*10**5+1)]  # 1-indexed\nleft = [[] for _ in range(2*10**5+1)]\ndic = defaultdict(tuple)\nfor i in range(1, N+1):\n    a, b = lr()\n    heappush(infants[b], (-a, i))\n    dic[i] = (a, b)\n\nfor i in range(1, 2*10**5+1):\n    if infants[i]:\n        rate, id = infants[i][0]\n        heappush(top, (-rate, id))\n\nfor _ in range(Q):\n    c, next = lr()\n    r, prev = dic[c]\n    dic[c] = (r, next)\n    r3, prev_top = infants[prev][0]\n    heappush(left_top, (-r3, prev_top))\n    heappush(left[prev], (-r, c))\n    while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:\n        heappop(infants[prev])\n        heappop(left[prev])\n    if infants[prev]:\n        rate, id = infants[prev][0]\n        heappush(top, (-rate, id))\n    if infants[next]:\n        heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # id\u3092push\n    heappush(infants[next], (-r, c))  # tuple\u3067push\n    while left[next] and infants[next][0][1] == left[next][0][1]:\n        heappop(infants[next])\n        heappop(left[next])\n    r2, id2 = infants[next][0]\n    heappush(top, (-r2, id2))\n    while left_top and top[0][1] == left_top[0][1]:\n        heappop(top); heappop(left_top)\n    answer = top[0][0]\n    print(answer)\n", "import sys\nimport bisect\nimport heapq\n\nN_MAX = 2*10**5\nA_MAX = 10**9\n\nA = []\nB = []\nBB = [[] for _ in range(N_MAX)]\n\nBBmax = []  # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\n\ndef max_rate_in_a_kg(kg):\n    \n    # \u5bfe\u8c61\u306e\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u30ec\u30fc\u30c8\u3092\u66f4\u65b0\n    while BB[kg]:\n        rate, k = BB[kg][0]\n        if B[k] == kg:  # \u3044\u308b\u306a\u3089OK\n            return -rate\n        else:\n            heapq.heappop(BB[kg])  # \u8ee2\u5712\u3057\u3066\u3044\u308c\u3070\u524a\u9664\n\n    return 0\n\n\ndef max_rate():\n    while BBmax:\n        rate, kg_no = BBmax[0]\n        if max_rate_in_a_kg(kg_no) == rate:\n            return rate\n        else:\n            heapq.heappop(BBmax)\n    return None\n\ndef p():\n    for i in range(len(BB)):\n        if BB[i] != []:\n            print(i, BB[i])\n\ndef pp():\n    print(\"BBmax : \", end=\"\")\n    for i in range(len(BBmax)):\n        print(BBmax[i], end=\" \")\n    print()\n\n\ndef main():\n\n    N, Q = map(int, sys.stdin.readline().split())\n\n    for i in range(N):\n        a, b = map(int, sys.stdin.readline().split())\n        A.append(a)  # \u30ec\u30fc\u30c8\n        B.append(b-1)  # \u5e7c\u7a1a\u5712\u756a\u53f7\u30820\u304b\u3089\u306b\u3059\u308b\n        heapq.heappush(BB[b-1],(-a,i))  # BB \u306f\u6700\u5927\u304c\u6700\u3082\u5de6\u306b\u6765\u308b\u3088\u3046\u306b\u3059\u308b\n\n    for kg_no in range(N_MAX):\n        rate = max_rate_in_a_kg(kg_no)\n        if rate > 0:\n            BBmax.append((rate, kg_no))\n    heapq.heapify(BBmax)\n\n    # p()\n    # pp()\n\n    for i in range(Q):\n        # print(\"====\")\n        c, d = map(int, sys.stdin.readline().split())\n\n        kid_no = c-1  # \u5712\u5150\u756a\u53f7\n        after = d-1  # \u5e7c\u7a1a\u5712\u756a\u53f7\n\n        # \u8ee2\u51fa\n        before = B[kid_no]\n        B[kid_no] = after  # \u5712\u5150\u306e\u6240\u5c5e\u3092\u66f4\u65b0\n\n        heapq.heappush(BB[after], (-A[kid_no], kid_no))  # \u5e7c\u7a1a\u5712\u306e\u6700\u5927\u3092\u66f4\u65b0\n        # p()\n\n        new_rate_kg = max_rate_in_a_kg(before)  # \u8ee2\u5165\u5143\u306e\u6700\u5927\u3092\u66f4\u65b0\n        if new_rate_kg != 0:\n            heapq.heappush(BBmax, (new_rate_kg, before))\n\n        new_rate_kg = max_rate_in_a_kg(after)  # \u8ee2\u5712\u5148\u306e\u6700\u5927\u30ec\u30fc\u30c8\u3092\u66f4\u65b0\n        if new_rate_kg != 0:\n            heapq.heappush(BBmax, (new_rate_kg, after))  # BBmax \u3092\u66f4\u65b0\n\n        # pp()\n        print(max_rate())\n\ndef __starting_point():\n    main()\n__starting_point()", "def main():\n    import sys\n    def input(): return sys.stdin.readline().rstrip()\n    n, q = map(int, input().split())\n    from collections import defaultdict\n    from heapq import heappush, heappop\n    # \u5e7c\u7a1a\u5712\u3054\u3068\u306e\u5712\u5150\u30ea\u30b9\u30c8\u3092\u30d2\u30fc\u30d7\u3067\u683c\u7d0d\n    h = defaultdict(lambda: [])\n    # \u5e7c\u7a1a\u5712\u5f8c\u306e\u6700\u5f37\u5712\u5150\u3092\u683c\u7d0d\n    saikyo = []\n    A, B = [], []\n    for i in range(n):\n        a, b = map(int, input().split())\n        A.append(a)\n        B.append(b)\n        heappush(h[b], (-a, i)) \n    for i in h:\n        x = h[i][0]\n        heappush(saikyo, (-x[0], x[1]))       \n    for i in range(q):\n        c, d = map(int, input().split())\n        c -= 1\n        # \u8ee2\u5712\u51e6\u7406\n        cfrom = B[c]\n        B[c] = d\n        # \u79fb\u52d5\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30c1\u30a7\u30c3\u30af\n        while h[cfrom]:\n            x = h[cfrom][0]\n            if B[x[1]] != cfrom:\n                heappop(h[cfrom])\n                continue\n            heappush(saikyo, (-x[0], x[1]))\n            break\n        heappush(h[d], (-A[c], c))\n        # \u79fb\u52d5\u5148\u306e\u6700\u5f37\u5712\u5150\u30c1\u30a7\u30c3\u30af\n        while h[d]:\n            x = h[d][0]\n            # if B[x[1]] != d:\n            #     heappop(h[d])\n            #     continue\n            heappush(saikyo, (-x[0], x[1]))\n            break\n\n        # saikyo\u306e\u6700\u5c0f\u5024\u3092\u6c42\u3081\u308b\u3002\n        while saikyo:\n            x = saikyo[0]\n\n            y = h[B[x[1]]][0]\n            if -y[0] != x[0]:\n                heappop(saikyo)\n                continue\n            print(x[0])\n            break\n    \n    print()\ndef __starting_point():\n    main()\n__starting_point()", "import heapq\nN,Q=map(int,input().split())\nM=2*(10**5)\nbelong=[]\nrate=[]\ngarden=[[]for _ in range(M)]\nfor c in range(N):\n    A,B=map(int,input().split())\n    B-=1\n    belong.append(B)\n    rate.append(A)\n    heapq.heappush(garden[B],(-A,c))\n    \nstrong=[]\n\nfor i in range(M):\n    if garden[i]:\n        A,c=garden[i][0]\n        heapq.heappush(strong,(-A,c,i))\n        \nfor i in range(Q):\n    C,D=map(int,input().split())\n    C-=1\n    D-=1\n    now=belong[C]\n    belong[C]=D\n    \n    while garden[now]:\n        A,c=garden[now][0]\n        if belong[c]!=now:\n            heapq.heappop(garden[now])\n        else:\n            heapq.heappush(strong,(-A,c,now))\n            break\n            \n    heapq.heappush(garden[D],(-rate[C],C))\n    A,c=garden[D][0]\n    heapq.heappush(strong,(-A,c,D))\n    \n    while strong:\n        A,c,d=strong[0]\n        if belong[c]!=d or garden[d][0][1]!=c:\n            heapq.heappop(strong)\n        else:\n            print(A)\n            break", "from heapq import heappop, heappush\nfrom typing import Optional\n\n\nclass DeletableHeapq:\n    \"\"\"Deletable Heapq: a heapq that supports lazy deletion of values.\"\"\"\n\n    __slots__ = [\"_is_max_heap\", \"_set\", \"_heap\"]\n\n    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:\n        self._is_max_heap = is_max_heap\n        self._set = set()\n        self._heap = []\n\n        if initial_values:\n            for v in initial_values:\n                self.push(v)\n\n    def __len__(self) -> int:\n        return len(self._set)\n\n    @property\n    def is_empty(self) -> bool:\n        \"\"\"Return whether the heap has no values or not.\"\"\"\n        return len(self) == 0\n\n    @property\n    def top(self) -> Optional[int]:\n        \"\"\"Return the minimum value if is_max_heap is False;\n        otherwise, return the maximum value from the heap.\n        If the heap is empty, None is returned.\n        \"\"\"\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        return self._heap[0] if not self._is_max_heap else -self._heap[0]\n\n    def push(self, value: int) -> None:\n        \"\"\"Push value into the heap.\"\"\"\n        if self._is_max_heap:\n            value = -value\n        if value in self._set:\n            return\n        heappush(self._heap, value)\n        self._set.add(value)\n\n    def delete(self, value: int) -> None:\n        \"\"\"Delete value from the heap.\"\"\"\n        if self._is_max_heap:\n            value = -value\n        if value not in self._set:\n            return\n        self._set.discard(value)\n\n\ndef main():\n    # https://atcoder.jp/contests/abc170/tasks/abc170_e\n    N, _, *X = list(map(int, open(0).read().split()))\n    AB, CD = X[: 2 * N], X[2 * N :]\n    rate, belonging = [0] * (N + 1), [0] * (N + 1)\n    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]\n\n    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):\n        rate[i], belonging[i] = (a << 18) + i, b\n        kindy[b].push(rate[i])\n\n    smarts = DeletableHeapq(*(k.top for k in kindy if not k.is_empty))\n    res = []\n    for c, d in zip(*[iter(CD)] * 2):\n        prev_k, next_k = kindy[belonging[c]], kindy[d]\n        belonging[c] = d\n\n        for k in (prev_k, next_k):\n            if not k.is_empty:\n                smarts.delete(k.top)\n\n        prev_k.delete(rate[c])\n        next_k.push(rate[c])\n\n        for k in (prev_k, next_k):\n            if not k.is_empty:\n                smarts.push(k.top)\n\n        res.append(smarts.top >> 18)\n\n    print((\"\\n\".join(map(str, res))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "import heapq\nimport sys\ninput = sys.stdin.readline\n \nN, Q = map(int, input().split())\nAB = [tuple(map(int, input().split())) for _ in range(N)]\nCD = [tuple(map(int, input().split())) for _ in range(Q)]\nH = 2*10**5 # \u5e7c\u7a1a\u5712\n \nINF = 10**18\nrates = [[] for _ in range(H)]\nmembers = [set() for _ in range(H)]\nbelongs = [-1]*N\nfor i,(a,b) in enumerate(AB):\n    b -= 1\n    heapq.heappush(rates[b], (-a,i))\n    members[b].add(i)\n    belongs[i] = b\n \nmxrates = []\nfor num,r in enumerate(rates):\n    if len(r) > 0:\n        heapq.heappush(mxrates, (-r[0][0], num)) # \u5e7c\u7a1a\u5712\u3054\u3068\u306e\u6700\u5927\u5024\u3092\u3044\u308c\u308b\n \nfor c,d in CD:\n    c, d = c-1, d-1\n    old = belongs[c]\n    belongs[c] = d\n    members[old].remove(c)\n    members[d].add(c)\n    # \u8ee2\u5712\u5143\u306e\u6700\u5927\u5024\u3092\u6700\u65b0\u5316\u3059\u308b\n    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:\n        heapq.heappop(rates[old])\n    # \u6700\u65b0\u5316\u3055\u308c\u305f\u8ee2\u5712\u5143\u304b\u3089\u6539\u3081\u3066\u53d6\u5f97\n    if len(rates[old]) > 0:\n        heapq.heappush(mxrates, (-rates[old][0][0], old))\n    # \u8ee2\u5712\u5148\u306b\u8ffd\u52a0\n    heapq.heappush(rates[d], (-AB[c][0], c))\n    heapq.heappush(mxrates, (AB[c][0], d))\n    while mxrates:\n        rate, num = mxrates[0]\n        # mxrates\u306e\u6700\u5c0f\u304c\u6700\u65b0\u3067\u306f\u306a\u3044\u5834\u5408\n        if len(rates[num]) == 0 or -rates[num][0][0] != rate:\n            heapq.heappop(mxrates)\n        else:\n            print(rate)\n            break", "import sys\nsys.setrecursionlimit(10**7) #\u518d\u5e30\u95a2\u6570\u306e\u4e0a\u9650,10**5\u4ee5\u4e0a\u306e\u5834\u5408python\nimport math\nfrom copy import copy, deepcopy\nfrom copy import deepcopy as dcp\nfrom operator import itemgetter\nfrom bisect import bisect_left, bisect, bisect_right#2\u5206\u63a2\u7d22\n#bisect_left(l,x), bisect(l,x)#a\u306f\u30bd\u30fc\u30c8\u6e08\u307f\u3067\u3042\u308b\u5fc5\u8981\u3042\u308a\u3002a\u306e\u4e2d\u304b\u3089x\u672a\u6e80\u306e\u8981\u7d20\u6570\u3092\u8fd4\u3059\u3002right\u3060\u3068\u4ee5\u4e0b\nfrom collections import deque\n#deque(l), pop(), append(x), popleft(), appendleft(x)\n##list\u3067que\u306e\u4ee3\u7528\u3092\u3059\u308b\u3068O(N)\u306e\u8a08\u7b97\u91cf\u304c\u304b\u304b\u3063\u3066\u3057\u307e\u3046\u306e\u3067\u6ce8\u610f\nfrom collections import Counter#\u6587\u5b57\u5217\u3092\u500b\u6570\u30ab\u30a6\u30f3\u30c8\u8f9e\u66f8\u306b\u3001\n#S=Counter(l),S.most_common(x),S.keys(),S.values(),S.items()\nfrom itertools import accumulate#\u7d2f\u7a4d\u548c\n#list(accumulate(l))\nfrom heapq import heapify,heappop,heappush\n#heapify(q),heappush(q,a),heappop(q) #q=heapify(q)\u3068\u3057\u306a\u3044\u3053\u3068\u3001\u8fd4\u308a\u5024\u306fNone\n#import fractions#\u53e4\u3044atcoder\u30b3\u30f3\u30c6\u30b9\u30c8\u306e\u5834\u5408GCD\u306a\u3069\u306f\u3053\u3053\u304b\u3089import\u3059\u308b\nfrom functools import lru_cache#pypy\u3067\u3082\u3046\u3054\u304f\n#@lru_cache(maxsize = None)#maxsize\u306f\u4fdd\u5b58\u3059\u308b\u30c7\u30fc\u30bf\u6570\u306e\u6700\u5927\u5024\u30012**n\u304c\u6700\u3082\u9ad8\u52b9\u7387\n\ndef input(): return sys.stdin.readline()[:-1]\ndef printl(li): _=print(*li, sep=\"\\n\") if li else None\ndef argsort(s, return_sorted=False): \n    inds=sorted(range(len(s)), key=lambda k: s[k])\n    if return_sorted: return inds, [s[i] for i in inds]\n    return inds\ndef alp2num(c,cap=False): return ord(c)-97 if not cap else ord(c)-65\ndef num2alp(i,cap=False): return chr(i+97) if not cap else chr(i+65)\ndef matmat(A,B):\n    K,N,M=len(B),len(A),len(B[0])\n    return [[sum([(A[i][k]*B[k][j]) for k in range(K)]) for j in range(M)] for i in range(N)]\ndef matvec(M,v):\n    N,size=len(v),len(M)\n    return [sum([M[i][j]*v[j] for j in range(N)]) for i in range(size)]\ndef T(M):\n    n,m=len(M),len(M[0])\n    return [[M[j][i] for j in range(n)] for i in range(m)]\ndef main():\n    mod = 1000000007\n    #w.sort(key=itemgetter(1),reversed=True)  #\u4e8c\u500b\u76ee\u306e\u8981\u7d20\u3067\u964d\u9806\u4e26\u3073\u66ff\u3048\n\n    #N = int(input())\n    N, Q = map(int, input().split())\n    #A = tuple(map(int, input().split())) #1\u884c\u30d9\u30af\u30c8\u30eb\n    #L = tuple(int(input()) for i in range(N)) #\u6539\u884c\u30d9\u30af\u30c8\u30eb\n    #S = tuple(tuple(map(int, input().split())) for i in range(N)) #\u6539\u884c\u884c\u5217\n\n    l=[Counter() for _ in range(2*10**5)]\n    rates=[[] for _ in range(2*10**5)]\n    dic=dict()\n    for i in range(N):\n        a,b=map(int, input().split())\n        b-=1\n        l[b][a]+=1\n        dic[i]=(a,b)\n        heappush(rates[b],-a)\n    tot=[]\n    for b,r in enumerate(rates):\n        if r:\n            a=-r[0]\n            heappush(tot,(a,b))\n    \n\n    qs = tuple(tuple(map(int, input().split())) for i in range(Q))\n    for c,d in qs:\n        c-=1\n        d-=1\n        a,b=dic[c]\n        l[b][a]-=1\n        l[d][a]+=1\n        dic[c]=(a,d)\n        heappush(rates[d],-a)\n        heappush(tot,(a,d))\n        rm=-rates[b][0]\n        while rates[b] and l[b][-rates[b][0]]==0:\n            heappop(rates[b])\n\n        if rates[b]:\n            heappush(tot,(-rates[b][0],b))\n\n        m,mb=tot[0]\n        #print(l[0],l[1],l[2])\n        while l[mb][m]<1 or m!=-rates[mb][0]:\n            heappop(tot)\n            \n            m,mb=tot[0]\n            \n        print(m)\n        \n\n\n\n\n\n\n\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "import heapq\n\n\nclass HeapDict:\n    def __init__(self):\n        # heapq\u3068dict\u3092\u7528\u610f\n        self.h = []\n        self.d = dict()\n\n    def insert(self, x):\n        heapq.heappush(self.h, x)\n        if x not in self.d:\n            self.d[x] = 1\n        else:\n            self.d[x] += 1\n\n    def erase(self, x):\n        if x not in self.d or self.d[x] == 0:\n            print((x, \"is not in HeapDict\"))\n            return\n        else:\n            self.d[x] -= 1\n\n        while len(self.h) != 0:\n            if self.d[self.h[0]] == 0:\n                heapq.heappop(self.h)\n            else:\n                break\n\n    def is_exist(self, x):\n        if x in self.d and self.d[x] != 0:\n            return True\n        else:\n            False\n\n    def get_min(self):\n        return self.h[0]\n\n    def size(self):\n        return len(self.h)\n\n\ndef main():\n    N, Q = list(map(int, input().split()))\n    A = []  # \u30ec\u30fc\u30c8\n    B = []  # \u6240\u5c5e\u5e7c\u7a1a\u5712\n    con = 2 * 10 ** 5\n    INF = 10 ** 18\n    youchi = [HeapDict() for _ in range(con)]  # \u5404\u5e7c\u7a1a\u5712\u306b\u5bfe\u3059\u308bHeapDict\n    max_values = HeapDict()  # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u306eHeapDict\n    for i in range(N):\n        a, b = list(map(int, input().split()))\n        b -= 1\n        A.append(a)\n        B.append(b)\n        youchi[b].insert(-a)\n\n    for i in range(con):  # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u3092\u307e\u3068\u3081\u308b\n        if youchi[i].size() != 0:\n            max_values.insert(-youchi[i].get_min())\n\n    for i in range(Q):\n        c, d = list(map(int, input().split()))\n        c -= 1\n        d -= 1\n        rate = A[c]\n        youchi_now = B[c]\n        youchi_next = d\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b\n        max_values.erase(-youchi[youchi_now].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b\n        youchi[youchi_now].erase(-rate)\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u5143\u306e\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b(\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044)\n        if youchi[youchi_now].size() != 0:\n            max_values.insert(-youchi[youchi_now].get_min())\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u304b\u3089\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u5143\u306e\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u524a\u9664\u3059\u308b(\u5712\u5150\u304c\u4e00\u4eba\u3082\u3044\u306a\u3044\u5834\u5408\u4f55\u3082\u3057\u306a\u3044)\n        if youchi[youchi_next].size() != 0:\n            max_values.erase(-youchi[youchi_next].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b\n        youchi[youchi_next].insert(-rate)\n\n        # \u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u306e\u96c6\u5408\u306b\u3001\u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u65b0\u3057\u3044\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8\u3092\u3001\u633f\u5165\u3059\u308b\n        max_values.insert(-youchi[youchi_next].get_min())\n\n        # \u8ee2\u5712\u3059\u308b\u5712\u5150\u306e\u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u306e\u756a\u53f7\u3092\u66f4\u65b0\u3059\u308b\n        B[c] = youchi_next\n\n        print((max_values.get_min()))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t,_ in x:t and f(l,-t[0])\nfor c,d in z[n:]:\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)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y[0]!=t:f(l,a);t<0and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "import sys\nimport numpy as np\nfrom heapq import heappush, heappop \nfrom bisect import bisect_left as bi_l, bisect_right as bi_r\nfrom collections import deque, Counter, defaultdict\nfrom itertools import combinations, product\nimport string \nimport math \ninf = float('inf')\nMOD = 10**9+7\n# MOD = 998244353\n\n\nclass NumberTheory():\n  def __init__(self, n=2*10**6, numpy=True):\n    self.n = n\n    self.np_flg = numpy \n    self.is_prime_number, self.prime_numbers = self.sieve_of_eratosthenes(n)\n  \n  def sieve_of_eratosthenes(self, n):\n    if self.np_flg:\n      sieve = np.ones(n+1, dtype=np.int64); sieve[:2] = 0\n      for i in range(2, int(n**.5)+1):\n        if sieve[i]: sieve[i*2::i] = 0\n      prime_numbers = np.flatnonzero(sieve)\n    else:\n      sieve = [1] * (n+1); sieve[0] = sieve[1] = 0\n      for i in range(2, int(n**.5)+1):\n        if not sieve[i]: continue\n        for j in range(i*2, n+1, i): sieve[j] = 0\n      prime_numbers = [i for i in range(2, n+1) if sieve[i]]\n    return sieve, prime_numbers \n\n  def prime_factorize(self, n):\n    res = dict()\n    if n < 2: return res\n    border = int(n**.5)\n    for p in self.prime_numbers:\n      if p > border: break\n      while n % p == 0: res[p] = res.get(p, 0)+1; n //= p\n      if n == 1: return res\n    res[n] = 1; return res\n\n  def prime_factorize_factorial(self, n):\n    res = dict()\n    for i in range(2, n+1):\n      for p, c in self.prime_factorize(i).items(): res[p] = res.get(p, 0)+c\n    return res\n  \n  @staticmethod\n  def gcd(a, b): return gcd(b, a%b) if b else abs(a)\n\n  @staticmethod\n  def lcm(a, b): return abs(a // gcd(a, b) * b)\n\n  @staticmethod\n  def find_divisors(n):\n    divisors = []\n    for i in range(1, int(n**.5)+1):\n      if n%i: continue\n      divisors.append(i)\n      j = n // i\n      if j != i: divisors.append(j)\n    return divisors\n  \n  @staticmethod\n  def base_convert(n, b):\n    if not n: return [0]\n    res = []\n    while n:\n      n, r = divmod(n, b)\n      if r < 0: n += 1; r -= b\n      res.append(r)\n    return res\n\n\nclass UnionFind():\n  def __init__(self, n=10**6):\n    self.root = list(range(n))\n    self.height = [0] * n \n    self.size = [1] * n \n  \n  def find_root(self, u):\n    if self.root[u] == u: return u\n    self.root[u] = self.find_root(self.root[u])\n    return self.root[u]\n  \n  def unite(self, u, v):\n    ru = self.find_root(u)\n    rv = self.find_root(v)\n    if ru == rv: return \n    hu = self.height[ru]\n    hv = self.height[rv]\n    if hu >= hv:\n      self.root[rv] = ru \n      self.size[ru] += self.size[rv]\n      self.height[ru] = max(hu, hv+1)\n    else:\n      self.root[ru] = rv \n      self.size[rv] += self.size[ru]\n\n\nclass Combinatorics():\n  def __init__(self, N=10**9, n=10**6, mod=10**9+7, numpy=True):\n    self.mod = mod\n    self.nCr = dict()\n    self.np_flg=numpy\n    self.make_mod_tables(N, n)\n\n  sys.setrecursionlimit(10**6)\n  def choose(self, n, r, mod=None): # no mod, or mod \u2260 prime\n    if r > n or r < 0: return 0\n    if r == 0: return 1\n    if (n, r) in self.nCr: return self.nCr[(n, r)]\n    if not mod:\n      self.nCr[(n, r)] = (self.choose(n-1, r) + self.choose(n-1, r-1))\n    else:\n      self.nCr[(n, r)] = (self.choose(n-1, r, mod) + self.choose(n-1, r-1, mod)) % mod\n    return self.nCr[(n,r)]\n  \n  def cumprod(self, a):\n    p = self.mod\n    l = len(a); sql = int(np.sqrt(l)+1)\n    a = np.resize(a, sql**2).reshape(sql, sql)\n    for i in range(sql-1): a[:, i+1] *= a[:, i]; a[:, i+1] %= p\n    for i in range(sql-1): a[i+1] *= a[i, -1]; a[i+1] %= p\n    return np.ravel(a)[:l]\n\n  def make_mod_tables(self, N, n):\n    p = self.mod\n    if self.np_flg:\n      fac = np.arange(n+1); fac[0] = 1; fac = self.cumprod(fac)\n      ifac = np.arange(n+1, 0, -1); ifac[0] = pow(int(fac[-1]), p-2, p)\n      ifac = self.cumprod(ifac)[n::-1]\n      n_choose = np.arange(N+1, N-n, -1); n_choose[0] = 1;\n      n_choose[1:] = self.cumprod(n_choose[1:])*ifac[1:n+1]%p\n    else:\n      fac = [None]*(n+1); fac[0] = 1\n      for i in range(n): fac[i+1] = fac[i]*(i+1)%p\n      ifac = [None]*(n+1); ifac[n] = pow(fac[n], p-2, p)\n      for i in range(n, 0, -1): ifac[i-1] = ifac[i]*i%p\n      n_choose = [None] * (n+1); n_choose[0] = 1\n      for i in range(n): n_choose[i+1] = n_choose[i]*(N-i)%p\n      for i in range(n+1): n_choose[i] = n_choose[i]*ifac[i]%p\n    self.fac, self.ifac, self.mod_n_choose = fac, ifac, n_choose\n  \n  def mod_choose(self, n, r):\n    return self.fac[n]*self.ifac[r]%self.mod*self.ifac[n-r]%self.mod\n\n\ndef z_algorithm(s):\n  n = len(s)\n  a = [0] * n; a[0] = n\n  l = r = -1\n  for i in range(1, n):\n    if r >= i: a[i] = min(a[i-l], r-i)\n    while i + a[i] < n and s[i+a[i]] == s[a[i]]: a[i] += 1\n    if i+a[i] >= r: l, r = i, i+a[i]\n  return a\n\n\nclass ABC001():\n  def A():\n    h1, h2 = map(int, sys.stdin.read().split())\n    print(h1-h2)\n\n  def B(): pass\n  def C(): pass \n  def D(): pass \n\n\nclass ABC002():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(max(x, y))\n\n  def B():\n    vowels = set('aeiou')\n    s = sys.stdin.readline().rstrip() \n    t = ''\n    for c in s:\n      if c in vowels: continue \n      t += c \n    print(t)\n\n  def C():\n    *coords, = map(int, sys.stdin.readline().split())\n    def triangle_area(x0, y0, x1, y1, x2, y2):\n      x1 -= x0; x2 -= x0; y1 -= y0; y2 -= y0;\n      return abs(x1*y2 - x2*y1) / 2\n    print(triangle_area(*coords))\n\n  def D():\n    n, m = map(int, sys.stdin.readline().split())\n    edges = set()\n    for _ in range(m):\n      x, y = map(int, sys.stdin.readline().split())\n      x -= 1; y -= 1\n      edges.add((x, y))\n    cand = []\n    for i in range(1, 1<<n):\n      s = [j for j in range(n) if i>>j & 1]\n      for x, y in combinations(s, 2):\n        if (x, y) not in edges: break\n      else:\n        cand.append(len(s))\n    print(max(cand))\n\n\nclass ABC003():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)*5000)\n\n  def B():\n    atcoder = set('atcoder')\n    s, t = sys.stdin.read().split()\n    for i in range(len(s)):\n      if s[i] == t[i]: continue\n      if s[i] == '@' and t[i] in atcoder: continue \n      if t[i] == '@' and s[i] in atcoder: continue\n      print('You will lose')\n      return \n    print('You can win')\n\n  def C():\n    n, k, *r = map(int, sys.stdin.read().split())\n    res = 0\n    for x in sorted(r)[-k:]:\n      res = (res+x) / 2\n    print(res)\n\n  def D(): pass \n\n\nclass ABC004():\n  def A():\n    print(int(sys.stdin.readline().rstrip())*2)\n\n  def B():\n    c = [sys.stdin.readline().rstrip() for _ in range(4)]\n    for l in c[::-1]:\n      print(l[::-1])\n\n  def C():\n    n = int(sys.stdin.readline().rstrip())\n    n %= 30\n    res = list(range(1, 7))\n    for i in range(n):\n      i %= 5\n      res[i], res[i+1] = res[i+1], res[i]\n    print(''.join(map(str, res)))\n\n  def D(): pass \n\n\nclass ABC005():\n  def A():\n    x, y = map(int, sys.stdin.readline().split())\n    print(y//x)\n\n  def B():\n    n, *t = map(int, sys.stdin.read().split())\n    print(min(t))\n\n  def C():\n    t = int(sys.stdin.readline().rstrip())\n    n = int(sys.stdin.readline().rstrip())\n    a = [int(x) for x in sys.stdin.readline().split()]\n    m = int(sys.stdin.readline().rstrip())\n    b = [int(x) for x in sys.stdin.readline().split()]\n    i = 0\n    for p in b:\n      if i == n: print('no'); return \n      while p-a[i] > t:\n        i += 1\n        if i == n: print('no'); return \n      if a[i] > p: print('no'); return \n      i += 1\n    print('yes')\n\n  def D():\n    n = int(sys.stdin.readline().rstrip())\n    d = np.array([sys.stdin.readline().split() for _ in range(n)], np.int64)\n    s = d.cumsum(axis=0).cumsum(axis=1)\n    s = np.pad(s, 1)\n    max_del = np.zeros((n+1, n+1), dtype=np.int64)\n    for y in range(1, n+1):\n      for x in range(1, n+1):\n        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])\n    res = np.arange(n**2+1)[:, None]\n    i = np.arange(1, n+1)\n    res = max_del[i, np.minimum(res//i, n)].max(axis=1)\n    q = int(sys.stdin.readline().rstrip())\n    p = np.array(sys.stdin.read().split(), dtype=np.int64)\n    print(*res[p], sep='\\n')\n\n\nclass ABC006():\n  def A():\n    n = sys.stdin.readline().rstrip()\n    if '3' in n: print('YES')\n    elif int(n)%3 == 0: print('YES')\n    else: print('NO')\n\n  def B():\n    mod = 10007\n    t = [0, 0, 1]\n    for _ in range(1001001):\n      t.append(t[-1]+t[-2]+t[-3]); t[-1] %= mod\n    n = int(sys.stdin.readline().rstrip())\n    print(t[n-1])\n    \n  def C():\n    n, m = map(int, sys.stdin.readline().split())\n    cnt = [0, 0, 0]\n    if m == 1: cnt = [-1, -1, -1]\n    else:\n      if m & 1: m -= 3; cnt[1] += 1; n -= 1\n      cnt[2] = m//2 - n \n      cnt[0] = n - cnt[2]\n    if cnt[0]<0 or cnt[1]<0 or cnt[2]<0: print(-1, -1, -1)\n    else: print(*cnt, sep=' ')\n      \n  def D():\n    n, *c = map(int, sys.stdin.read().split())\n    lis = [inf]*n \n    for x in c: lis[bi_l(lis, x)] = x \n    print(n - bi_l(lis, inf))\n\n\nclass ABC007():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n-1)\n\n  def B():\n    s = sys.stdin.readline().rstrip()\n    if s == 'a': print(-1)\n    else: print('a')\n\n  def C():\n    r, c = map(int, sys.stdin.readline().split())\n    sy, sx = map(int, sys.stdin.readline().split())\n    gy, gx = map(int, sys.stdin.readline().split())\n    sy -= 1; sx -=1; gy -= 1; gx -= 1\n    maze = [sys.stdin.readline().rstrip() for _ in range(r)]\n    queue = deque([(sy, sx)])\n    dist = np.full((r, c), np.inf); dist[sy, sx] = 0\n    while queue:\n      y, x = queue.popleft()\n      for i, j in [(-1, 0), (1, 0), (0, -1), (0, 1)]:\n        i += y; j += x\n        if maze[i][j] == '#' or dist[i, j] != np.inf: continue \n        dist[i, j] = dist[y, x] + 1\n        queue.append((i, j))\n    print(int(dist[gy, gx]))\n  \n  def D(): pass \n\n\nclass ABC008():\n  def A():\n    s, t = map(int, sys.stdin.readline().split())\n    print(t-s+1)\n\n  def B():\n    n, *s = sys.stdin.read().split()\n    res = defaultdict(int)\n    for name in s: res[name] += 1\n    print(sorted(res.items(), key=lambda x: x[1])[-1][0])\n\n  def C():\n    n, *a = map(int, sys.stdin.read().split())\n    a = np.array(a)\n    c = n - np.count_nonzero(a[:, None]%a, axis=1)\n    print(np.sum((c+1)//2/c))\n  \n  def D(): pass\n\nclass ABC009():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((n+1)//2)\n\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    print(sorted(set(a))[-2])\n    \n  def C():\n    n, k = map(int, sys.stdin.readline().split())\n    s = list(sys.stdin.readline().rstrip())\n    cost = [1]*n\n    r = k\n    for i in range(n-1):\n      q = []\n      for j in range(i+1, n):\n        if s[j] < s[i] and cost[i]+cost[j] <= r:\n          heappush(q, (s[j], cost[i]+cost[j], -j))\n      if not q: continue\n      _, c, j = heappop(q); j = -j \n      s[i], s[j] = s[j], s[i]\n      r -= c \n      cost[i] = cost[j] = 0\n    print(''.join(s))\n      \n  def D(): pass \n\n\nclass ABC010():\n  def A():\n    print(sys.stdin.readline().rstrip()+'pp')\n  def B():\n    n, *a = map(int, sys.stdin.read().split())\n    tot = 0\n    for x in a:\n      c = 0 \n      while x%2==0 or x%3==2:\n        x -= 1\n        c += 1\n      tot += c\n    print(tot)\n\n  def C():\n    sx, sy, gx, gy, t, v, n, *xy = map(int, sys.stdin.read().split())\n    x, y = np.array(xy).reshape(-1, 2).T\n    def dist(x1, y1, x2, y2):\n      return np.sqrt((x2-x1)**2 + (y2-y1)**2)\n    ans = 'YES' if (dist(sx, sy, x, y)+dist(x, y, gx, gy) <= v*t).any() else 'NO'\n    print(ans)\n\n  def D(): pass \n\nclass ABC011():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print(n%12+1)\n\n  def B():\n    s = sys.stdin.readline().rstrip() \n    print(s[0].upper()+s[1:].lower())\n\n  def C():\n    n, *ng = map(int, sys.stdin.read().split())\n    ng = set(ng)\n    if n in ng: print('NO')\n    else:\n      r = 100\n      while n > 0:\n        if r == 0: print('NO'); return\n        for i in range(3, 0, -1):\n          if (n-i) in ng: continue \n          n -= i\n          r -= 1\n          break \n        else: print('NO'); return \n      print('YES')\n\n  def D(): pass \n\nclass ABC040():\n  def A():\n    n, x = map(int, sys.stdin.readline().split())\n    print(min(x-1, n-x))\n\n  def B():\n    n = int(sys.stdin.readline().rstrip())\n    res = inf \n    for i in range(1, int(n**.5)+1):\n      res = min(res, n//i-i+n%i)\n    print(res)\n\n  def C():\n    n, *h = map(int, sys.stdin.read().split())\n    h = [h[0]]+h\n    cost = [None] * (n+1); cost[0] = cost[1] = 0\n    for i in range(2, n+1):\n      cost[i] = min(\n        cost[i-2] + abs(h[i]-h[i-2]),\n        cost[i-1] + abs(h[i]-h[i-1])\n      )\n    print(cost[n])\n\n  def D(): pass\n\n\nclass ABC041():\n  def A():\n    s, i = sys.stdin.read().split()\n    i = int(i)\n    print(s[i-1])\n\n  def B():\n    a, b, c = map(int, sys.stdin.readline().split())\n    ans = a * b % MOD * c % MOD \n    print(ans)\n\n  def C():\n    n, *a = map(int, sys.stdin.read().split())\n    for i, h in sorted(enumerate(a), key=lambda x: -x[1]):\n      print(i+1)\n\n  def D():\n    n, m, *xy = map(int, sys.stdin.read().split())\n    *xy, = zip(*[iter(xy)]*2)\n    edges = [0] * n \n    for x, y in xy:\n      x -= 1; y -= 1\n      edges[x] |= 1<<y\n    comb = [None] * (1<<n); comb[0] = 1\n    def count(edges, bit):\n      if comb[bit] is not None: return comb[bit]\n      comb[bit] = 0\n      for i in range(n):\n        if (bit>>i) & 1 and not edges[i]:\n          nxt_bit = bit & ~(1<<i)\n          nxt_edges = edges.copy() \n          for j in range(n):\n            nxt_edges[j] &= ~(1<<i)\n          cnt = count(nxt_edges, nxt_bit)\n          comb[bit] += cnt\n      return comb[bit]\n    print(count(edges, (1<<n)-1))\n\n\nclass ABC042():\n  def A():\n    a = [int(x) for x in sys.stdin.readline().split()]\n    c = Counter(a)\n    print('YES' if c[5]==2 and c[7]==1 else 'NO')\n\n  def B():\n    n, l, *s = sys.stdin.read().split()\n    print(''.join(sorted(s)))\n\n  def C():\n    n, k, *d = sys.stdin.read().split()\n    l = len(n)\n    ok = sorted(set(string.digits)-set(d))\n    cand = [int(''.join(p)) for p in product(ok, repeat=l)] + [int(min(x for x in ok if x > '0')+min(ok)*l)]\n    print(cand[bi_l(cand, int(n))])\n\n  def D():\n    h, w, a, b = map(int, sys.stdin.read().split())\n    combinatorics = Combinatorics(n=2*10**5, mod=MOD, numpy=True)\n    tot = combinatorics.mod_choose(h+w-2, h-1)\n    i = np.arange(h-a, h)\n    ng = np.sum(combinatorics.mod_choose(i+b-1, i) * combinatorics.mod_choose(h-i+w-b-2, h-1-i) % MOD)\n    tot -= ng; tot %= MOD\n    print(tot)\n\n\nclass ABC043():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    print((1+n)*n//2)\n\n  def B():\n    s = sys.stdin.readline().rstrip()\n    t = ''\n    for c in s:\n      if c == 'B': t = t[:-1]\n      else: t += c\n    print(t)\n\n  def C():\n    n, *a = map(int, sys.stdin.read().split())\n    a = np.array(a)\n    x = np.around(a.sum()/n).astype(int)\n    print(np.sum((a-x)**2))\n\n  def D():\n    s = sys.stdin.readline().rstrip()\n    n = len(s)\n    for i in range(n-1):\n      if s[i] == s[i+1]:\n        print(i+1, i+2); return \n    for i in range(n-2):\n      if s[i] == s[i+2]:\n        print(i+1, i+3); return \n    print(-1, -1)\n\n\nclass ABC170():\n  def A():\n    x = [int(x) for x in sys.stdin.readline().split()]\n    for i in range(5):\n      if x[i] != i+1:\n        print(i+1)\n        break\n\n  def B():\n    x, y = map(int, sys.stdin.readline().split())\n    print('Yes' if 2*x <= y <= 4*x and y%2 == 0 else 'No')\n      \n  def C():\n    x, n, *p = map(int, sys.stdin.read().split())\n    a = list(set(range(102)) - set(p))\n    a = [(abs(y-x), y) for y in a]\n    print(sorted(a)[0][1])\n\n  def D():\n    n, *a = map(int, sys.stdin.read().split())\n    cand = set(a)\n    cnt = 0\n    for x, c in sorted(Counter(a).items()):\n      cnt += c == 1 and x in cand\n      cand -= set(range(x*2, 10**6+1, x))\n    print(cnt)\n\n  def E():\n    n, q = map(int, sys.stdin.readline().split())\n    queue = [] \n    m = 2*10**5\n    infants = [[] for _ in range(m)]\n    highest_rate = [None] * m\n    where = [None] * n\n    rate = [None] * n\n\n    def entry(i, k):\n      where[i] = k\n      while infants[k]:\n        r, j = heappop(infants[k])\n        if where[j] != k or j == i: continue \n        if rate[i] >= -r:\n          highest_rate[k] = rate[i]\n          heappush(queue, (rate[i], k, i))\n        heappush(infants[k], (r, j))\n        break\n      else:\n        highest_rate[k] = rate[i]\n        heappush(queue, (rate[i], k, i))\n      heappush(infants[k], (-rate[i], i))\n\n    def transfer(i, k):\n      now = where[i]\n      while infants[now]:\n        r, j = heappop(infants[now])\n        if where[j] != now or j == i: continue\n        if highest_rate[now] != -r:\n          highest_rate[now] = -r\n          heappush(queue, (-r, now, j))\n        heappush(infants[now], (r, j))\n        break\n      else:\n        highest_rate[now] = None\n      entry(i, k)\n\n    def inquire():\n      while True:\n        r, k, i = heappop(queue)\n        if where[i] != k or r != highest_rate[k]: continue \n        heappush(queue, (r, k, i))\n        return r\n\n    for i in range(n):\n      a, b = map(int, sys.stdin.readline().split())\n      rate[i] = a \n      entry(i, b-1)\n    for _ in range(q):\n      c, d = map(int, sys.stdin.readline().split())\n      transfer(c-1, d-1)\n      print(inquire())\n    \n  def F(): pass \n\n\nclass ABC171():\n  def A():\n    c = sys.stdin.readline().rstrip()\n    print('A' if c < 'a' else 'a')\n\n  def B():\n    n, k, *p = map(int, sys.stdin.read().split())\n    print(sum(sorted(p)[:k]))\n\n  def C():\n    n = int(sys.stdin.readline().rstrip())\n    n -= 1\n    l = 1\n    while True:\n      if n < pow(26, l):\n        break \n      n -= pow(26, l)\n      l += 1\n    res = ''.join([chr(ord('a')+d) for d in NumberTheory.base_convert(n, 26)][::-1])\n    res = 'a'*(l-len(res)) + res\n    print(res)\n\n  def D():\n    n = int(sys.stdin.readline().rstrip())\n    a = [int(x) for x in sys.stdin.readline().split()]\n    s = sum(a)\n    cnt = Counter(a)\n    q = int(sys.stdin.readline().rstrip())\n    for _ in range(q):\n      b, c = map(int, sys.stdin.readline().split())\n      s += (c-b)*cnt[b]\n      print(s)\n      cnt[c] += cnt[b]; cnt[b] = 0\n\n  def E():\n    n, *a = map(int, sys.stdin.read().split())\n    s = 0\n    for x in a: s ^= x \n    b = map(lambda x: x^s, a)\n    print(*b, sep=' ')\n\n  def F(): pass \n\n\nclass ABC172():\n  def A(): pass\n  def B(): pass\n  def C(): pass \n  def D(): pass \n  def E(): pass \n  def F(): pass \n\n\nclass ABC173():\n  def A():\n    n = int(sys.stdin.readline().rstrip())\n    charge = (n+999)//1000 * 1000 - n\n    print(charge)\n\n  def B():\n    n, *s = sys.stdin.read().split() \n    c = Counter(s)\n    for v in 'AC, WA, TLE, RE'.split(', '):\n      print(f'{v} x {c[v]}')\n\n  def C():\n    h, w, k = map(int, sys.stdin.readline().split())\n    c = [sys.stdin.readline().rstrip() for _ in range(h)]\n    tot = 0\n    for i in range(1<<h):\n      for j in range(1<<w):\n        cnt = 0\n        for y in range(h):\n          for x in range(w):\n            if i>>y & 1 or j>>x & 1:\n              continue \n            cnt += c[y][x] ==  '#'\n        tot += cnt == k\n    print(tot)\n\n  def D():\n    n, *a = map(int, sys.stdin.read().split())\n    a.sort(reverse=True)\n    res = a[0] + sum(a[1:1+(n-2)//2])*2 + a[1+(n-2)//2]*(n & 1)\n    print(res)\n\n  def E():\n    MOD = 10**9+7\n    n, k, *a = map(int, sys.stdin.read().split())\n    minus = [x for x in a if x < 0]\n    plus = [x for x in a if x > 0]\n    if len(plus) + len(minus)//2*2 >= k: # plus \n      *minus, = map(abs, minus)\n      minus.sort(reverse=True)\n      plus.sort(reverse=True)\n      cand = []\n      if len(minus)&1: minus = minus[:-1]\n      for i in range(0, len(minus)-1, 2):\n        cand.append(minus[i]*minus[i+1]%MOD)\n      if k & 1:\n        res = plus[0]\n        plus = plus[1:]\n      else:\n        res = 1\n      if len(plus)&1: plus = plus[:-1]\n      for i in range(0, len(plus)-1, 2):\n        cand.append(plus[i]*plus[i+1]%MOD)\n      cand.sort(reverse=True)\n      for x in cand[:k//2]:\n        res *= x\n        res %= MOD \n      print(res)\n    elif 0 in a:\n      print(0)\n    else:\n      cand = sorted(map(abs, a))\n      res = 1\n      for i in range(k):\n        res *= cand[i]\n        res %= MOD\n      res = MOD - res\n      print(res)\n      pass\n  \n  def F(): pass \n\n\ndef __starting_point():\n  # ABC040.D()\n  ABC170.E()\n__starting_point()", "from collections import defaultdict\nimport heapq\n\nINF_MAX = 10 ** 10\n\ndef set_remove(hp,dct,x):\n    dct[x] += 1\n\ndef set_getmin(hp,dct):\n    while True:\n        if len(hp) == 0:\n            return INF_MAX\n        a = hp[0]\n        if dct[a]:\n            dct[a] -= 1\n            heapq.heappop(hp)\n        else:\n            return a\n\nN,Q = map(int,input().split())\nA = [0]*N\nB = [0]*N\nC = [0]*Q\nD = [0]*Q\nE = [-1]*N\nG = set()\nhps = dict()\ndcts = dict()\nb,c,d,FROM,TO = 0,0,0,0,0\nfor i in range(N):\n    A[i],b = map(int,input().split())\n    b -= 1\n    B[i] = b\n    G.add(b)\nfor i in range(Q):\n    c,d = map(int,input().split())\n    c -= 1\n    d -= 1\n    C[i] = c\n    D[i] = d\n    G.add(d)\n\nG.add(-1)\nfor g in G:\n    hps[g] = list()\n    dcts[g] = defaultdict(int)\n\nfor i in range(N):\n    b = B[i]\n    heapq.heappush(hps[b],-A[i])\n    E[i] = b\n\nhps[-1] = [-hps[b][0] for b in set(B)]\nheapq.heapify(hps[-1])\n\nfor i in range(Q):\n    c = C[i]\n    FROM = E[c]\n    TO = D[i]\n    E[c] = TO\n    c = A[c]\n    # \u8ee2\u6821\u5143\u3067\u306e\u51e6\u7406\n    b = set_getmin(hps[FROM],dcts[FROM])\n    b *= -1\n    if c == b:\n        set_remove(hps[-1],dcts[-1],c)\n        set_remove(hps[FROM],dcts[FROM],-c)\n        d = set_getmin(hps[FROM],dcts[FROM])\n        if d != INF_MAX:\n            d *= -1\n            heapq.heappush(hps[-1],d)\n    else:\n        set_remove(hps[FROM],dcts[FROM],-c)\n\n    # \u8ee2\u6821\u5148\u3067\u306e\u51e6\u7406\n    b = set_getmin(hps[TO],dcts[TO])\n    if b != INF_MAX:\n        b *= -1\n        if c > b:\n            set_remove(hps[-1],dcts[-1],b)\n            heapq.heappush(hps[-1],c)\n    else:\n        heapq.heappush(hps[-1],c)\n    heapq.heappush(hps[TO],-c)\n    print(set_getmin(hps[-1],dcts[-1]))", "import sys\nfrom heapq import heapify, heappop, heappushpop, heappush\n\nM = 2*10**5\ninput = sys.stdin.readline\nN, Q = list(map(int, input().split()))\nrates = [0] * N\nwheres = [0] * N\nkgs = [[(0, 0)] for _ in range(M)]\nfor i in range(N):\n    a, b = list(map(int, input().split()))\n    rates[i] = a\n    wheres[i] = b-1\n    heappush(kgs[b-1], (-a, i))\nrankers = []\nfor kg in kgs:\n    v = kg[0]\n    if v[0] != 0:\n        heappush(rankers, (-v[0], v[1], wheres[v[1]]))\n\ndef fetch_max(i):\n    while True:\n        v = kgs[i][0]\n        if v[0] == 0 or wheres[v[1]] == i:\n            return v\n        heappop(kgs[i])\n\ndef fetch_min():\n    while True:\n        v = rankers[0]\n        w = fetch_max(v[2])\n        if w[0] != 0 and w[1] == v[1]:\n            return v\n        heappop(rankers)\n\ndef solve():\n    for _ in range(Q):\n        c, d = list(map(int, input().split()))\n        ibkg, iakg = wheres[c-1], d-1\n        wheres[c-1] = d-1\n        heappush(kgs[iakg], (-rates[c-1], c-1))\n\n        bef = fetch_max(ibkg)\n        heappush(rankers, (-bef[0], bef[1], ibkg))\n\n        aft = kgs[iakg][0]\n        heappush(rankers, (-aft[0], aft[1], iakg))\n\n        print((fetch_min()[0]))\n\ndef __starting_point():\n    solve()\n\n__starting_point()", "from heapq import heappop, heappush\n\nencode_kindy = lambda x, y: -((x << 18) + y)\ndecode_kindy = lambda x: (-x >> 18, -x & ((1 << 18) - 1))\nencode_smarts = lambda x, y, z: ((x << 36) + (y << 18) + z)\ndecode_smarts_rate = lambda x: x >> 36\n\n\nclass DeletableHeapq:\n    def __init__(self, *initial_values):\n        self.size = 0\n        self._set = set()\n        self._heap = []\n\n        if initial_values:\n            for v in initial_values:\n                self.push(v)\n\n    @property\n    def top(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        return self._heap[0]\n\n    def pop(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        res = heappop(self._heap)\n        self._set.discard(res)\n        self.size -= 1\n        return res\n\n    def push(self, x):\n        self.size += 1\n        heappush(self._heap, x)\n        self._set.add(x)\n\n    def delete(self, x):\n        self.size -= 1\n        self._set.discard(x)\n\n\ndef main():\n    N, _, *X = list(map(int, open(0).read().split()))\n    AB, CD = X[: 2 * N], X[2 * N :]\n    rate, belonging = [0] * (N + 1), [0] * (N + 1)\n    kindy = [DeletableHeapq() for _ in range(200_001)]\n\n    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):\n        rate[i], belonging[i] = a, b\n        kindy[b].push(encode_kindy(a, i))\n\n    smart_infants = DeletableHeapq(\n        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)\n    )\n\n    res = []\n    for c, next_k in zip(*[iter(CD)] * 2):\n        prev_k = belonging[c]\n        belonging[c] = next_k\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        kindy[prev_k].delete(encode_kindy(rate[c], c))\n        kindy[next_k].push(encode_kindy(rate[c], c))\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        res.append(decode_smarts_rate(smart_infants.top))\n\n    print((\"\\n\".join(map(str, res))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import heappop, heappush\n\n\nclass DeletableHeapq:\n    \"\"\"Deletable Heapq: A heapq supporting lazy deletion of values.\"\"\"\n\n    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:\n        self.is_max_heap = is_max_heap\n        self.size = 0\n        self._set = set()\n        self._heap = []\n\n        if initial_values:\n            for v in initial_values:\n                self.push(v)\n\n    @property\n    def top(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        return self._heap[0] if not self.is_max_heap else -self._heap[0]\n\n    def pop(self):\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        self.size -= 1\n        res = heappop(self._heap)\n        self._set.discard(res)\n        return res if not self.is_max_heap else -res\n\n    def push(self, value):\n        if value is None:\n            return\n        if self.is_max_heap:\n            value = -value\n        if value in self._set:\n            return\n        self.size += 1\n        heappush(self._heap, value)\n        self._set.add(value)\n\n    def delete(self, value):\n        if value is None:\n            return\n        if self.is_max_heap:\n            value = -value\n        if value not in self._set:\n            return\n        self.size -= 1\n        self._set.discard(value)\n\n\ndef main():\n    # https://atcoder.jp/contests/abc170/tasks/abc170_e\n    encode_kindy = lambda x, y: (x << 18) + y\n    decode_kindy = lambda x: (x >> 18, x & ((1 << 18) - 1))\n    encode_smarts = lambda x, y, z: (x << 36) + (y << 18) + z\n    decode_smarts_rate = lambda x: x >> 36\n\n    N, _, *X = list(map(int, open(0).read().split()))\n    AB, CD = X[: 2 * N], X[2 * N :]\n    rate, belonging = [0] * (N + 1), [0] * (N + 1)\n    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]\n\n    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):\n        rate[i], belonging[i] = a, b\n        kindy[b].push(encode_kindy(a, i))\n\n    smart_infants = DeletableHeapq(\n        *(encode_smarts(*decode_kindy(k.top), i) for i, k in enumerate(kindy) if k.size)\n    )\n    res = []\n    for c, next_k in zip(*[iter(CD)] * 2):\n        prev_k = belonging[c]\n        belonging[c] = next_k\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.delete(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        kindy[prev_k].delete(encode_kindy(rate[c], c))\n        kindy[next_k].push(encode_kindy(rate[c], c))\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.push(encode_smarts(*decode_kindy(kindy[k].top), k))\n\n        res.append(decode_smarts_rate(smart_infants.top))\n\n    print((\"\\n\".join(map(str, res))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "\ndef main():\n    import heapq\n    import sys\n    input = sys.stdin.readline\n    \n    N, Q = map(int, input().split())\n    AB = [tuple(map(int, input().split())) for _ in range(N)]\n    CD = [tuple(map(int, input().split())) for _ in range(Q)]\n\n    maximum = 2*10**5\n\n    B = [[] for _ in range(maximum)]\n    member = [set() for _ in range(maximum)]\n    belongs = [-1]*N\n\n    for i,(a,b) in enumerate(AB):\n        b -= 1\n        heapq.heappush(B[b], (-a,i))\n        member[b].add(i)\n        belongs[i] = b\n\n\n    maximum_list = []\n    for i,b in enumerate(B):\n        if len(b) > 0:\n            heapq.heappush(maximum_list, (-b[0][0], i))\n    \n    Inf = [0] * maximum\n    for c, d in CD:\n        c -= 1\n        d -= 1\n        before = belongs[c]\n        belongs[c] = d\n        member[before].remove(c)\n        member[d].add(c)\n        for i in Inf:\n            if len(B[before]) <= 0:\n                break\n            if B[before][0][1] in member[before]:\n                break\n            else:\n                heapq.heappop(B[before])\n        \n        if len(B[before]) > 0:\n            heapq.heappush(maximum_list, (-B[before][0][0], before))\n        \n        heapq.heappush(B[d], (-AB[c][0], c))\n        heapq.heappush(maximum_list, (AB[c][0], d))\n        for i in Inf:\n            minmum, num = maximum_list[0]\n            if len(B[num]) == 0 or -B[num][0][0] != minmum:\n                heapq.heappop(maximum_list)\n            else:\n                print(minmum)\n                break\n\nmain()", "import sys\nreadline = sys.stdin.readline\nfrom collections import defaultdict as ddict\nimport heapq as hq\n\nN,Q = list(map(int,readline().split()))\n\n# \u5712\u5150\u306e\u60c5\u5831[\u30ec\u30fc\u30c8, \u73fe\u5728\u306e\u5712]\u3092index\u3067\u53d6\u5f97\u3067\u304d\u308b\u3088\u3046\u306b\u7ba1\u7406\u3059\u308b\n# \u8ee2\u5712\u3057\u305f\u3089\u3001\"\u73fe\u5728\u306e\u5712\"\u3092\u5e38\u306b\u66f4\u65b0\u3059\u308b\n# \u5168\u3066\u306e\u5712\u306b\u3064\u3044\u3066\u3001(-rate, \u5712\u5150\u306eID)\u3067\u5712\u5150\u60c5\u5831\u3092\u6301\u3064\n# heapq\u3067\u6700\u5f37\u306e\u5712\u5150(rate * -1)\u3092\u78ba\u8a8d\u3067\u304d\u308b\u3088\u3046\u306b\u3059\u308b\uff08pop\u3057\u306a\u3044\uff09\n# \u53d6\u308a\u51fa\u3057\u305f\u5712\u5150\u306e\u6240\u5c5e\u3092\u8abf\u3079\u3066\u3001\u73fe\u5728\u306e\u6240\u5c5e\u3068\u7570\u306a\u308b\u3088\u3046\u3067\u3042\u308c\u3070\u7834\u68c4\uff08\u8ee2\u5712\u6e08\uff09\n# \u7834\u68c4\u3059\u308b\u3068\u304d\u306b\u521d\u3081\u3066pop\u3059\u308b\n\n# \u5168\u4f53\u306b\u3064\u3044\u3066\u306f\u3001(\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7)\u3092\u7ba1\u7406\u3059\u308bheapq\u3092\u6301\u3064\n# \u8ee2\u5712\u304c\u3042\u308b\u3068\u6700\u5f37\u30ec\u30fc\u30c8\u304c\u5909\u308f\u308a\u5f97\u308b\u305f\u3081\u3001\u6bce\u56de\u306e\u51e6\u7406\u3054\u3068\u306b\n# \u30fb\u8ee2\u5712\u5143\u306e\u5712\u306e\u6700\u65b0\u306e(\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7)\n# \u30fb\u8ee2\u5712\u5148\u306e\u5712\u306e\u6700\u65b0\u306e(\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7)\n# \u3092heapq\u306b\u683c\u7d0d\u3059\u308b\n# \u5148\u982d\u306e\u5712\u306b\u3064\u3044\u3066\u3001\u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3068\u7167\u5408\u3057\u3066\uff08\u6b63\u8ca0\u306b\u6ce8\u610f\uff09\u3001\n# \u4e00\u81f4\u3057\u306a\u3051\u308c\u3070\u60c5\u5831\u304c\u53e4\u3044\u306e\u3067\u7834\u68c4(pop)\n\nNN = 2 * (10 ** 5)\n#NN = 4\ninfants = [None] * (N + 1)\nkinda = [[] for i in range(NN + 1)] # (-1 * \u30ec\u30fc\u30c8,\u5712\u5150ID)\nfor i in range(N):\n  a,b = list(map(int,readline().split()))\n  infants[i + 1] = [a,b]\n  hq.heappush(kinda[b], (-a, i + 1))\n\n#print(\"kinda\",kinda)\n# \u5168\u4f53\u306e\u6700\u5f37\u5712\u5150\u60c5\u5831\u3000\uff08\u6700\u5f37\u5712\u5150\u306e\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7\uff09\nall_kinda = [] # (\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7)\n# \u6700\u521d\u306b\u3001\u73fe\u5728\u306e\u6700\u5f37\u5712\u5150\u3092\u5168\u3066\u683c\u7d0d\u3059\u308b\nfor i in range(len(kinda)):\n  if kinda[i]:\n    hq.heappush(all_kinda, ((-1) * (kinda[i][0][0]), i))\n    \n#print(\"all_kinda\",all_kinda)\ndef search_max_rate_from_kinda(x): # \u3042\u308b\u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u6b63\u306e\u6570\u3067\u8fd4\u3059\n  q = kinda[x]\n  while q:\n    rate, infant_id = q[0] # \u30ec\u30fc\u30c8\u306f\u8ca0\u306e\u6570\n    # \u53d6\u308a\u51fa\u3057\u305f\u5712\u5150\u304c\u3001\u73fe\u5728\u3082x\u306b\u6240\u5c5e\u3057\u3066\u3044\u308b\u304b\u3092\u8abf\u3079\u308b\n    if infants[infant_id][1] != x:\n      # \u8ee2\u5712\u6e08\n      hq.heappop(q)\n    else:\n      # \u73fe\u5728\u3082\u6240\u5c5e\u3057\u3066\u3044\u308b\n      return -rate # \u6b63\u8ca0\u3092\u53cd\u8ee2\u3057\u3066\u8fd4\u3059\n  return -1 # \u5168\u54e1\u304c\u8ee2\u5712\u6e08\u307f\u3060\u3063\u305f\u5834\u5408\n  \nfor i in range(Q):\n  target, new_kinda_id = list(map(int,readline().split())) # \u5712\u5150, \u8ee2\u5712\u5148\n  # \u73fe\u5728\u306e\u5712\u3068\u30ec\u30fc\u30c8\u3092\u8abf\u3079\u308b\n  rate, old_kinda_id = infants[target]\n  # \u73fe\u5728\u306e\u5712\u3092\u6700\u65b0\u306b\u4fdd\u3064\n  infants[target][1] = new_kinda_id\n  # \u8ee2\u5712\u5148\u306b\u5712\u5150\u3092\u8ffd\u52a0\u3059\u308b\n  hq.heappush(kinda[new_kinda_id],(-rate, target))\n  \n  # \u8ee2\u5712\u5143\u306e\u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u53d6\u308a\u51fa\u3057\u3001\u5168\u4f53\u306e\u30ad\u30e5\u30fc\u306b\u8ffd\u52a0\n  old_kinda_rate = search_max_rate_from_kinda(old_kinda_id)\n  if old_kinda_rate != -1:\n    hq.heappush(all_kinda, (old_kinda_rate, old_kinda_id))\n  \n  # \u8ee2\u5712\u5148\u306e\u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u53d6\u308a\u51fa\u3057\u3001\u5168\u4f53\u306e\u30ad\u30e5\u30fc\u306b\u8ffd\u52a0\n  new_kinda_rate = search_max_rate_from_kinda(new_kinda_id)\n  if new_kinda_rate != -1:\n    hq.heappush(all_kinda, (new_kinda_rate, new_kinda_id))\n    \n  #print(\"i\",i,\"kinda\",kinda)\n  #print(\"i\",i,\"all_kinda\",all_kinda)\n  # \u5168\u4f53\u306e\u30ad\u30e5\u30fc\u306e\u5148\u982d\u306b\u3044\u308b(\u6700\u5f31\u30ec\u30fc\u30c8, \u5712\u306e\u756a\u53f7)\u306b\u3064\u3044\u3066\u3001\n  # \u305d\u306e\u5712\u306e\u6700\u5f37\u5712\u5150\u3068\u4e00\u81f4\u3057\u3066\u3044\u308c\u3070\u51fa\u529b\u3059\u308b\n  while all_kinda:\n    weakest_rate, kinda_id = all_kinda[0]\n    current_max_rate = search_max_rate_from_kinda(kinda_id)\n    if weakest_rate != current_max_rate:\n      # \u60c5\u5831\u304c\u53e4\u3044\n      hq.heappop(all_kinda)\n    else:\n      print(weakest_rate)\n      break\n", "import heapq\nimport sys\ninput = sys.stdin.readline\n\nN, Q = list(map(int, input().split()))\nAB = [tuple(map(int, input().split())) for _ in range(N)]\nCD = [tuple(map(int, input().split())) for _ in range(Q)]\nH = 2*10**5 # \u5e7c\u7a1a\u5712\n\nINF = 10**18\nrates = [[] for _ in range(H)]\nmembers = [set() for _ in range(H)]\nbelongs = [-1]*N\nfor i,(a,b) in enumerate(AB):\n    b -= 1\n    heapq.heappush(rates[b], (-a,i))\n    members[b].add(i)\n    belongs[i] = b\n\nmxrates = []\nfor num,r in enumerate(rates):\n    if len(r) > 0:\n        heapq.heappush(mxrates, (-r[0][0], num)) # \u5e7c\u7a1a\u5712\u3054\u3068\u306e\u6700\u5927\u5024\u3092\u3044\u308c\u308b\n\nfor c,d in CD:\n    c, d = c-1, d-1\n    old = belongs[c]\n    belongs[c] = d\n    members[old].remove(c)\n    members[d].add(c)\n    # \u8ee2\u5712\u5143\u306e\u6700\u5927\u5024\u3092\u6700\u65b0\u5316\u3059\u308b\n    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:\n        heapq.heappop(rates[old])\n    # \u6700\u65b0\u5316\u3055\u308c\u305f\u8ee2\u5712\u5143\u304b\u3089\u6539\u3081\u3066\u53d6\u5f97\n    if len(rates[old]) > 0:\n        heapq.heappush(mxrates, (-rates[old][0][0], old))\n    # \u8ee2\u5712\u5148\u306b\u8ffd\u52a0\n    heapq.heappush(rates[d], (-AB[c][0], c))\n    heapq.heappush(mxrates, (AB[c][0], d))\n    while mxrates:\n        rate, num = mxrates[0]\n        # mxrates\u306e\u6700\u5c0f\u304c\u6700\u65b0\u3067\u306f\u306a\u3044\u5834\u5408\n        if len(rates[num]) == 0 or -rates[num][0][0] != rate:\n            heapq.heappop(mxrates)\n        else:\n            print(rate)\n            break\n", "import heapq\nN,Q=map(int,input().split())\nM=2*(10**5)\nbelong=[]\nrate=[]\ngarden=[[]for _ in range(M)]\nfor c in range(N):\n    A,B=map(int,input().split())\n    B-=1\n    belong.append(B)\n    rate.append(A)\n    heapq.heappush(garden[B],(-A,c))\n    \nstrong=[]\n\nfor i in range(M):\n    if garden[i]:\n        A,c=garden[i][0]\n        heapq.heappush(strong,(-A,c,i))\n        \nfor i in range(Q):\n    C,D=map(int,input().split())\n    C-=1\n    D-=1\n    now=belong[C]\n    belong[C]=D\n    \n    while garden[now]:\n        A,c=garden[now][0]\n        if belong[c]!=now:\n            heapq.heappop(garden[now])\n        else:\n            heapq.heappush(strong,(-A,c,now))\n            break\n            \n    heapq.heappush(garden[D],(-rate[C],C))\n    while garden[D]:\n        A,c=garden[D][0]\n        heapq.heappush(strong,(-A,c,D))\n        break\n    \n    while strong:\n        A,c,d=strong[0]\n        if belong[c]!=d or garden[d][0][1]!=c:\n            heapq.heappop(strong)\n        else:\n            print(A)\n            break", "# -*- coding:utf-8 -*-\n\ndef solve():\n    import heapq\n\n    M = 2*(10**5)\n    N, Q = list(map(int, input().split()))\n    As, Bs = [], []\n    yochien = [list() for _ in range(M)]  # \u5e7c\u7a1a\u5712\n    for i in range(N):\n        a, b = list(map(int, input().split()))\n        b = b - 1\n        As.append(a), Bs.append(b)\n        heapq.heappush(yochien[b], (-a, i))  # \u5e7c\u7a1a\u5712b\u306b\u3001\u5e7c\u5150i\u306e\u30ec\u30fc\u30c8a\u3092\u3001\u30d7\u30e9\u30a4\u30aa\u30ea\u30c6\u30a3\u30ad\u30e5\u30fc\u3067\u6301\u3064\u3002\uff08\u5148\u982d\u306b\u6700\u3082\u5927\u304d\u3044\u30ec\u30fc\u30c8\u306e\u5e7c\u5150\u304c\u304f\u308b\u3088\u3046\u306b\u3059\u308b\uff09\n\n    # \u5404\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u9023\u4e2d\u306e\u5e7c\u5150\u60c5\u5831\u3092\u3001\u30d7\u30e9\u30a4\u30aa\u30ea\u30c6\u30a3\u30ad\u30e5\u30fctop\u306b\u3076\u3061\u3053\u3080\u3002\n    # \u5e7c\u5150\u60c5\u5831\u306f(\u30ec\u30fc\u30c8, \u5e7c\u5150, \u6240\u5c5e\u5e7c\u7a1a\u5712)\u306e\u5f62\u5f0f\u3067\u3076\u3061\u3053\u3080\n    # \u3059\u306a\u308f\u3061\u3001top[0]\u306b\u306f\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u9023\u4e2d\u306e\u6700\u4f4e\u30ec\u30fc\u30c8\u306e\u5e7c\u5150\u60c5\u5831\u304c\u5165\u3063\u3066\u3044\u308b\u3002\n    # \u300c\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u9023\u4e2d\u306e\u6700\u4f4e\u30ec\u30fc\u30c8\u5e7c\u5150\u300d\u306f\u9577\u3044\u306e\u3067\u3001\u4ee5\u964d\u300c\u5e73\u7b49\u30ec\u30fc\u30c8\u5e7c\u5150\u300d\u3068\u547c\u3076\u3002\n    top = []\n    for m in range(M):\n        if yochien[m]:\n            heapq.heappush(top, (-yochien[m][0][0], yochien[m][0][1], m))\n\n    # \u30af\u30a8\u30ea\u3092\u51e6\u7406\u3059\u308b\n    for _ in range(Q):\n        # \u5e7c\u5150c\u3092\u5e7c\u7a1a\u5712d\u306b\u8ee2\u5712\u3055\u305b\u305f\u3044\n        c, d = list(map(int, input().split()))\n        c, d = c-1, d-1\n\n        before = Bs[c]  # \u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\n        Bs[c] = d\n\n        # \u5e7c\u5150c\u3092\u5e7c\u7a1a\u5712d\u306b\u8ee2\u5712\u3059\u308b\n        heapq.heappush(yochien[d], (-As[c], c))\n\n        if yochien[d][0][1] == c:\n            # \u5e7c\u5150c\u304c\u8ee2\u5712\u5148\u306e\u5e7c\u7a1a\u5712d\u3067\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u306b\u306a\u3063\u305f\u306a\u3089\u3070\u3001\u30c8\u30c3\u30d7\u3092\u66f4\u65b0\u3059\u308b\n            heapq.heappush(top, (As[c], c, d))\n\n        flag = False  # \u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u304c\u5909\u308f\u3063\u305f\u304b\uff1f\n        while yochien[before] and Bs[yochien[before][0][1]] != before:\n            # \u300c\u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u304c\u7a7a\u3058\u3083\u306a\u3044\u300d\u3001\u304b\u3064\u3001\u300c\u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u304c\u5909\u308f\u3063\u305f\u300d\u306a\u3089\u3070\u3001\n            # \u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u3092\u524a\u9664\u3059\u308b\n            heapq.heappop(yochien[before])\n            flag = True\n\n        if flag and yochien[before]:\n            # \u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u304c\u5909\u308f\u3063\u3066\u3057\u307e\u3044\u3001\u307e\u3060\u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306b\u5e7c\u5150\u304c\u5b58\u5728\u3059\u308b\u306a\u3089\u3070\u3001\n            # \u8ee2\u5712\u524d\u306e\u5e7c\u7a1a\u5712\u306e\u30c8\u30c3\u30d7\u30b3\u30fc\u30c0\u30fc\u306f\u305d\u306e\u5e7c\u5150\u306b\u306a\u308b\n            heapq.heappush(top, (-yochien[before][0][0], yochien[before][0][1], before))\n\n        while not yochien[top[0][2]] or yochien[top[0][2]][0][1] != top[0][1]:\n            # \u300c\u5e73\u7b49\u30ec\u30fc\u30c8\u5e7c\u5150\u306e\u6240\u5c5e\u5e7c\u7a1a\u5712\u304c\u7a7a\u3058\u3083\u306a\u3044\u300d\u3001\u307e\u305f\u306f\u3001\u300c\u5e73\u7b49\u30ec\u30fc\u30c8\u5e7c\u5150\u304c\u5909\u308f\u3063\u305f\u300d\u306a\u3089\u3070\u3001\n            # \u5e73\u7b49\u30ec\u30fc\u30c8\u5e7c\u5150\u3092\u66f4\u65b0\u3059\u308b\n            heapq.heappop(top)\n\n        # \u5e73\u7b49\u3055\uff08\u5e73\u7b49\u30ec\u30fc\u30c8\u5e7c\u5150\u306e\u30ec\u30fc\u30c8\u5024\uff09\u3092\u8868\u793a\u3059\u308b\n        print((top[0][0]))\n\n\ndef __starting_point():\n    solve()\n\n__starting_point()", "import sys\nimport  math\nimport fractions\nimport heapq\nimport copy\nfrom collections import defaultdict\nstdin = sys.stdin\n     \nns = lambda: stdin.readline().rstrip()\nni = lambda: int(stdin.readline().rstrip())\nnm = lambda: map(int, stdin.readline().split())\nnl = lambda: list(map(int, stdin.readline().split()))\n\n\nclass My_heapavi():\n    def __init__(self):\n        self.p = list()\n        self.q = list()\n        self.p2 = list()\n        self.q2 = list()\n\n    def insert(self,x):\n        heapq.heappush(self.p, x)\n        heapq.heappush(self.p2,-x)\n        return\n\n    def erase(self,x):\n        heapq.heappush(self.q, x)\n        heapq.heappush(self.q2,-x)\n        return\n\n    def minimum(self):\n        while self.q and self.p[0] == self.q[0]:\n            heapq.heappop(self.p)\n            heapq.heappop(self.q)\n        return self.p[0]\n    \n    def maximum(self):\n        while self.q2 and self.p2[0] == self.q2[0]:\n            heapq.heappop(self.p2)\n            heapq.heappop(self.q2)\n        return -self.p2[0]\n\n    def size(self):\n        return len(self.p)-len(self.q)\n\n\n\ns=[My_heapavi() for i in range(200005)]\nmaxs=My_heapavi()\n\n\ndef getmax(i):\n    if(s[i].size()==0):\n        return -1 \n    return s[i].maximum()\n\ndef addYouchien(i):\n    x=getmax(i)\n    if(x==-1):\n        return\n    maxs.insert(x)\n\ndef delYouchien(i):\n    x=getmax(i)\n    if(x==-1):\n        return\n    maxs.erase(x)\n\n \ndef addEnji(i,x):\n    delYouchien(i)\n    s[i].insert(x)\n    addYouchien(i)\n\n\ndef delEnji(i,x):\n    delYouchien(i)\n    s[i].erase(x)\n    addYouchien(i)\n\nN,Q=nm()\na=[0 for i in range(200005)]\nb=[0 for i in range(200005)]\n\nfor i in range(N):\n    a[i],b[i]=nm()\n    addEnji(b[i],a[i])\n\nfor i in range(Q):\n    c,d=nm()\n    c-=1\n    delEnji(b[c],a[c])\n    b[c]=d\n    addEnji(b[c],a[c])\n    print(maxs.minimum())", "import sys\n# import math\n# import bisect\n# import numpy as np\n# from decimal import Decimal\n# from numba import njit, i8, u1, b1 #JIT compiler\n# from itertools import combinations, product\n# from collections import Counter, deque, defaultdict\n\n# sys.setrecursionlimit(10 ** 6)\nMOD = 10 ** 9 + 7\nINF = 10 ** 9\nPI = 3.14159265358979323846\n\ndef read_str():      return sys.stdin.readline().strip()\ndef read_int():      return int(sys.stdin.readline().strip())\ndef read_ints():     return map(int, sys.stdin.readline().strip().split())\ndef read_ints2(x):   return map(lambda num: int(num) - x, sys.stdin.readline().strip().split())\ndef read_str_list(): return list(sys.stdin.readline().strip().split())\ndef read_int_list(): return list(map(int, sys.stdin.readline().strip().split()))\ndef GCD(a: int, b: int) -> int: return b if a%b==0 else GCD(b, a%b)\ndef LCM(a: int, b: int) -> int: return (a * b) // GCD(a, b)\n\nfrom heapq import heappop, heappush\ndef Main():\n    n, q = read_ints()\n    num = 2 * (10 ** 5)\n    kindergarten = [[] for _ in range(num)]\n    rating = [0] * n\n    now = [0] * n\n\n    for i in range(n):\n        a, b = read_ints()\n        heappush(kindergarten[~-b], (-a, i))\n        rating[i] = a\n        now[i] = ~-b\n\n    ranking = []\n    for j in range(num):\n        if kindergarten[j]:\n            a, i = kindergarten[j][0]\n            heappush(ranking, (-a, i))\n    \n    for _ in range(q):\n        c, d = read_ints()\n        last = now[~-c]\n        now[~-c] = ~-d\n        heappush(kindergarten[~-d], (-rating[~-c], ~-c))\n\n        while kindergarten[last] and now[kindergarten[last][0][1]] != last:\n            heappop(kindergarten[last])\n        while kindergarten[~-d] and now[kindergarten[~-d][0][1]] != ~-d:\n            heappop(kindergarten[~-d])\n\n        if kindergarten[last]:\n            a, i = kindergarten[last][0]\n            heappush(ranking, (-a, i))\n        if kindergarten[~-d]:\n            a, i = kindergarten[~-d][0]\n            heappush(ranking, (-a, i))\n\n        while ranking and kindergarten[now[ranking[0][1]]][0][1] != ranking[0][1]:\n            heappop(ranking)\n        \n        print(ranking[0][0])\n\ndef __starting_point():\n    Main()\n__starting_point()", "3\n# -*- coding:utf-8 -*-\n\nimport heapq\nfrom collections import defaultdict\n\ndef remove(hq, belongs, maxs, pd):\n  while hq:\n    if belongs[hq[0][1]] != pd:\n      heapq.heappop(hq)\n    else:\n      heapq.heappush(maxs, (-hq[0][0], hq[0][1], pd))\n      break\n\ndef main():\n  n, q = list(map(int, input().strip().split()))\n  rates = defaultdict(list)\n  id2rate = [0] * n\n  belongs = [0] * n\n  for i in range(n):\n    a, b = list(map(int, input().strip().split()))\n    b -= 1\n    rates[b].append((-a, i))\n    belongs[i] = b\n    id2rate[i] = a\n    \n  maxs = []\n  for k in list(rates.keys()):\n    heapq.heapify(rates[k])\n    maxs.append((-rates[k][0][0], rates[k][0][1], k))\n  heapq.heapify(maxs)\n\n  for _ in range(q):\n    c, d = list(map(int, input().strip().split()))\n    c -= 1\n    d -= 1\n\n    pd = belongs[c]\n    belongs[c] = d\n    remove(rates[pd], belongs, maxs, pd)\n        \n    heapq.heappush(rates[d], (-id2rate[c], c))    \n    remove(rates[d], belongs, maxs, d)\n    heapq.heappush(maxs, (-rates[d][0][0], rates[d][0][1], d))\n    \n    while maxs:\n      if belongs[maxs[0][1]] != maxs[0][2] or rates[maxs[0][2]][0][1] != maxs[0][1]:\n        heapq.heappop(maxs)\n      else:\n        print((maxs[0][0]))\n        break\n      \n\ndef __starting_point():\n  main()\n\n\n__starting_point()", "# coding: utf-8\nimport sys\nfrom heapq import heapify, heappop, heappush\nfrom collections import defaultdict\n\nsr = lambda: sys.stdin.readline().rstrip()\nir = lambda: int(sr())\nlr = lambda: list(map(int, sr().split()))\n\ndef main():\n    N, Q = lr()\n    top = []\n    left_top = []\n    infants = [[] for _ in range(2*10**5+1)]  # 1-indexed\n    left = [[] for _ in range(2*10**5+1)]\n    dic = defaultdict(tuple)\n    for i in range(1, N+1):\n        a, b = lr()\n        heappush(infants[b], (-a, i))\n        dic[i] = (a, b)\n\n    for i in range(1, 2*10**5+1):\n        if infants[i]:\n            rate, id = infants[i][0]\n            heappush(top, (-rate, id))\n\n    for _ in range(Q):\n        c, next = lr()\n        r, prev = dic[c]\n        dic[c] = (r, next)\n        r3, prev_top = infants[prev][0]\n        heappush(left_top, (-r3, prev_top))\n        heappush(left[prev], (-r, c))\n        while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:\n            heappop(infants[prev])\n            heappop(left[prev])\n        if infants[prev]:\n            rate, id = infants[prev][0]\n            heappush(top, (-rate, id))\n        if infants[next]:\n            heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # id\u3092push\n        heappush(infants[next], (-r, c))  # tuple\u3067push\n        while left[next] and infants[next][0][1] == left[next][0][1]:\n            heappop(infants[next])\n            heappop(left[next])\n        r2, id2 = infants[next][0]\n        heappush(top, (-r2, id2))\n        while left_top and top[0][1] == left_top[0][1]:\n            heappop(top); heappop(left_top)\n        answer = top[0][0]\n        print(answer)\n\nmain()", "import sys\nreadline = sys.stdin.readline\n\nimport heapq as hq\n\nN,Q = list(map(int,readline().split()))\nNN = 2 * (10 ** 5)\n\n# (\u30ec\u30fc\u30c8, \u6240\u5c5e\u5712)\ninfants = [None] * (N + 1)\n# (\u6700\u5f37\u5712\u5150, \u5712\u5150\u756a\u53f7)\nkinda = [[] for i in range(NN + 1)]\nfor i in range(N):\n  a,b = list(map(int,readline().split()))\n  infants[i + 1] = [a,b]\n  hq.heappush(kinda[b], (-a, i + 1))\n\n# (\u6700\u5f31\u5712\u5150, \u5712\u306e\u756a\u53f7)\nall_kinda = []\nfor i in range(len(kinda)):\n  if kinda[i]:\n    hq.heappush(all_kinda, (-kinda[i][0][0], i))\n  \ndef get_max_rate(x): # \u5712\u306e\u6700\u5f37\u30ec\u30fc\u30c8\u3092\u53d6\u308a\u51fa\u3059\n  q = kinda[x]\n  while q:\n    rate, ind = q[0]\n    if infants[ind][1] != x:\n      hq.heappop(q)\n      continue\n    return -rate\n  return -1\n  \nfor i in range(Q):\n  ind,next_kinda_id = list(map(int,readline().split()))\n  rate,old_kinda_id = infants[ind]\n  infants[ind][1] = next_kinda_id\n  hq.heappush(kinda[next_kinda_id],(-rate, ind))\n  \n  for target_kinda_id in (old_kinda_id,next_kinda_id):\n    target_kinda_max_rate = get_max_rate(target_kinda_id)\n    if target_kinda_max_rate != -1:\n      hq.heappush(all_kinda, (target_kinda_max_rate, target_kinda_id))\n\n  while all_kinda:\n    rate, kinda_id = all_kinda[0]\n    if rate != get_max_rate(kinda_id):\n      hq.heappop(all_kinda)\n      continue\n    print(rate)\n    break\n", "import sys\nfrom heapq import heappush, heappop\n\nread = sys.stdin.read\nreadline = sys.stdin.readline\nreadlines = sys.stdin.readlines\nsys.setrecursionlimit(10 ** 9)\nINF = 1 << 60\nMOD = 1000000007\n\n\ndef main():\n    N, Q = map(int, readline().split())\n    M = 2 * 10 ** 5\n    p = [[] for _ in range(M)]\n    p_del = [[] for _ in range(M)]\n    q = []\n    q_del = []\n\n    A = [0] * N\n    B = [0] * N\n    for i in range(N):\n        a, b = map(int, readline().split())\n        A[i] = a\n        B[i] = b - 1\n        heappush(p[b - 1], -a)\n\n    for i in range(M):\n        if p[i]:\n            heappush(q, -p[i][0])\n\n    CD = map(int, read().split())\n    ans = [0] * Q\n    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):\n        c -= 1\n        d -= 1\n\n        b, B[c] = B[c], d\n\n        max_prev = set()\n        max_prev.add(-p[b][0])\n        if p[d]:\n            max_prev.add(-p[d][0])\n\n        heappush(p_del[b], -A[c])\n        heappush(p[d], -A[c])\n\n        while p_del[b] and p[b][0] == p_del[b][0]:\n            heappop(p[b])\n            heappop(p_del[b])\n\n        max_current = set()\n        max_current.add(-p[d][0])\n        if p[b]:\n            max_current.add(-p[b][0])\n\n        for rating in max_prev - max_current:\n            heappush(q_del, rating)\n\n        for rating in max_current - max_prev:\n            heappush(q, rating)\n\n        while q_del and q[0] == q_del[0]:\n            heappop(q)\n            heappop(q_del)\n\n        ans[i] = q[0]\n\n    print(*ans, sep='\\n')\n\n    return\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import heappop, heappush\n\nMAX = 2*10**5\nn, q = list(map(int, input().split()))\nab = []\nk_in = [[] for _ in range(MAX)]\nk_out = [[] for _ in range(MAX)]\nfor i in range(n):\n    a, b = list(map(int, input().split()))\n    b -= 1\n    ab.append([a, b])\n    heappush(k_in[b], -a)\n\nk_max_in = []\nk_max_out = []\nfor i in range(MAX):\n    if k := k_in[i]:\n        heappush(k_max_in, -k[0])\n\nfor _ in range(q):\n    c, d = [int(x)-1 for x in input().split()]\n    idx = ab[c][1]\n    heappush(k_max_out, -k_in[idx][0])\n    if k_in[d]:\n        heappush(k_max_out, -k_in[d][0])\n    while k_max_out and k_max_in[0] == k_max_out[0]:\n        heappop(k_max_in)\n        heappop(k_max_out)\n    heappush(k_out[idx], -ab[c][0])\n    while k_out[idx] and k_in[idx][0] == k_out[idx][0]:\n        heappop(k_in[idx])\n        heappop(k_out[idx])\n\n    heappush(k_in[d], -ab[c][0])\n    if k_in[idx]:\n        heappush(k_max_in, -k_in[idx][0])\n    heappush(k_max_in, -k_in[d][0])\n    ab[c][1] = d\n\n    print((k_max_in[0]))\n", "import heapq\n\nN,Q = map(int,input().split())\nST = [0]*(N+1) #strong,belong\nkid_Add = [[] for _ in range(2*10**5+1)] #infant who is in this kinder at least one time\nkid_Del = [[] for _ in range(2*10**5+1)] #infant who is no longer in this kinder\nmax_Add = [] #highest rate\nmax_Del = [] #highest rate deleted\n\nheapq.heapify(kid_Add)\nheapq.heapify(kid_Del)\nheapq.heapify(max_Add)\nheapq.heapify(max_Del)\n\nfor i in range(N):\n    A,B = map(int,input().split())\n    heapq.heappush(kid_Add[B],-1*A)\n    ST[i+1] = (A,B)\n\nfor i in range(2*10**5+1):\n    if kid_Add[i]:heapq.heappush(max_Add,-1*kid_Add[i][0])\n\ndef deleteHeap(x,y):\n    while y and x[0] == y[0]:\n        heapq.heappop(x)\n        heapq.heappop(y)\n\nfor j in range(Q):\n    C,D = map(int,input().split())\n    s, t = ST[C]\n    if not kid_Add[D]:\n        Ne_S = 0\n    else:\n        Ne_S = kid_Add[D][0]\n    Ol_S = kid_Add[t][0]\n    heapq.heappush(kid_Add[D],-1*s)\n    heapq.heappush(kid_Del[t],-1*s)\n    deleteHeap(kid_Add[t],kid_Del[t])\n\n    if Ne_S > -1*s:\n        heapq.heappush(max_Add,s)\n        if Ne_S != 0 : heapq.heappush(max_Del,-1*Ne_S)\n    if Ol_S == -1*s:\n        heapq.heappush(max_Del,s)\n        if kid_Add[t]:heapq.heappush(max_Add,-1*kid_Add[t][0])\n        \n    deleteHeap(max_Add,max_Del)\n    print(max_Add[0])\n    ST[C] = (s,D)", "from collections import defaultdict\nimport heapq\nimport sys\ninput = sys.stdin.readline\n\nn, q = list(map(int, input().split()))\nab = [list(map(int, input().split())) for _ in range(n)]\ncd = [list(map(int, input().split())) for _ in range(q)]\n\nm = 2 * 10 ** 5\nthq = []\ntop = defaultdict(int)\ntopcnt = defaultdict(int)\nrhq = [[] for _ in range(m + 1)]\nrate = [defaultdict(int) for _ in range(m + 1)]\nfor a, b in ab:\n    top[b] = max(top[b], a)\n    rate[b][a] += 1\n    heapq.heappush(rhq[b], -a)\nfor num in list(top.values()):\n    heapq.heappush(thq, num)\n    topcnt[num] += 1\n\nfor c, d in cd:\n    a, b = ab[c - 1]\n    ab[c - 1][1] = d\n    rate[b][a] -= 1\n    if rate[b][a] == 0:\n        del rate[b][a]\n    topcnt[top[b]] -= 1\n    if topcnt[top[b]] == 0:\n        del topcnt[top[b]]\n    del top[b]\n    if len(rate[b]) > 0:\n        top[b] = -heapq.heappop(rhq[b])\n        while top[b] not in rate[b]:\n            top[b] = -heapq.heappop(rhq[b])\n        heapq.heappush(rhq[b], -top[b])\n        heapq.heappush(thq, top[b])\n        topcnt[top[b]] += 1\n\n    rate[d][a] += 1\n    heapq.heappush(rhq[d], -a)\n    if a > top[d]:\n        if top[d] > 0:\n            topcnt[top[d]] -= 1\n            if topcnt[top[d]] == 0:\n                del topcnt[top[d]]\n        top[d] = a\n        topcnt[top[d]] += 1\n    heapq.heappush(thq, top[d])\n\n    ans = heapq.heappop(thq)\n    while ans not in topcnt:\n        ans = heapq.heappop(thq)\n    heapq.heappush(thq, ans)\n    print(ans)\n", "# coding: utf-8\nimport sys\n# from operator import itemgetter\nsysread = sys.stdin.readline\nread = sys.stdin.read\nsys.setrecursionlimit(10 ** 7)\nfrom heapq import heappop, heappush\n#from collections import OrderedDict, defaultdict\n#import math\n#from itertools import product, accumulate, combinations, product\n#import bisect# lower_bound etc\n#import numpy as np\n# from copy import deepcopy\n#from collections import deque\n#import numba\n\ndef binary_search(arr, operator='max'):\n    _cri = {'max':max, 'min':min}\n    ope = _cri[operator]\n    dic = {0: arr}\n    dep = 0\n    while True:\n        _arr = dic[dep]\n        if len(_arr) == 1:break\n        dic[dep+1] = []\n        for i in range(0, len(_arr), 2):\n            if i == len(_arr) - 1:\n                dic[dep+1].append(_arr[i])\n                continue\n            dic[dep+1].append(ope(_arr[i], _arr[i+1]))\n        dep += 1\n    return _arr[0]\n\ndef eval_max(dic):\n    tmp = binary_search(list(dic.keys()))\n    return tmp\n\ndef run():\n    N, Q = list(map(int, input().split()))\n    rate = [0]\n    child = [0]\n    G = 2 * 10 ** 5\n    group = [[] for _ in range(G + 1)]\n    stocks = [[] for _ in range(G + 1)]\n    for i in range(1, N+1):\n        a, b = list(map(int, sysread().split()))\n        rate.append(a)\n        child.append(b)\n        heappush(group[b], -a)\n\n    max_vals = []\n    max_stocks = []\n    for i in range(1, G + 1):\n        if len(group[i]) > 0:\n            heappush(max_vals, -group[i][0])\n\n    for i in range(Q):\n        c,d = list(map(int, sysread().split()))\n        pre_g = child[c]\n        heappush(max_stocks, -group[pre_g][0])\n        heappush(stocks[pre_g], -rate[c])\n        while group[pre_g] and stocks[pre_g]:\n            if group[pre_g][0] == stocks[pre_g][0]:\n                heappop(stocks[pre_g])\n                heappop(group[pre_g])\n            else:\n                break\n        if group[pre_g]:\n            heappush(max_vals, -group[pre_g][0])\n\n        if group[d]:\n            heappush(max_stocks, -group[d][0])\n        heappush(group[d], -rate[c])\n        heappush(max_vals, -group[d][0])\n\n\n        while max_vals and max_stocks:\n            if max_vals[0] == max_stocks[0]:\n                heappop(max_vals)\n                heappop(max_stocks)\n            else:\n                break\n\n        child[c] = d\n\n        print((max_vals[0]))\n\n\n\ndef __starting_point():\n    run()\n\n\n__starting_point()", "import heapq\n\n\nclass DeletableHeap:\n  def __init__(self, reversed=False, debug=False):\n    self.heap = []\n    self.removed = {}\n    self.reversed = reversed  # get the max if True\n    self.factor = -1 if reversed else 1\n    self.debug = debug\n  \n  def push(self,x):\n#    if self.debug: print('push', x, self.heap, self.removed)\n    heapq.heappush(self.heap, x * self.factor)\n  \n  def pop(self):\n#    if self.debug: print('pop', self.heap, self.removed)\n    while self.heap:\n      a = heapq.heappop(self.heap) * self.factor\n      if a in self.removed and self.removed[a]:\n        self.removed[a] -= 1\n        if self.removed[a] == 0:\n          del self.removed[a]\n      else:\n #       if self.debug: print(a)\n        return a\n\n  def peek(self):\n #   if self.debug: print('peek', self.heap, self.removed)\n    while self.heap:\n      a = self.heap[0] * self.factor\n      if a in self.removed and self.removed[a]:\n        self.removed[a] -= 1\n        if self.removed[a] == 0:\n          del self.removed[a]\n        heapq.heappop(self.heap)\n      else:\n #       if self.debug: print(a)\n        return a\n\n  def remove(self,x):\n  #  if self.debug: print('remove', x, self.heap, self.removed)\n    if x not in self.removed:\n      self.removed[x] = 0\n    self.removed[x] += 1\n    \nN, Q = list(map(int, input().split()))\n\nKG = [DeletableHeap(reversed=True) for _ in range(2*10**5)]\nB = []\nA = []\nfor _ in range(N):\n  a, b = list(map(int, input().split()))\n  b -= 1\n  KG[b].push(a)\n  B.append(b)\n  A.append(a)\n\nrates = DeletableHeap(debug=False)\nfor kg in KG:\n  if kg.peek() is not None:\n    rates.push(kg.peek())\n#print(rates.heap, rates.removed)\n    \nfor _ in range(Q):\n#  print('######')\n  c, d = list(map(int, input().split()))\n  c -= 1\n  d -= 1\n  # c is at B[c]\n  b = B[c]\n  B[c] = d\n  a = A[c] # rate\n  # c moves from b to d\n  rates.remove(KG[b].peek())\n  KG[b].remove(a)\n  if KG[b].peek() is not None:\n    rates.push(KG[b].peek())\n  \n  if KG[d].peek() is not None:\n    rates.remove(KG[d].peek())\n  KG[d].push(a)\n  rates.push(KG[d].peek())\n  #print(rates.heap, rates.removed)\n  print((rates.peek()))\n  \n # for i in range(10):\n #   print('kg', i, KG[i].heap, KG[i].removed)\n\n\n", "import sys\nfrom heapq import heappush, heappop\n\nread = sys.stdin.read\nreadline = sys.stdin.readline\nreadlines = sys.stdin.readlines\nsys.setrecursionlimit(10 ** 9)\nINF = 1 << 60\nMOD = 1000000007\n\n\ndef main():\n    N, Q = map(int, readline().split())\n    M = 2 * 10 ** 5\n    hq1 = [[] for _ in range(M)]\n    hq2 = [[] for _ in range(M)]\n    hq_ans1 = []\n    hq_ans2 = []\n\n    A = [0] * N\n    B = [0] * N\n    for i in range(N):\n        a, b = map(int, readline().split())\n        A[i] = a\n        B[i] = b - 1\n        heappush(hq1[b - 1], -a)\n\n    for i in range(M):\n        if hq1[i]:\n            heappush(hq_ans1, -hq1[i][0])\n\n    CD = map(int, read().split())\n    ans = [0] * Q\n    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):\n        c -= 1\n        d -= 1\n\n        b = B[c]\n        B[c] = d\n\n        max_from_prev = -hq1[b][0]\n        if hq1[d]:\n            max_to_prev = -hq1[d][0]\n        else:\n            max_to_prev = None\n\n        heappush(hq2[b], -A[c])\n        heappush(hq1[d], -A[c])\n\n        while hq2[b] and hq1[b][0] == hq2[b][0]:\n            heappop(hq1[b])\n            heappop(hq2[b])\n\n        if hq1[b]:\n            max_from = -hq1[b][0]\n        else:\n            max_from = None\n        max_to = -hq1[d][0]\n\n        if max_from_prev != max_from:\n            heappush(hq_ans2, max_from_prev)\n            if max_from:\n                heappush(hq_ans1, max_from)\n\n        if max_to_prev != max_to:\n            if max_to_prev:\n                heappush(hq_ans2, max_to_prev)\n            heappush(hq_ans1, max_to)\n\n        while hq_ans2 and hq_ans1[0] == hq_ans2[0]:\n            heappop(hq_ans1)\n            heappop(hq_ans2)\n\n        ans[i] = hq_ans1[0]\n\n    print(*ans, sep='\\n')\n\n    return\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "# -*- coding: utf-8 -*-\nimport heapq\n\nN,Q = list(map(int, input().rstrip().split()))\nAB_list = [list(map(int, input().rstrip().split())) for i in range(N)]\nCD_list = [list(map(int, input().rstrip().split())) for i in range(Q)]\n#-----\n\nK = [ [] for _ in range(2*10**5) ]  # kindergarten\nK_deleted = [ [] for _ in range(2*10**5) ]\n\nmax_K = []\nmax_K_deleted = []\n\n\nfor a,b in AB_list:\n    heapq.heappush(K[b-1], -a)\n\nfor member in K:\n    if member:\n        heapq.heappush( max_K, -member[0] )\n\n\nfor c,d in CD_list:\n    c_rate = AB_list[c-1][0]\n    c_prev = AB_list[c-1][1]\n    \n    \n    departure_prev_max = K[c_prev-1][0]\n    \n    if K[d-1]:\n        destination_prev_max = K[d-1][0]\n    else:\n        destination_prev_max = None\n    \n    \n    # Delete c from current position\n    heapq.heappush( K_deleted[c_prev-1], -c_rate )\n    \n    # Add c to Destination(next position)\n    AB_list[c-1][1] = d\n    heapq.heappush(K[d-1], -c_rate)\n    \n    \n    # check HeapQueue of current and destination\n    for i in [c_prev, d]:\n        while K_deleted[i-1] and (K[i-1][0] == K_deleted[i-1][0]):\n            heapq.heappop(K[i-1])\n            heapq.heappop(K_deleted[i-1])\n    \n    \n    # check max-rank at departure.\n    if (not K[c_prev-1]):\n        heapq.heappush(max_K_deleted, -departure_prev_max)\n    \n    elif departure_prev_max != K[c_prev-1][0]:\n        heapq.heappush(max_K_deleted, -departure_prev_max)\n        heapq.heappush(max_K, -K[c_prev-1][0])\n    \n    \n    # check max-rank at destination.\n    if destination_prev_max != K[d-1][0]:\n        if destination_prev_max:\n            heapq.heappush(max_K_deleted, -destination_prev_max)\n        \n        heapq.heappush(max_K, -K[d-1][0])\n    \n    \n    # check min-value among kindergarten\n    while max_K_deleted and (max_K[0] == max_K_deleted[0]):\n        heapq.heappop(max_K)\n        heapq.heappop(max_K_deleted)\n    \n    \n    print((max_K[0]))\n", "import sys\nfrom heapq import heappush, heappop\n\nread = sys.stdin.read\nreadline = sys.stdin.readline\nreadlines = sys.stdin.readlines\nsys.setrecursionlimit(10 ** 9)\nINF = 1 << 60\nMOD = 1000000007\n\n\ndef main():\n    N, Q = map(int, readline().split())\n    M = 2 * 10 ** 5\n    hq1 = [[] for _ in range(M)]\n    hq2 = [[] for _ in range(M)]\n    hq_ans1 = []\n    hq_ans2 = []\n\n    A = [0] * N\n    B = [0] * N\n    for i in range(N):\n        a, b = map(int, readline().split())\n        A[i] = a\n        B[i] = b - 1\n        heappush(hq1[b - 1], -a)\n\n    for i in range(M):\n        if hq1[i]:\n            heappush(hq_ans1, -hq1[i][0])\n\n    CD = map(int, read().split())\n    ans = [0] * Q\n    for i, (c, d) in enumerate(zip(*[iter((CD))] * 2)):\n        c -= 1\n        d -= 1\n\n        b = B[c]\n        B[c] = d\n\n        max_from_prev = -hq1[b][0]\n        if hq1[d]:\n            max_to_prev = -hq1[d][0]\n        else:\n            max_to_prev = None\n\n        heappush(hq2[b], -A[c])\n        heappush(hq1[d], -A[c])\n\n        while hq2[b] and hq1[b][0] == hq2[b][0]:\n            heappop(hq1[b])\n            heappop(hq2[b])\n\n        if hq1[b]:\n            max_from = -hq1[b][0]\n        else:\n            max_from = None\n        max_to = -hq1[d][0]\n\n        if max_from_prev != max_from:\n            heappush(hq_ans2, max_from_prev)\n            if max_from:\n                heappush(hq_ans1, max_from)\n\n        if max_to_prev != max_to:\n            if max_to_prev:\n                heappush(hq_ans2, max_to_prev)\n            heappush(hq_ans1, max_to)\n\n        while hq_ans2 and hq_ans1[0] == hq_ans2[0]:\n            heappop(hq_ans1)\n            heappop(hq_ans2)\n\n        ans[i] = hq_ans1[0]\n\n    print(*ans, sep='\\n')\n\n    return\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "import sys\nimport heapq\n\nsys.setrecursionlimit(10 ** 8)\n\ninput = sys.stdin.readline\n\n\ndef main():\n    N, Q = [int(x) for x in input().split()]\n\n    hsize = 2 * 10 ** 5 + 1\n\n    h = [[] for _ in range(hsize)]\n\n    # \u5712\u5150\u304c\u73fe\u5728\u6240\u5c5e\u3057\u3066\u3044\u308b\u5e7c\u7a1a\u5712\u3092\u4fdd\u5b58\n    C = [0] * N\n    A = []\n    for i in range(N):\n        a, b = [int(x) for x in input().split()]\n        A.append(a)\n        heapq.heappush(h[b], (-a, i))\n        C[i] = b\n\n    A = tuple(A)\n    byodo = []\n\n    for i in range(1, hsize):\n        if len(h[i]) == 0:\n            continue\n        # \u5404\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u3092byodo\u306b\u5165\u308c\u308b\n        x = h[i][0]\n        heapq.heappush(byodo, (-x[0], x[1]))\n\n    ans = []\n    for _ in range(Q):\n        c, d = [int(x) for x in input().split()]\n        c -= 1\n\n        # \u79fb\u52d5\u5143\u6700\u5927\u5024\u30c1\u30a7\u30c3\u30af\n        cfrom = C[c]\n        # c\u5712\u5150\u306e\u73fe\u5728\u6642\u3092d\u306b\u66f4\u65b0\n        C[c] = d\n        while h[cfrom]:\n            x = h[cfrom][0]\n            # \u6700\u5927\u5024\u306e\u5712\u5150\u306e\u73fe\u5728\u306e\u6240\u5c5e\u5e7c\u7a1a\u5712\u304cC[c]\u3068\u7570\u306a\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            if C[x[1]] != cfrom:\n                heapq.heappop(h[cfrom])\n                continue\n\n            # \u73fe\u5728\u306e\u6700\u5927\u5024\u3092\u5e73\u7b49\u306bpush\n            heapq.heappush(byodo, (-x[0], x[1]))\n            break\n\n        # c\u5712\u5150\u3092d\u5e7c\u7a1a\u5712\u306bpush\n        heapq.heappush(h[d], (-A[c], c))\n\n        # \u79fb\u52d5\u5148\u6700\u5927\u5024\u30c1\u30a7\u30c3\u30af\n        while h[d]:\n            x = h[d][0]\n            # \u6700\u5927\u5024\u306e\u5712\u5150\u306e\u73fe\u5728\u306e\u6240\u5c5e\u5e7c\u7a1a\u5712\u304cd\u3068\u7570\u306a\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            if C[x[1]] != d:\n                heapq.heappop(h[d])\n                continue\n\n            # \u73fe\u5728\u306e\u6700\u5927\u5024\u3092byodo\u306bpush\n            heapq.heappush(byodo, (-x[0], x[1]))\n            break\n\n        # \u5e73\u7b49\u306e\u6700\u5c11\u5024\u3092\u53d6\u5f97\n        while byodo:\n            x = byodo[0]\n\n            # \u6700\u5c0f\u5024\u304c\u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u306e\u6700\u5927\u5024\u304c\u7570\u306a\u3063\u3066\u3044\u308c\u3070pop\u3057\u305f\u307e\u307e\u306b\u3059\u308b\n            y = h[C[x[1]]][0]\n            if -y[0] != x[0]:\n                heapq.heappop(byodo)\n                continue\n\n            ans.append(x[0])\n            break\n\n    print(('\\n'.join(map(str, ans))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "from heapq import heappop, heappush\nfrom typing import Optional\n\n\nclass DeletableHeapq:\n    \"\"\"Deletable Heapq: A heapq supporting lazy deletion of values.\"\"\"\n\n    def __init__(self, *initial_values: int, is_max_heap: bool = False) -> None:\n        self.is_max_heap = is_max_heap\n        self.size = 0\n        self._set = set()\n        self._heap = []\n\n        if initial_values:\n            for v in initial_values:\n                self.push(v)\n\n    @property\n    def top(self) -> Optional[int]:\n        \"\"\"Return the minimum value if is_max_heap is False;\n        otherwise, return the maximum value from the heap.\n        If the heap is empty, None is returned.\n        \"\"\"\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        return self._heap[0] if not self.is_max_heap else -self._heap[0]\n\n    def pop(self) -> Optional[int]:\n        \"\"\"Pop and return the minimum value if is_max_heap is False;\n        otherwise, return the maximum value from the heap.\n        If the heap is empty, None is returned.\n        \"\"\"\n        while self._heap and self._heap[0] not in self._set:\n            heappop(self._heap)\n        if not self._heap:\n            return None\n        self.size -= 1\n        res = heappop(self._heap)\n        self._set.discard(res)\n        return res if not self.is_max_heap else -res\n\n    def push(self, value: int) -> None:\n        \"\"\"Push value into the heap.\"\"\"\n        if self.is_max_heap:\n            value = -value\n        if value in self._set:\n            return\n        self.size += 1\n        heappush(self._heap, value)\n        self._set.add(value)\n\n    def delete(self, value: int) -> None:\n        \"\"\"Delete value from the heap.\"\"\"\n        if self.is_max_heap:\n            value = -value\n        if value not in self._set:\n            return\n        self.size -= 1\n        self._set.discard(value)\n\n\ndef main():\n    # https://atcoder.jp/contests/abc170/tasks/abc170_e\n    N, _, *X = list(map(int, open(0).read().split()))\n    AB, CD = X[: 2 * N], X[2 * N :]\n    rate, belonging = [0] * (N + 1), [0] * (N + 1)\n    kindy = [DeletableHeapq(is_max_heap=True) for _ in range(200_001)]\n\n    for i, (a, b) in enumerate(zip(*[iter(AB)] * 2), 1):\n        rate[i], belonging[i] = (a << 18) + i, b\n        kindy[b].push(rate[i])\n\n    smart_infants = DeletableHeapq(*(k.top for k in kindy if k.size))\n    res = []\n    for c, next_k in zip(*[iter(CD)] * 2):\n        prev_k = belonging[c]\n        belonging[c] = next_k\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.delete(kindy[k].top)\n\n        kindy[prev_k].delete(rate[c])\n        kindy[next_k].push(rate[c])\n\n        for k in (prev_k, next_k):\n            if kindy[k].size:\n                smart_infants.push(kindy[k].top)\n\n        res.append(smart_infants.top >> 18)\n\n    print((\"\\n\".join(map(str, res))))\n\n\ndef __starting_point():\n    main()\n\n__starting_point()", "# coding: utf-8\nimport sys\nfrom heapq import heapify, heappop, heappush\nfrom collections import defaultdict\n\nsr = lambda: sys.stdin.readline().rstrip()\nir = lambda: int(sr())\nlr = lambda: list(map(int, sr().split()))\n\nN, Q = lr()\ntop = []\nleft_top = []\ninfants = [[] for _ in range(2*10**5+1)]  # 1-indexed\nleft = [[] for _ in range(2*10**5+1)]\ndic = defaultdict(list)\nfor i in range(1, N+1):\n    a, b = lr()\n    heappush(infants[b], (-a, i))\n    dic[i] = (a, b)\n\nfor i in range(1, 2*10**5+1):\n    if infants[i]:\n        rate, id = infants[i][0]\n        heappush(top, (-rate, id))\n\nfor _ in range(Q):\n    c, next = lr()\n    r, prev = dic[c]\n    dic[c] = (r, next)\n    r3, prev_top = infants[prev][0]\n    heappush(left_top, (-r3, prev_top))\n    heappush(left[prev], (-r, c))\n    while infants[prev] and left[prev] and infants[prev][0][1] == left[prev][0][1]:\n        heappop(infants[prev])\n        heappop(left[prev])\n    if infants[prev]:\n        rate, id = infants[prev][0]\n        heappush(top, (-rate, id))\n    if infants[next]:\n        heappush(left_top, (-infants[next][0][0], infants[next][0][1]))  # id\u3092push\n    heappush(infants[next], (-r, c))  # tuple\u3067push\n    while left[next] and infants[next][0][1] == left[next][0][1]:\n        heappop(infants[next])\n        heappop(left[next])\n    r2, id2 = infants[next][0]\n    heappush(top, (-r2, id2))\n    while left_top and top[0][1] == left_top[0][1]:\n        heappop(top); heappop(left_top)\n    answer = top[0][0]\n    print(answer)\n", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t,_ in x:t and f(l,-t[0])\nfor c,d in z[n:]:\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)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y[0]<t:f(l,a);t<0and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "import sys\ndef input():return sys.stdin.readline().strip()\nfrom collections import defaultdict\nfrom heapq import heappop, heappush, heapify\n\ndef main():\n    N, Q = map(int, input().split())\n    infant_info = [tuple(map(int, input().split())) for _ in range(N)]\n    queries = [tuple(map(int, input().split())) for _ in range(Q)]\n    \n    num_kd = 2 * 10 ** 5\n    nums = [0] * num_kd\n    h = [[] for _ in range(num_kd)]\n    pos = [-1] * N\n    kd_max = defaultdict(int)\n    min_max_timestamp = [0] * num_kd\n\n    # init\n    for i, (a, b) in enumerate(infant_info):\n        b -= 1\n\n        heappush(h[b], (-a, i))\n        pos[i] = b\n        nums[b] += 1\n\n        kd_max[b] = max(kd_max[b], a)\n    \n    # rate, id, timestamp\n    min_max_h = [(val, kd, 0) for kd, val in kd_max.items()]\n\n    heapify(min_max_h)\n\n    # query\n    for t, (c, to_kd) in enumerate(queries, 1):\n        c -= 1\n        to_kd -= 1\n\n        from_kd = pos[c]\n        pos[c] = to_kd\n\n        # from\n        nums[from_kd] -= 1\n        if nums[from_kd] > 0:\n            while True:\n                rate, infant = heappop(h[from_kd])\n                if pos[infant] == from_kd:\n                    heappush(h[from_kd], (rate, infant))\n                    heappush(min_max_h, (-rate, from_kd, t))\n                    break\n        \n        min_max_timestamp[from_kd] = t\n\n        \n        # to\n        nums[to_kd] += 1\n\n        rate_c, _ = infant_info[c]\n        heappush(h[to_kd], (-rate_c, c))\n\n        while True:\n            rate, infant = heappop(h[to_kd])\n            if pos[infant] == to_kd:\n                heappush(h[to_kd], (rate, infant))\n                heappush(min_max_h, (-rate, to_kd, t))\n                break\n        \n        min_max_timestamp[to_kd] = t\n\n\n\n        # equality\n        # print(\"pos\", pos)\n        while True:\n            rate, kd, ts = heappop(min_max_h) \n            if min_max_timestamp[kd] == ts:\n                print(rate)\n                heappush(min_max_h, (rate, kd, ts))\n                break\n    \ndef __starting_point():\n    main()\n__starting_point()", "from heapq import *\nimport sys\ninput = sys.stdin.readline\n\ndef main():\n    n, q = list(map(int, input().split()))\n    children = [[int(x) for x in input().split()] for _ in range(n)]\n    \n    m = int(2*1e5)\n    heap_each = [[] for _ in range(m)]\n    each_moved = [dict() for _ in range(m)]\n    heap_all = []\n    all_moved = dict()\n    for i in range(n):\n        a, b = children[i]\n        heappush(heap_each[b-1], -a)\n    for i in range(m):\n        if heap_each[i]:\n            heappush(heap_all, -heap_each[i][0])\n    \n    ans = []\n    for i in range(q):\n        c, d = list(map(int, input().split()))#\u5e7c\u5150C\u304c\u5e7c\u7a1a\u5712D\u306b\u79fb\u52d5\n        a, b = children[c-1]#\u5e7c\u5150\u306e\u30ec\u30fc\u30c8\uff1aA\u3001\u5143\u306e\u5e7c\u7a1a\u5712\uff1aB\n        if a == -heap_each[b-1][0]:#\u5e7c\u5150\u304c\u305d\u306e\u5712\u306e\u30c8\u30c3\u30d7\u3060\u3063\u305f\u3068\u304d\n            if a in all_moved:#\u5168\u4f53\u30ea\u30b9\u30c8\u304b\u3089\u524a\u9664\n                all_moved[a] += 1\n            else:\n                all_moved[a] = 1\n            heappop(heap_each[b-1])#\u305d\u306e\u5e7c\u7a1a\u5712\u306e\u30ea\u30b9\u30c8\u304b\u3089\u524a\u9664\n            while heap_each[b-1]:#\u5024\u304c\u524a\u9664\u6e08\u307f\u306e\u5712\u5150\u304b\u3069\u3046\u304b\u5224\u5b9a:\u305d\u3046\u3067\u306a\u3044\u306a\u3089\u5168\u4f53\u30ea\u30b9\u30c8\u306b\u5024\u3092\u8ffd\u52a0\n                if heap_each[b-1][0] in each_moved[b-1] and each_moved[b-1][heap_each[b-1][0]] > 0:\n                    each_moved[b-1][heap_each[b-1][0]] -= 1\n                    heappop(heap_each[b-1])\n                    continue\n                heappush(heap_all, -heap_each[b-1][0])\n                break\n        else:#\u5e7c\u5150\u304c\u305d\u306e\u5712\u306e\u30c8\u30c3\u30d7\u3067\u306a\u3044\u3068\u304d\u306f\u3001\u524a\u9664\u30ea\u30b9\u30c8\u306b\u8ffd\u52a0\u3059\u308b\u306e\u307f\n            if -a in each_moved[b-1]:\n                each_moved[b-1][-a] += 1\n            else:\n                each_moved[b-1][-a] = 1\n        #\u8ee2\u5712\u5148\u3067\u306e\u8a71\n        if not heap_each[d-1]:#\u65b0\u3057\u3044\u5712\u304c\u3072\u3068\u308a\u307c\u3063\u3061\u306a\u3089\n            heappush(heap_each[d-1], -a)\n            heappush(heap_all, a)\n        elif -a < heap_each[d-1][0]:#\u65b0\u3057\u3044\u5712\u3067\u30c8\u30c3\u30d7\u306a\u3089\n            if -heap_each[d-1][0] in all_moved:#\u65e7\u4e00\u4f4d\u3092\u5168\u4f53\u30ea\u30b9\u30c8\u304b\u3089\u524a\u9664\n                all_moved[-heap_each[d-1][0]] += 1\n            else:\n                all_moved[-heap_each[d-1][0]] = 1\n            heappush(heap_each[d-1], -a)\n            heappush(heap_all, a)\n        else:#\u65b0\u3057\u3044\u5712\u3067\u305f\u3060\u306e\u4eba\u306a\u3089\n            heappush(heap_each[d-1], -a)\n        while heap_all:\n            if heap_all[0] in all_moved and all_moved[heap_all[0]] > 0:\n                all_moved[heap_all[0]] -= 1\n                heappop(heap_all)\n                continue\n            break\n        children[c-1][1] = d\n        ans.append(heap_all[0])\n    \n    \n    for answer in ans:\n        print(answer)\n\n            \ndef __starting_point():\n    main()        \n\n__starting_point()", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t in x:t[0]and f(l,-t[0][0])\nfor c,d in z[n:]:\n a,b=z[c-1];z[c-1][1]=d;v,w=x[b];y,_=x[d];t=0;f(w,-a)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y:t=y[0]\n f(y,-a)\n if y[0]!=t:f(l,a);t<0and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "import sys\nfrom heapq import heappop, heappush, heapify\n\nsys.setrecursionlimit(10 ** 7)\ninput = sys.stdin.readline\nf_inf = float('inf')\nmod = 10 ** 9 + 7\nMAX = 2 * 10 ** 5 + 1\n\n\ndef resolve():\n    def max_rate_in_cls(c):\n        q = class_rate[c]\n        while q:\n            x, enj = q[0]\n            if enji_cls[enj] == c:\n                return -x\n            else:\n                heappop(q)\n        return 0\n\n    def get_ans():\n        q = max_rate\n        while True:\n            x, c = q[0]\n            if max_rate_in_cls(c) == x:\n                return x\n            heappop(q)\n\n    def max_rate_in_cls(c):\n        q = class_rate[c]\n        while q:\n            x, enj = q[0]\n            if enji_cls[enj] == c:\n                return -x\n            else:\n                heappop(q)\n        return 0\n\n    n, q = list(map(int, input().split()))\n\n    enji_rate = [0] * (n + 1)\n    enji_cls = [0] * (n + 1)\n    class_rate = [[] for _ in range(MAX)]\n    for i in range(1, n + 1):\n        rate, cls = list(map(int, input().split()))\n        enji_rate[i] = rate\n        enji_cls[i] = cls\n        heappush(class_rate[cls], (-rate, i))\n\n    max_rate = []\n    for c in range(MAX):\n        x = max_rate_in_cls(c)\n        if x:\n            max_rate.append((x, c))\n    heapify(max_rate)\n\n    for _ in range(q):\n        enj, after_cls = list(map(int, input().split()))\n        before_cls = enji_cls[enj]\n        heappush(class_rate[after_cls], (-enji_rate[enj], enj))\n        enji_cls[enj] = after_cls\n        for c in (before_cls, after_cls):\n            x = max_rate_in_cls(c)\n            if x != 0:\n                heappush(max_rate, (x, c))\n        print((get_ans()))\n\n\ndef __starting_point():\n    resolve()\n\n__starting_point()", "from collections import defaultdict\nimport heapq\nimport sys\ninput = sys.stdin.readline\n\nn, q = list(map(int, input().split()))\nab = [list(map(int, input().split())) for _ in range(n)]\ncd = [list(map(int, input().split())) for _ in range(q)]\n\nthq = []\ntop = defaultdict(int)\ntopcnt = defaultdict(int)\nrhq = [[] for _ in range(2 * 10 ** 5 + 1)]\nrate = [defaultdict(int) for _ in range(2 * 10 ** 5 + 1)]\nfor a, b in ab:\n    top[b] = max(top[b], a)\n    rate[b][a] += 1\n    heapq.heappush(rhq[b], -a)\nfor num in list(top.values()):\n    heapq.heappush(thq, num)\n    topcnt[num] += 1\n\nfor c, d in cd:\n    a, b = ab[c - 1]\n    ab[c - 1][1] = d\n\n    # \u5143\u306e\u5712\u306b\u3064\u3044\u3066\n    rate[b][a] -= 1\n    if rate[b][a] == 0:\n        del rate[b][a]\n    topcnt[top[b]] -= 1\n    if topcnt[top[b]] == 0:\n        del topcnt[top[b]]\n    del top[b]\n    if len(rate[b]) > 0:\n        top[b] = -heapq.heappop(rhq[b])\n        while top[b] not in rate[b]:\n            top[b] = -heapq.heappop(rhq[b])\n        heapq.heappush(rhq[b], -top[b])\n        heapq.heappush(thq, top[b])\n        topcnt[top[b]] += 1\n\n    # \u65b0\u3057\u3044\u5712\u306b\u3064\u3044\u3066\n    rate[d][a] += 1\n    heapq.heappush(rhq[d], -a)\n    if a > top[d]:\n        if top[d] > 0:\n            topcnt[top[d]] -= 1\n            if topcnt[top[d]] == 0:\n                del topcnt[top[d]]\n        top[d] = a\n        topcnt[top[d]] += 1\n        heapq.heappush(thq, top[d])\n\n    # \u6700\u5c0f\u5024\u306b\u3064\u3044\u3066\n    ans = heapq.heappop(thq)\n    while ans not in topcnt:\n        ans = heapq.heappop(thq)\n    heapq.heappush(thq, ans)\n    print(ans)\n", "import heapq\nimport sys\ndef input(): return sys.stdin.readline().rstrip()\n\n\ndef main():\n    n, q = map(int, input().split())\n    syozoku = [0]*(n+1)\n    rate = [0]*(n+1)\n    enrate = [0]*(2*10**5+1)\n    saikyourate = HeapDict()\n    for i in range(1, 2*10**5+1):\n        enrate[i] = HeapDict()\n    for i in range(1, n+1):\n        a, b = map(int, input().split())\n        syozoku[i] = b\n        rate[i] = a\n        enrate[b].insert(-a)\n    for i in range(1, 2*10**5+1):\n        if len(enrate[i].h) != 0:\n            saikyourate.insert(-(enrate[i].get_min()))\n    for _ in range(q):\n        c,d=map(int, input().split()) #\u79fb\u52d5 syozoku[c]\u2192d\n        saikyourate.erase(-(enrate[syozoku[c]].get_min()))\n        enrate[syozoku[c]].erase(-rate[c])\n        if len(enrate[syozoku[c]].h) != 0:\n            saikyourate.insert(-(enrate[syozoku[c]].get_min()))\n        if len(enrate[d].h) != 0:\n            saikyourate.erase(-(enrate[d].get_min()))\n        enrate[d].insert(-rate[c])\n        saikyourate.insert(-(enrate[d].get_min()))\n        syozoku[c]=d\n        print(saikyourate.get_min())\n\n\n        \n\n\nclass HeapDict:  # \u5b9f\u88c5https://tsubo.hatenablog.jp/entry/2020/06/15/124657\n    def __init__(self):\n        self.h = []\n        self.d = dict()\n\n    def insert(self, x):\n        heapq.heappush(self.h, x)\n        if x not in self.d:\n            self.d[x] = 1\n        else:\n            self.d[x] += 1\n\n    def erase(self, x):\n        if x not in self.d or self.d[x] == 0:\n            print(x, \"is not in HeapDict\")\n            return\n        else:\n            self.d[x] -= 1\n\n        while len(self.h) != 0:\n            if self.d[self.h[0]] == 0:\n                heapq.heappop(self.h)\n            else:\n                break\n\n    def is_exist(self, x):\n        if x in self.d and self.d[x] != 0:\n            return True\n        else:\n            return False\n\n    def get_min(self):\n        return self.h[0]\n\n\ndef __starting_point():\n    main()\n__starting_point()", "import heapq\n\nclass BalancingTree:\n    def __init__(self):\n        self.p = []\n        self.q = []\n\n    def insert(self, x):\n        heapq.heappush(self.p, x)\n\n    def erase(self, x):\n        heapq.heappush(self.q, x)\n\n    def minimum(self):\n        while self.q and self.p[0] == self.q[0]:\n            heapq.heappop(self.p)\n            heapq.heappop(self.q)\n        return self.p[0] if self.p else None\n\n\nMAX = 2*10**5\nn, q = list(map(int, input().split()))\nab = []\nk = [BalancingTree() for _ in range(MAX)]\nfor i in range(n):\n    a, b = list(map(int, input().split()))\n    b -= 1\n    ab.append([a, b])\n    k[b].insert(-a)\n\nk_max = BalancingTree()\nfor i in range(MAX):\n    if v := k[i].minimum():\n        k_max.insert(-v)\n\nfor _ in range(q):\n    c, d = [int(x)-1 for x in input().split()]\n    a, b = ab[c]\n    k_max.erase(-k[b].minimum())\n    if v := k[d].minimum():\n        k_max.erase(-v)\n    k[b].erase(-a)\n\n    k[d].insert(-a)\n    if v := k[b].minimum():\n        k_max.insert(-v)\n    k_max.insert(-k[d].minimum())\n    ab[c][1] = d\n\n    print((k_max.minimum()))\n", "import heapq\n\nN, Q = map(int, input().split())\n\nM = 2 * 10**5\n\nrate_list = []\nrates = [[] for _ in range(M)]\nmembers = [set() for _ in range(M)]\nbelongs = [-1] * N\n\nfor i in range(N):\n    A, B = map(int, input().split())\n    B = B - 1\n    heapq.heappush(rates[B], (-A, i))\n    members[B].add(i)\n    belongs[i] = B\n    rate_list.append(A)\n\nmax_rates = []\nfor num, rate in enumerate(rates):\n    if len(rate) > 0:\n        heapq.heappush(max_rates, (-rate[0][0], num))\n\nfor i in range(Q):\n    C, D = map(int, input().split())\n    C = C - 1\n    D = D - 1\n    old = belongs[C]\n    belongs[C] = D\n    members[old].remove(C)\n    members[D].add(C)\n    while len(rates[old]) > 0 and rates[old][0][1] not in members[old]:\n        heapq.heappop(rates[old])\n    \n    if len(rates[old]) > 0:\n        heapq.heappush(max_rates, (-rates[old][0][0], old))\n        \n    heapq.heappush(rates[D], (-rate_list[C], C))\n    heapq.heappush(max_rates, (rate_list[C], D))\n\n    while max_rates:\n        rate, num = max_rates[0]\n        if len(rates[num])==0 or - rates[num][0][0] != rate:\n            heapq.heappop(max_rates)\n        else:\n            print(rate)\n            break", "from heapq import heappop, heappush\n# \u30d7\u30e9\u30a4\u30aa\u30ea\u30c6\u30a3\u30ad\u30e5\u30fc\n# \u8981\u7d20\u306e\u633f\u5165\u3001\u6700\u5c0f\u5024\uff08\u6700\u5927\u5024\uff09\u306e\u53d6\u308a\u51fa\u3057\u304c\u901f\u3044\n# \u5712\u5150\u306e\u8ee2\u5712\u306b\u3088\u308b\u524a\u9664\u304c\u30dc\u30c8\u30eb\u30cd\u30c3\u30af\n# \u524a\u9664\u3057\u306a\u3051\u308c\u3070\u826f\u3044\u3068\u8003\u3048\u308b\uff08\u52ff\u8ad6\u30c1\u30a7\u30c3\u30af\u306f\u5fc5\u8981\uff09\n\nN, Q = list(map(int, input().split()))\n\n# \u5e7c\u7a1a\u5712\u306e\u6570\nM = 2 * (10 ** 5)\n# \u5e7c\u5150i\u306e\u6240\u5c5e\u5148\u306e\u5e7c\u7a1a\u5712\nbelong = [None] * N\n# \u5e7c\u5150i\u306e\u30ec\u30fc\u30c8\nrate = [None] * N\n# \u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3002(\u30de\u30a4\u30ca\u30b9\u30ec\u30fc\u30c8, \u5e7c\u5150\u756a\u53f7)\n# KinDerGarTen\nkdgt = [[] for _ in range(M)]\n\nfor c in range(N):\n    A, B = list(map(int, input().split()))\n    # \u5e7c\u7a1a\u5712\u756a\u53f7\u30920-index\u306b\u3059\u308b\n    B -= 1\n    # \u6240\u5c5e\n    belong[c] = B\n    # \u30ec\u30fc\u30c8\n    rate[c] = A\n    # \u5e7c\u7a1a\u5712\u306e\u7bb1\u306b\u5bfe\u3057\u3066\u3001(\u30de\u30a4\u30ca\u30b9\u30ec\u30fc\u30c8\u3001\u5e7c\u5150\u756a\u53f7)\n    heappush(kdgt[B], (-A, c))\n\n# \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3002(\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8, \u5e7c\u5150\u756a\u53f7, \u5712\u756a\u53f7)\nq = []\n\n# \u5404\u5e7c\u7a1a\u5712\u306b\u3064\u3044\u3066\nfor i in range(M):\n    # \u4e00\u4eba\u3082\u6240\u5c5e\u3057\u3066\u3044\u306a\u3051\u308c\u3070\u30d1\u30b9\n    if kdgt[i]:\n        # \u30de\u30a4\u30ca\u30b9\u304c\u304b\u304b\u3063\u3066\u3044\u308b\u306e\u3067\u6700\u5927\u5024\u304c\u53d6\u308a\u51fa\u305b\u308b\n        A, c = kdgt[i][0]\n        # (\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8\u3001\u5e7c\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7)\n        heappush(q, (-A, c, i))\n\nfor _ in range(Q):\n    C, D = list(map(int, input().split()))\n    # \u5e7c\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7\u30920-index\u306b\n    C -= 1\n    D -= 1\n    # \u79fb\u52d5\u5143\u306e\u5e7c\u7a1a\u5712\n    pd = belong[C]\n    # \u5e7c\u5150\u306ebelong\u3092\u66f4\u65b0\n    belong[C] = D\n\n    # \u79fb\u52d5\u5143\u306e\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3092\u66f4\u65b0\n    while kdgt[pd]:\n        # \u305d\u306e\u5712\u3067\u306e\u6700\u5f37\u5712\u5150\uff08\u4eee\uff09\n        A, c = kdgt[pd][0]\n        # \u65e2\u306b\u5b58\u5728\u3057\u306a\u3044\u3068\u304d\u3001\u53d6\u308a\u9664\u304f\n        # \u5b58\u5728\u3059\u308b\u3068\u304d, \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3078\u8ffd\u52a0\n        if belong[c] != pd:\n            heappop(kdgt[pd])\n        else:\n            heappush(q, (-A, c, pd))\n            break\n\n    # \u79fb\u52d5\u5148\u306e\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3092\u66f4\u65b0\n    # \u5bfe\u8c61\u306e\u5e7c\u5150\u3092\u8ffd\u52a0\n    heappush(kdgt[D], (-rate[C], C))\n    while kdgt[D]:\n        # \u305d\u306e\u5712\u3067\u306e\u6700\u5f37\u5712\u5150\uff08\u4eee\uff09\n        A, c = kdgt[D][0]\n        # \u65e2\u306b\u5b58\u5728\u3057\u306a\u3044\u3068\u304d\u53d6\u308a\u9664\u304f\n        # \u5b58\u5728\u3059\u308b\u3068\u304d, \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3078\u8ffd\u52a0\n        if belong[c] != D:\n            heappop(kdgt[D])\n        else:\n            heappush(q, (-A, c, D))\n            break\n\n    while q:\n        # \u6700\u5f37\u306e\u4e2d\u306e\u6700\u5f31\uff08\u4eee\uff09\n        # (\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8\u3001\u5712\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7)\n        A, c, d = q[0]\n        # \u30ad\u30e5\u30fc\u306e\u5148\u982d\u306e\u5e7c\u5150\u304c\u65e2\u306b\u53bb\u3063\u3066\u3044\u308b or \u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u306e\u5148\u982d\u3067\u306f\u7121\u3044\u6642\u53d6\u308a\u9664\u304f\n        # \u305d\u3046\u3067\u306f\u306a\u3044\u3068\u304d\u3001\u3053\u308c\u304c\u7b54\u3048\n        # if belong[c] != d or kdgt[d][0][1] != c:\n        if belong[c] != d or kdgt[d][0][1] != c:\n            heappop(q)\n        else:\n            print(A)\n            break\n", "from heapq import heappush, heappop\n\nn, q = map(int, input().split())\nrate = [0]*n\nbelong = [-1]*n\nyochien_rates = [[] for i in range(2 * 10 ** 5 + 10)]\ndelete_yochien_rates = [[] for i in range(2 * 10 ** 5 + 10)]\nyochiens = set()\nfor i in range(n):\n    a, b = map(int, input().split())\n    b -= 1\n    rate[i] = a\n    belong[i] = b\n    yochiens.add(b)\n    heappush(yochien_rates[b], -a)\n\nmaxs = []\ndelete_maxs = []\n\nfor i in yochiens:\n    heappush(maxs, -yochien_rates[i][0])\nans = []\nfor _ in range(q):\n    c, d = map(int, input().split())\n    c -= 1\n    d -= 1\n\n    old = belong[c]\n    belong[c] = d\n\n    # \u5143\u3044\u305f\u5e7c\u7a1a\u5712\u3068\u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306e\u6700\u5f37\u5712\u5150\u3092\u524a\u9664\u30ad\u30e5\u30fc\u306b\u5165\u308c\u308b\n    heappush(delete_maxs, -yochien_rates[old][0])\n    if yochien_rates[d]:\n        heappush(delete_maxs, -yochien_rates[d][0])\n\n    # \u65b0\u3057\u3044\u5e7c\u7a1a\u5712\u306erates\u3068\u5168\u4f53\u306erates\u306e\u66f4\u65b0\n    heappush(yochien_rates[d], -rate[c])\n    heappush(maxs, -yochien_rates[d][0])\n\n    # old\u306e\u66f4\u65b0\n    heappush(delete_yochien_rates[old], -rate[c])\n    while delete_yochien_rates[old] and yochien_rates[old][0] == delete_yochien_rates[old][0]:\n        heappop(yochien_rates[old])\n        heappop(delete_yochien_rates[old])\n    if yochien_rates[old]:\n        heappush(maxs, -yochien_rates[old][0])\n\n    # \u6700\u5c0f\u5024\u8a08\u7b97\n    while delete_maxs and maxs[0] == delete_maxs[0]:\n        heappop(maxs)\n        heappop(delete_maxs)\n    ans.append(maxs[0])\n\nprint(*ans, sep='\\n')\n\n", "import heapq\n\nymax = 200000\nN, Q  = list(map(int, input().split()))\n\nyo = [[] for i in range(ymax+1)]\nym = []\nAB = [(0,0)]\ns = set()\n\nfor i in range(N):\n  A, B  = list(map(int, input().split()))\n  AB.append( (A, B) )\n  heapq.heappush(yo[B],(-A,i+1))\n  s.add(B)\n#\nfor i in s:\n  mA, c = yo[i][0]\n  heapq.heappush(ym,(-mA,c,i)) \n#\nfor i in range(Q):\n  C, D  = list(map(int, input().split()))\n  A, B = AB[C]\n  AB[C] = (A, D)\n\n  if  yo[B][0][1] == C:\n    while (yo[B]) and (AB[ yo[B][0][1] ][1] != B):\n      heapq.heappop(yo[B])\n    if yo[B]:\n      mA, c = yo[B][0]\n      heapq.heappush(ym,(-mA,c,B)) \n#\n  heapq.heappush(yo[D],(-A,C))\n  mA, c = yo[D][0]\n  if c == C:\n    heapq.heappush(ym,(-mA,c,D)) \n#\n  while ym:\n    if AB[ ym[0][1] ][1] != ym[0][2]:\n      heapq.heappop(ym)\n    elif ym[0][1] != yo[ ym[0][2] ][0][1] :\n      heapq.heappop(ym)\n    else:\n      break\n#      \n  print((ym[0][0]))\n#\n", "from heapq import *\nn,q = map(int,input().split())\nkg = [[] for _ in range(2*10**5)]\npos = [0]*n\nrate = [0]*n\nfor i in range(n):\n    a,b = map(int,input().split())\n    b-=1\n    heappush(kg[b], (-a,i))\n    pos[i] = b\n    rate[i] = a\n\nevenness = []\nfor i in range(2*10**5):\n    if kg[i]:\n        a,c = kg[i][0]\n        heappush(evenness, (-a,c))\n\nfor _ in range(q):\n    c,d = map(int,input().split())\n    c,d = c-1,d-1\n    prev = pos[c]\n    pos[c] = d\n    heappush(kg[d], (-rate[c],c))\n    while kg[prev] and pos[kg[prev][0][1]]!=prev:\n        heappop(kg[prev])\n    while kg[d] and pos[kg[d][0][1]]!=d:\n        heappop(kg[d])\n    if kg[prev]:\n        a,c = kg[prev][0]\n        heappush(evenness, (-a,c))\n    if kg[d]:\n        a,c = kg[d][0]\n        heappush(evenness, (-a,c))\n    while evenness and kg[pos[evenness[0][1]]][0][1]!=evenness[0][1]:\n        heappop(evenness)\n    print(evenness[0][0])", "from collections import defaultdict\nimport heapq\n\nn, q = map(int, input().split())\nkindergarten = defaultdict(lambda : [])\n\nbest = []\nA, B = [], []\n\nfor i in range(n):\n    a, b = map(int, input().split())\n    A.append(a)  # \u30b9\u30b3\u30a2\n    B.append(b)  # \u5e7c\u7a1a\u5712\u756a\u53f7\n    heapq.heappush(kindergarten[b], (-a, i))\n\nfor i in kindergarten:\n    tmp = kindergarten[i][0]\n    heapq.heappush(best, (-tmp[0], tmp[1]))\n\nfor i in range(q):\n    c, d = map(int, input().split())  # c: \u5e7c\u5150\u306e\u756a\u53f7, d: \u8ee2\u5712\u5148\u306e\u5e7c\u7a1a\u5712\u756a\u53f7\n    kd_ori = B[c-1]\n    B[c-1] = d\n\n    while kindergarten[kd_ori]:\n        x = kindergarten[kd_ori][0]\n        if B[x[1]] != kd_ori:\n            heapq.heappop(kindergarten[kd_ori])\n            continue\n        heapq.heappush(best, (-x[0], x[1]))\n        break\n    heapq.heappush(kindergarten[d], (-A[c-1], c-1))\n\n    while kindergarten[d]:\n        tmp = kindergarten[d][0]\n        heapq.heappush(best, (-tmp[0], tmp[1]))\n        break\n\n    while best:\n        tmp = best[0]\n\n        tmp2 = kindergarten[B[tmp[1]]][0]\n        if -tmp2[0] != tmp[0]:\n            heapq.heappop(best)\n            continue\n        print(tmp[0])\n        break\n\n    print()", "from heapq import*\nf,g=heappush,heappop\n(n,q),*z=[[*map(int,t.split())]for t in open(0)]\n*x,(l,r)=eval('[[],[]],'*8**6)\nfor a,b in z[:n]:f(x[b][0],-a)\nfor t,_ in x:t and f(l,-t[0])\nfor c,d in z[n:]:\n a,b=z[c-1];z[c-1]=a,d;v,w=x[b];y,_=x[d];t=0;f(w,-a)\n if-v[0]==a:\n  while w and w[0]==v[0]:g(w),g(v)\n  f(r,a);v and f(l,-v[0])\n if y:t=y[0]\n f(y,-a)\n if y[0]!=t:f(l,a);t<0and f(r,-t)\n while r and l[0]==r[0]:g(l),g(r)\n print(l[0])", "from heapq import heappop, heappush\n# \u30d7\u30e9\u30a4\u30aa\u30ea\u30c6\u30a3\u30ad\u30e5\u30fc\n# \u8981\u7d20\u306e\u633f\u5165\u3001\u6700\u5c0f\u5024\uff08\u6700\u5927\u5024\uff09\u306e\u53d6\u308a\u51fa\u3057\u304c\u901f\u3044\n# \u5712\u5150\u306e\u8ee2\u5712\u306b\u3088\u308b\u524a\u9664\u304c\u30dc\u30c8\u30eb\u30cd\u30c3\u30af\n# \u524a\u9664\u3057\u306a\u3051\u308c\u3070\u826f\u3044\u3068\u8003\u3048\u308b\uff08\u52ff\u8ad6\u30c1\u30a7\u30c3\u30af\u306f\u5fc5\u8981\uff09\n\nN, Q = list(map(int, input().split()))\n\n# \u5e7c\u7a1a\u5712\u306e\u6570\nM = 2 * (10 ** 5)\n# \u5e7c\u5150i\u306e\u6240\u5c5e\u5148\u306e\u5e7c\u7a1a\u5712\nbelong = [None] * N\n# \u5e7c\u5150i\u306e\u30ec\u30fc\u30c8\nrate = [None] * N\n# \u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3002(\u30de\u30a4\u30ca\u30b9\u30ec\u30fc\u30c8, \u5e7c\u5150\u756a\u53f7)\n# KinDerGarTen\nkdgt = [[] for _ in range(M)]\n\nfor c in range(N):\n    A, B = list(map(int, input().split()))\n    # \u5e7c\u7a1a\u5712\u756a\u53f7\u30920-index\u306b\u3059\u308b\n    B -= 1\n    # \u6240\u5c5e\n    belong[c] = B\n    # \u30ec\u30fc\u30c8\n    rate[c] = A\n    # \u5e7c\u7a1a\u5712\u306e\u7bb1\u306b\u5bfe\u3057\u3066\u3001(\u30de\u30a4\u30ca\u30b9\u30ec\u30fc\u30c8\u3001\u5e7c\u5150\u756a\u53f7)\n    heappush(kdgt[B], (-A, c))\n\n# \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3002(\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8, \u5e7c\u5150\u756a\u53f7, \u5712\u756a\u53f7)\nq = []\n\n# \u5404\u5e7c\u7a1a\u5712\u306b\u3064\u3044\u3066\nfor i in range(M):\n    # \u4e00\u4eba\u3082\u6240\u5c5e\u3057\u3066\u3044\u306a\u3051\u308c\u3070\u30d1\u30b9\n    if kdgt[i]:\n        # \u30de\u30a4\u30ca\u30b9\u304c\u304b\u304b\u3063\u3066\u3044\u308b\u306e\u3067\u6700\u5927\u5024\u304c\u53d6\u308a\u51fa\u305b\u308b\n        A, c = kdgt[i][0]\n        # (\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8\u3001\u5e7c\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7)\n        heappush(q, (-A, c, i))\n\nfor _ in range(Q):\n    C, D = list(map(int, input().split()))\n    # \u5e7c\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7\u30920-index\u306b\n    C -= 1\n    D -= 1\n    # \u79fb\u52d5\u5143\u306e\u5e7c\u7a1a\u5712\n    pd = belong[C]\n    # \u5e7c\u5150\u306ebelong\u3092\u66f4\u65b0\n    belong[C] = D\n\n    # \u79fb\u52d5\u5143\u306e\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3092\u66f4\u65b0\n    while kdgt[pd]:\n        # \u305d\u306e\u5712\u3067\u306e\u6700\u5f37\u5712\u5150\uff08\u4eee\uff09\n        A, c = kdgt[pd][0]\n        # \u65e2\u306b\u5b58\u5728\u3057\u306a\u3044\u3068\u304d\u3001\u53d6\u308a\u9664\u304f\n        # \u5b58\u5728\u3059\u308b\u3068\u304d, \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3078\u8ffd\u52a0\n        if belong[c] != pd:\n            heappop(kdgt[pd])\n        else:\n            heappush(q, (-A, c, pd))\n            break\n\n    # \u79fb\u52d5\u5148\u306e\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u3092\u66f4\u65b0\n    # \u5bfe\u8c61\u306e\u5e7c\u5150\u3092\u8ffd\u52a0\n    heappush(kdgt[D], (-rate[C], C))\n    while kdgt[D]:\n        # \u305d\u306e\u5712\u3067\u306e\u6700\u5f37\u5712\u5150\uff08\u4eee\uff09\n        A, c = kdgt[D][0]\n        # \u65e2\u306b\u5b58\u5728\u3057\u306a\u3044\u3068\u304d\u53d6\u308a\u9664\u304f\n        # \u5b58\u5728\u3059\u308b\u3068\u304d, \u6700\u5f37\u5712\u5150\u30ad\u30e5\u30fc\u3078\u8ffd\u52a0\n        if belong[c] != D:\n            heappop(kdgt[D])\n        else:\n            heappush(q, (-A, c, D))\n            break\n\n    while q:\n        # \u6700\u5f37\u306e\u4e2d\u306e\u6700\u5f31\uff08\u4eee\uff09\n        # (\u30d7\u30e9\u30b9\u30ec\u30fc\u30c8\u3001\u5712\u5150\u756a\u53f7\u3001\u5712\u756a\u53f7)\n        A, c, d = q[0]\n        # \u30ad\u30e5\u30fc\u306e\u5148\u982d\u306e\u5712\u5150\u304c\u65e2\u306b\u53bb\u3063\u3066\u3044\u308b or \u6240\u5c5e\u3059\u308b\u5e7c\u7a1a\u5712\u30ad\u30e5\u30fc\u306e\u5148\u982d\u3067\u306f\u7121\u3044\u6642\u53d6\u308a\u9664\u304f\n        # \uff08\u5f8c\u8005\u306b\u3064\u3044\u3066\uff09\u6700\u5f37\u306e\u4e2d\u306e\u6700\u5f31\u3092\u63a2\u3057\u305f\u3044\u306e\u306b\u3001\u65e2\u306b\u6700\u5f37\u3067\u306f\u306a\u3044\u5712\u5150\u304c\u7d1b\u308c\u8fbc\u3080\u5834\u5408\u304c\u3042\u308b\uff1f\n\n        # 2\u3064\u306e\u6761\u4ef6\u3092\u78ba\u8a8d\u3059\u308b\u90e8\u5206\u304c\u3042\u307e\u308a\u7406\u89e3\u3067\u304d\u3066\u3044\u306a\u3044\u3001\u5f8c\u65e5\u6539\u3081\u3066\u8003\u3048\u308b\n        if belong[c] != d or kdgt[d][0][1] != c:\n            heappop(q)\n        else:\n            print(A)\n            break\n", "import heapq\nN,Q=list(map(int,input().split()))\nA=[0 for i in range(N)];B=[0 for i in range(N)]\nC=[0 for i in range(Q)];D=[0 for i in range(Q)]\nfor i in range(N):\n    A[i],B[i]=list(map(int,input().split()));B[i]-=1\nfor i in range(Q):\n    C[i],D[i]=list(map(int,input().split()));C[i]-=1;D[i]-=1\n#print([(A[i],B[i]) for i in range(N)])\n#print([(C[i],D[i]) for i in range(Q)])\nnowbelongs=[B[i] for i in range(N)]\nmaxrate=[]\nkindergarden=[[] for i in range(2*10**5)]\nfor i in range(N):\n    heapq.heappush(kindergarden[B[i]],(-A[i],i))\n#range(2*10**5) to range(N)\ndef saikyo_enji(k):\n    while(kindergarden[k]):\n        minusrate,index=kindergarden[k][0]\n        if nowbelongs[index]==k:\n            return index\n        else:\n            heapq.heappop(kindergarden[k])\n    return -1\nfor k in range(2*10**5):\n    i=saikyo_enji(k)\n    if i!=-1:\n        heapq.heappush(maxrate,(A[i],i))\n#print(-1,maxrate,[A[saikyo_enji(i)] for i in range(3)],kindergarden[:3])\nfor j in range(Q):\n    i=C[j]\n    #print(\"#\"*30)\n    #print([(A[i],nowbelongs[i]) for i in range(N)],nowbelongs[C[j]],D[j])\n    oldbelongs=nowbelongs[i]\n    nowbelongs[i]=-1\n    if saikyo_enji(oldbelongs)!=-1:\n        heapq.heappush(maxrate,(A[saikyo_enji(oldbelongs)],saikyo_enji(oldbelongs)))\n    heapq.heappush(kindergarden[D[j]],(-A[C[j]],C[j]))\n    nowbelongs[C[j]]=D[j]\n    heapq.heappush(maxrate,(A[saikyo_enji(D[j])],saikyo_enji(D[j])))\n    #print(j,maxrate,[A[saikyo_enji(i)] for i in range(3)])\n    #print([(A[i],nowbelongs[i]) for i in range(N)])\n    while(maxrate):\n        rate,index=maxrate[0]\n        if saikyo_enji(nowbelongs[index])==index:\n            print(rate)\n            break\n        else:\n            heapq.heappop(maxrate)\n"]