Meereen is famous for its fighting pits where fighters fight each other to the death.

Initially, there are $n$ fighters and each fighter has a strength value. The $n$ fighters are divided into $\boldsymbol{\mbox{k}}$ teams, and each fighter belongs exactly one team. For each fight, the Great Masters of Meereen choose two teams, $\boldsymbol{x}$ and $y$, that must fight each other to the death. The teams attack each other in alternating turns, with team $\boldsymbol{x}$ always launching the first attack. The fight ends when all the fighters on one of the teams are dead.

Assume each team always attacks optimally. Each attack is performed as follows:

The attacking team chooses a fighter from their team with strength $\boldsymbol{\mathrm{~S~}}$.
The chosen fighter chooses at most $\boldsymbol{\mathrm{~S~}}$ fighters from other team and kills all of them. 

The Great Masters don't want to see their favorite fighters fall in battle, so they want to build their teams carefully and know who will win different team matchups. They want you to perform two type of queries:

1 p x Add a new fighter with strength $\boldsymbol{p}$ to team $\boldsymbol{x}$. It is guaranteed that this new fighter's strength value will not be less than any current member of team $\boldsymbol{x}$.
2 x y Print the name of the team that would win a matchup between teams $\boldsymbol{x}$ and $y$ in their current state (recall that team $\boldsymbol{x}$ always starts first). It is guaranteed that $x\neq y$. 

Given the initial configuration of the teams and $\textit{q}$ queries, perform each query so the Great Masters can plan the next fight.

Note: You are determining the team that would be the winner if the two teams fought. No fighters are actually dying in these matchups so, once added to a team, a fighter is available for all future potential matchups.

Input Format

The first line contains three space-separated integers describing the respective values of $n$ (the number of fighters), $\boldsymbol{\mbox{k}}$ (the number of teams), and $\textit{q}$ (the number of queries). 

Each line $\boldsymbol{i}$ of the $n$ subsequent lines contains two space-separated integers describing the respective values of fighter $\boldsymbol{i}$'s strength, $s_i$, and team number, $t_i$. 

Each of the $\textit{q}$ subsequent lines contains a space-separated query in one of the two formats defined in the Problem Statement above (i.e., 1 p x or 2 x y).

Constraints

$1\leq n,q\leq2\times10^5$
$2\leq k\leq2\times10^5$
$1\leq x,y,t_i\leq k$
$1\leq s_i,p\leq2\times10^5$
It is guaranteed that both teams in a query matchup will always have at least one fighter.

Scoring 

This challange has binary scoring. This means you will get a full score if your solution passes all test cases; otherwise, you will get $0$ points.

Output Format

After each type $2$ query, print the name of the winning team on a new line. For example, if $x=1$ and $y=2$ are matched up and $\boldsymbol{x}$ wins, you would print $1$.

Sample Input
7 2 6
1 1
2 1
1 1
1 2
1 2
1 2
2 2
2 1 2
2 2 1
1 2 1
1 2 1
2 1 2
2 2 1

Sample Output
1
2
1
1

Explanation

Team $1$ has three fighters with the following strength levels: $S_1=\{1,1,2\}$. 

Team $2$ has four fighters with the following strength levels: $S_2=\{1,1,1,2\}$.      

The first query matching up team $x=1$ and $y=2$ would play out as follows:

Team $x=1$ attacks $\rightarrow$ The fighter with strength $2$ can kill one fighter with strength $2$ and one fighter with strength $1$. Now, $S_1=\{1,1,2\}$, and $S_2=\{1,1\}$.
Team $x=2$ attacks $\rightarrow$ The fighter with strength $1$ can kill the fighter with strength $2$. Now, $S_1=\{1,1\}$, and $S_2=\{1,1\}$.
Team $x=1$ attacks $\rightarrow$ The fighter with strength $1$ can kill one fighter with strength $1$. Now, $S_1=\{1,1\}$, and $S_2=\{1\}$.
Team $x=2$ attacks $\rightarrow$ The fighter with strength $1$ can kill one fighter with strength $1$. Now, $S_1=\{1\}$, and $S_2=\{1\}$.
Team $x=1$ attacks $\rightarrow$ The fighter with strength $1$ can kill the last fighter with strength $1$. Now, $S_1=\{1\}$, and $S_2=\{\}$.

After this last attack, all of Team $2$'s fighters would be dead. Thus, we print $1$ as team $1$ would win that fight.

Source: hackerrank | Difficulty: MEDIUM_HARD
Tags: Greedy algorithms


Solutions:
from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import sys

def compare(x, y):
	i = len(x)
	j = len(y)
	while i > 0 and j > 0:
		if x[i - 1] >= y[j - 1]:
			return True
		else:
			if i == 1:
				if j > x[0]:
					return False
				else:
					return True
			j -= x[i - 1] - x[i - 2]
			if j < 1:
				return True
		if y[j - 1] >= x[i - 1]:
			return False
		else:
			if j == 1:
				if i > y[0]:
					return True
				else:
					return False
			i -= y[j - 1] - y[j - 2]
	return False if i < 1 else True

def psum(x):
	ans = []
	sum = 0
	for i in x:
		sum += i
		ans.append(sum)
	return ans
(n, k, q) = map(int, sys.stdin.readline().strip().split())
teams = []
for i in range(k):
	teams.append([])
for i in range(n):
	(s, t) = map(int, sys.stdin.readline().strip().split())
	teams[t - 1].append(s)
for (i, t) in enumerate(teams):
	teams[i] = psum(sorted(t))
for i in range(q):
	(a, b, c) = map(int, sys.stdin.readline().strip().split())
	if a == 1:
		if teams[c - 1]:
			teams[c - 1].append(b + teams[c - 1][-1])
		else:
			teams[c - 1].append(b)
	elif compare(teams[b - 1], teams[c - 1]):
		print(b)
	else:
		print(c)


from itertools import accumulate
(n, k, q) = map(int, input().split(' '))
T = [[0] for i in range(k)]
for _ in range(n):
	(s, t) = map(int, input().split(' '))
	T[t - 1].append(s)
T = list(map(lambda x: list(accumulate(sorted(x))), T))
for _ in range(q):
	(c, x, y) = map(int, input().split(' '))
	if c == 1:
		T[y - 1].append(T[y - 1][-1] + x)
	else:
		X = T[x - 1]
		Y = T[y - 1]
		Xl = len(X)
		Yl = len(Y)
		while 1:
			if X[Xl - 1] >= Y[Yl - 1]:
				print(x)
				break
			Yl -= X[Xl - 1] - X[Xl - 2]
			if Yl <= 1:
				print(x)
				break
			if Y[Yl - 1] >= X[Xl - 1]:
				print(y)
				break
			Xl -= Y[Yl - 1] - Y[Yl - 2]
			if Xl <= 1:
				print(y)
				break


from itertools import accumulate
(n, k, q) = list(map(int, input().split()))
fighters = [[0] for i in range(k + 1)]
size = [0 for i in range(k + 1)]
tstrength = [0 for i in range(k + 1)]
tstrength2 = [[0]]
for _ in range(n):
	(strength, team) = list(map(int, input().split()))
	fighters[team].append(strength)
	tstrength[team] += strength
	size[team] += 1
for i in range(1, k + 1):
	fighters[i].sort()
	tstrength2.append(list(accumulate(fighters[i])))
for _ in range(q):
	(action, a, b) = list(map(int, input().split()))
	if action == 1:
		fighters[b].append(a)
		tstrength[b] += a
		tstrength2[b].append(tstrength[b])
		size[b] += 1
	else:
		numx = size[a]
		numy = size[b]
		stry = tstrength2[b][numy]
		while numx > 0:
			strx = tstrength2[a][numx]
			if strx >= stry:
				print(a)
				break
			numy -= fighters[a][numx]
			if numy <= 0:
				print(a)
				break
			else:
				stry = tstrength2[b][numy]
				if stry >= strx:
					print(b)
					break
				else:
					numx -= fighters[b][numy]
		else:
			print(b)


(n, k, q) = map(int, input().strip().split(' '))
teams = []
total_strengths = []
for i in range(k):
	teams.append([])
	total_strengths.append([])
for i in range(n):
	(s, t) = map(int, input().strip().split(' '))
	teams[t - 1].append(s)
for i in range(len(teams)):
	teams[i].sort()
	total = 0
	for j in range(len(teams[i])):
		total += teams[i][j]
		total_strengths[i].append(total)
winners = {}
for i in range(q):
	(a, b, c) = map(int, input().strip().split(' '))
	if a == 1:
		teams[c - 1].append(b)
		ts = total_strengths[c - 1]
		if len(ts) > 0:
			ts.append(ts[len(ts) - 1] + b)
		else:
			ts.append(b)
	else:
		tb = teams[b - 1]
		tc = teams[c - 1]
		tsb = total_strengths[b - 1]
		tsc = total_strengths[c - 1]
		ib = len(tb) - 1
		ic = len(tc) - 1
		if ic < 0:
			print(b)
			continue
		keys = []
		winner = -1
		while True:
			key = '{0}.{1}-{2}.{3}'.format(b, ib, c, ic)
			if key in winners:
				winner = winners[key]
				break
			if ib < 0:
				winner = c
				break
			if tsb[ib] >= tsc[ic]:
				winner = b
				break
			ic -= tb[ib]
			if ic < 0:
				winner = b
				break
			if tsc[ic] >= tsb[ib]:
				winner = c
				break
			ib -= tc[ic]
		print(winner)
		if not key in winners:
			for j in keys:
				winners[j] = winner


(n, k, q) = input().strip().split(' ')
(n, q, k) = [int(n), int(q), int(k)]

class teams(object):

	def __init__(self, k):
		self.teams = [i for i in range(1, k + 1)]
		self.fight = {i: [] for i in self.teams}
		self.ma = {i: 0 for i in self.teams}
		self.prov = {i: [] for i in self.teams}
		self.ind = {i: 0 for i in self.teams}
		self.listpuiss = {i: [0] for i in self.teams}

	def add_fighter(self, x, p, act):
		if act and self.fight[x] == [] or p >= self.ma[x]:
			self.fight[x].append(p)
			self.listpuiss[x].append(p + self.listpuiss[x][-1])
			self.ma[x] = p
			self.ind[x] = len(self.listpuiss[x]) - 1
		elif act and p < self.ma[x]:
			idx = len([j for j in self.fight[x] if j <= p])
			self.fight[x].insert(idx - 1, p)
			self.listpuiss[x].insert(idx + 1, self.listpuiss[x][idx] + p)
			for j in range(idx + 2, len(self.listpuiss[x])):
				self.listpuiss[x][j] += p
			self.ind[x] = len(self.listpuiss[x]) - 1
		else:
			self.fight[x].append(p)

	def actual(self):
		self.listpuiss = {i: [0] for i in self.teams}
		for i in self.teams:
			if not self.fight[i] == []:
				self.fight[i] = sorted(self.fight[i])
				self.ma[i] = max(self.fight[i])
				mem = 0
				for j in self.fight[i]:
					mem = mem + j
					self.listpuiss[i].append(mem)

	def rebootprov(self):
		self.ind = {i: len(self.listpuiss[i]) - 1 for i in self.teams}

	def round(self, x, y):
		if self.listpuiss[x][self.ind[x]] >= self.listpuiss[y][self.ind[y]]:
			return True
		elif self.ind[y] <= 0:
			return True
		elif not self.ind[x] <= 0:
			bf = self.listpuiss[x][self.ind[x]] - self.listpuiss[x][self.ind[x] - 1]
			self.ind[y] -= bf
			return self.ind[y] <= 0
		else:
			return False

	def combat(self, x, y):
		self.ind[x] = len(self.listpuiss[x]) - 1
		self.ind[y] = len(self.listpuiss[y]) - 1
		xwin = False
		ywin = False
		while not (xwin or ywin):
			if self.ind[x] <= 0:
				ywin = True
			elif self.ind[y] <= 0:
				xwin = True
			else:
				xwin = self.round(x, y)
				if not xwin:
					if self.ind[y] <= 0:
						xwin = True
					else:
						ywin = self.round(y, x)
		if xwin:
			return x
		if ywin:
			return y
t = teams(k)
for i in range(n):
	(p, x) = input().strip().split(' ')
	(p, x) = [int(p), int(x)]
	t.add_fighter(x, p, False)
t.actual()
for qu in range(q):
	(c, p, x) = input().strip().split(' ')
	if int(c) == 1:
		(p, x) = [int(p), int(x)]
		t.add_fighter(x, p, True)
	if int(c) == 2:
		(x, y) = [int(p), int(x)]
		print(t.combat(x, y))


(n, k, q) = [int(x) for x in input().split()]
fs = [[] for _ in range(k + 1)]
for _ in range(n):
	(s, t) = [int(x) for x in input().split()]
	fs[t].append(s)
fs = [sorted(team) for team in fs]
ss = [team[:] for team in fs]
for i in range(len(ss)):
	for j in range(1, len(ss[i])):
		ss[i][j] += ss[i][j - 1]
for _ in range(q):
	(a, x, y) = [int(x) for x in input().split()]
	if a == 1:
		fs[y].append(x)
		ss[y].append(x + ss[y][-1]) if ss[y] else ss[y].append(x)
	else:
		lenx = len(fs[x])
		leny = len(fs[y])
		sx = ss[x][-1]
		sy = ss[y][-1]
		while lenx > 0 and leny > 0:
			if sx >= sy:
				leny = 0
				break
			leny -= fs[x][lenx - 1]
			if leny <= 0:
				break
			sy = ss[y][leny - 1]
			if sy >= sx:
				lenx = 0
				break
			lenx -= fs[y][leny - 1]
			if lenx > 0:
				sx = ss[x][lenx - 1]
		if lenx > 0:
			print(x)
		else:
			print(y)


def fight(x, y, prefix_sums, teams):
	chance = True
	x_pos = len(teams[x]) - 1
	y_pos = len(teams[y]) - 1
	sum_x = prefix_sums[x][x_pos]
	sum_y = prefix_sums[y][y_pos]
	while True:
		if chance:
			if sum_x >= sum_y:
				return x + 1
			else:
				y_end = y_pos
				y_pos -= teams[x][x_pos]
				if y_pos < 0:
					return x + 1
				else:
					sum_y = prefix_sums[y][y_pos]
		elif sum_y >= sum_x:
			return y + 1
		else:
			x_end = x_pos
			x_pos -= teams[y][y_pos]
			if x_pos < 0:
				return y + 1
			else:
				sum_x = prefix_sums[x][x_pos]
		chance = not chance

def main():
	(n, k, q) = map(int, input().split())
	prefix_sums = [[] for _ in range(k)]
	teams = [[] for _ in range(k)]
	for i in range(n):
		(s, t) = map(int, input().split())
		teams[t - 1].append(s)
	for i in range(k):
		teams[i] = sorted(teams[i])
		if len(teams[i]) != 0:
			prefix_sums[i].append(teams[i][0])
		for j in range(1, len(teams[i])):
			prefix_sums[i].append(prefix_sums[i][j - 1] + teams[i][j])
	for _ in range(q):
		(c, x, y) = input().split()
		c = int(c)
		x = int(x)
		y = int(y)
		if c == 1:
			teams[y - 1].append(x)
			if len(teams[y - 1]) == 1:
				prefix_sums[y - 1].append(x)
			else:
				prefix_sums[y - 1].append(prefix_sums[y - 1][len(teams[y - 1]) - 2] + x)
		else:
			print(fight(x - 1, y - 1, prefix_sums, teams))
main()


import bisect

def getwinner(x, y, t, tsa, r):
	turn = [x, y]
	cur = 0
	other = 1
	ts = [tsa[turn[cur]], tsa[turn[other]]]
	ti = [len(t[turn[cur]]) - 1, len(t[turn[other]]) - 1]
	while ti[0] >= 0 and ti[1] >= 0 and (ts[cur] < ts[other]):
		v = t[turn[other]]
		l = t[turn[cur]][ti[cur]]
		rem = min(l, ti[other] + 1)
		newsum = 0
		if ti[other] - rem >= 0:
			newsum = r[turn[other]][ti[other] - rem]
		ts[other] = newsum
		ti[other] -= rem
		cur ^= 1
		other ^= 1
	winner = turn[other]
	loser = turn[cur]
	if ti[cur] >= 0:
		winner = turn[cur]
		loser = turn[other]
	return winner
(n, k, q) = map(int, input().split(' '))
t = [[] for _ in range(k)]
r = [[] for _ in range(k)]
ts = [0] * k
for i in range(n):
	(pi, ti) = map(int, input().split(' '))
	ti -= 1
	t[ti].append(pi)
	ts[ti] += pi
for i in range(k):
	t[i].sort()
for i in range(k):
	if len(t[i]) == 0:
		continue
	r[i].append(t[i][0])
	for j in range(1, len(t[i])):
		r[i].append(r[i][j - 1] + t[i][j])
for i in range(q):
	v = list(map(int, input().split(' ')))
	if v[0] == 1:
		t[v[2] - 1].append(v[1])
		ts[v[2] - 1] += v[1]
		if len(r[v[2] - 1]) > 0:
			r[v[2] - 1].append(r[v[2] - 1][len(r[v[2] - 1]) - 1] + v[1])
		else:
			r[v[2] - 1].append(v[1])
	else:
		print(getwinner(v[1] - 1, v[2] - 1, t, ts, r) + 1)


import itertools

def fight(team1, team2, acc1, acc2, x, y):
	i = len(team1) - 1
	j = len(team2) - 1
	while True:
		if i < 0:
			return y
		if j < 0 or acc1[i] >= acc2[j]:
			return x
		j -= team1[i]
		if j < 0:
			return x
		if i < 0 or acc2[j] >= acc1[i]:
			return y
		i -= team2[j]
[n, k, q] = list(map(int, input().strip().split(' ')))
teams = dict([(i, ([], [])) for i in range(1, k + 1)])
for i in range(n):
	[s, t] = list(map(int, input().strip().split(' ')))
	teams[t][0].append(s)
for (t, team) in teams.items():
	team[0].sort()
	team[1].extend(itertools.accumulate(team[0]))
for i in range(q):
	[t, a, b] = list(map(int, input().strip().split(' ')))
	if t == 1:
		teams[b][0].append(a)
		if len(teams[b][1]) == 0:
			teams[b][1].append(a)
		else:
			teams[b][1].append(teams[b][1][-1] + a)
	else:
		print(fight(teams[a][0], teams[b][0], teams[a][1], teams[b][1], a, b))


(n, k, q) = [int(i) for i in input().strip().split()]
teams = [[] for _ in range(k + 1)]
totals = [[] for _ in range(k + 1)]

def add_fighter(s, t, add_total=True):
	teams[t].append(s)
	if add_total:
		total = totals[t]
		prev = 0 if len(total) == 0 else total[-1]
		total.append(s + prev)

def fight(t1, t2):
	f1 = len(teams[t1]) - 1
	f2 = len(teams[t2]) - 1
	while True:
		if totals[t1][f1] >= totals[t2][f2]:
			return t1
		f2 -= teams[t1][f1]
		if f2 < 0:
			return t1
		if totals[t2][f2] >= totals[t1][f1]:
			return t2
		f1 -= teams[t2][f2]
		if f1 < 0:
			return t2
for _ in range(n):
	(s, t) = [int(i) for i in input().strip().split()]
	add_fighter(s, t, False)
for i in range(len(teams)):
	team = teams[i]
	team.sort()
	total = totals[i]
	running = 0
	for j in team:
		running += j
		total.append(running)
for _ in range(q):
	(p1, p2, p3) = [int(i) for i in input().strip().split()]
	if p1 == 1:
		add_fighter(p2, p3)
		continue
	print(fight(p2, p3))


(n, t, q) = map(int, input().split())
t = t + 1
team = [[] for i in range(t)]

def comp(b, c):
	i1 = len(team[b]) - 1
	i2 = len(team[c]) - 1
	if i1 < 0:
		print(c)
	elif i2 < 0:
		print(b)
	while i1 >= 0 and i2 >= 0:
		if team[b][i1] >= team[c][i2]:
			return b
		d = team[b][i1] if i1 == 0 else team[b][i1] - team[b][i1 - 1]
		i2 = i2 - d
		if i2 >= 0:
			if team[b][i1] <= team[c][i2]:
				return c
			d = team[c][i2] if i2 == 0 else team[c][i2] - team[c][i2 - 1]
			i1 = i1 - d
			if i1 < 0:
				return c
		else:
			return b
for i in range(n):
	(s, tt) = map(int, input().split())
	team[tt].append(s)
for i in range(1, t):
	team[i].sort()
for i in range(1, t):
	for j in range(1, len(team[i])):
		team[i][j] = team[i][j] + team[i][j - 1]
for i in range(q):
	(a, b, c) = map(int, input().split())
	if a == 1:
		if len(team[c]) > 0:
			team[c].append(b + team[c][-1])
		else:
			team[c].append(b)
	else:
		print(comp(b, c))


def win(a, b, x, y):
	if b == None:
		return True
	if a == None:
		return False
	xy = x * 100000 + y
	(pa, pb) = (len(a) - 1, len(b) - 1)
	(la, lb) = (pa, pb)
	cr = None
	if xy in CACHE:
		cr = CACHE[xy]
	if cr != None:
		if cr[0] == la and cr[1] == lb:
			return cr[2]
		if cr[2] and lb == cr[1] and (la > cr[0]):
			return True
		if not cr[2] and la == cr[0] and (lb > cr[1]):
			return False
	while pa > 0 and pb > 0:
		if a[pa] >= b[pb]:
			pb == 0
			break
		pb = pb - a[pa] + a[pa - 1]
		if pb > 0:
			if b[pb] >= a[pa]:
				pa = 0
				break
			pa = pa - b[pb] + b[pb - 1]
	rs = pa > 0
	if cr == None:
		cr = [la, lb, rs]
		CACHE[xy] = cr
	else:
		cr[0] = la
		cr[1] = lb
		cr[2] = rs
	return rs
(n, k, q) = map(int, input().split(' '))
teams = {}
CACHE = {}
E = None
for i in range(n):
	(s, t) = map(int, input().split(' '))
	if not t in teams:
		teams[t] = [0]
	teams[t].append(s)
for ti in teams:
	tti = teams[ti]
	tti.sort()
	for i in range(1, len(tti)):
		tti[i] = tti[i] + tti[i - 1]
for i in range(q):
	(c, x, y) = map(int, input().split(' '))
	if c == 1:
		if not y in teams:
			teams[y] = [0]
		teams[y].append(teams[y][-1] + x)
	else:
		print(x if win(teams[x] if x in teams else E, teams[y] if y in teams else E, x, y) else y)


import os
import sys
from collections import defaultdict

def fight(teams, x, y):
	global mem
	nx = x
	ny = y
	x = teams[x]
	y = teams[y]
	sx = x[1]
	sy = y[1]
	x = x[0]
	y = y[0]
	ix = len(x)
	iy = len(y)
	while True:
		if sx[ix] >= sy[iy]:
			return nx
		f = x[ix - 1]
		iy -= f
		if iy <= 0:
			return nx
		if sy[iy] >= sx[ix]:
			return ny
		f = y[iy - 1]
		ix -= f
		if ix <= 0:
			return ny

def fightingPits(teams, queries):
	fightno = 0
	for q in queries:
		(q_type, x, y) = q
		if q_type == 1:
			teams[y][0].append(x)
			teams[y][1].append(x + teams[y][1][-1])
		else:
			fightno += 1
			winner = fight(teams, x, y)
			print(winner)
(n_f, n_t, n_q) = map(int, input().strip().split())
teams = defaultdict(lambda : [[], [0]])
for i in range(n_f):
	(strength, team) = map(int, input().rstrip().split())
	teams[team][0].append(strength)
for team in teams.values():
	team[0].sort()
	for i in team[0]:
		team[1].append(i + team[1][-1])
queries = []
for _ in range(n_q):
	queries.append(list(map(int, input().strip().split())))
fightingPits(teams, queries)


(n, k, q) = map(int, input().split())
a = []
suu = []
for i in range(k):
	a.append([])
	suu.append([])
for i in range(n):
	(s, t) = map(int, input().split())
	a[t - 1] += [s]
for i in range(k):
	a[i].sort()
	c = 0
	for j in a[i]:
		c += j
		suu[i] += [c]
for i in range(q):
	qu = list(map(int, input().split()))
	if qu[0] == 1:
		a[qu[2] - 1] += [qu[1]]
		if len(suu[qu[2] - 1]) > 0:
			suu[qu[2] - 1] += [qu[1] + suu[qu[2] - 1][-1]]
		else:
			suu[qu[2] - 1] += [qu[1]]
	else:
		x = qu[1] - 1
		y = qu[2] - 1
		i = len(a[x]) - 1
		j = len(a[y]) - 1
		c = 0
		while i >= 0 and j >= 0:
			if c % 2 == 0:
				if suu[x][i] >= suu[y][j]:
					j = -1
					break
				j = j - a[x][i]
			else:
				if suu[x][i] <= suu[y][j]:
					i = -1
					break
				i = i - a[y][j]
			c += 1
		if j >= 0:
			print(y + 1)
		else:
			print(x + 1)


import sys

def compare(x, y):
	i = len(x)
	j = len(y)
	while i > 0 and j > 0:
		if x[i - 1] >= y[j - 1]:
			return True
		else:
			if i == 1:
				if j > x[0]:
					return False
				else:
					return True
			j -= x[i - 1] - x[i - 2]
			if j < 1:
				return True
		if y[j - 1] >= x[i - 1]:
			return False
		else:
			if j == 1:
				if i > y[0]:
					return True
				else:
					return False
			i -= y[j - 1] - y[j - 2]
	return False if i < 1 else True

def psum(x):
	ans = []
	sum = 0
	for i in x:
		sum += i
		ans.append(sum)
	return ans
(n, k, q) = map(int, sys.stdin.readline().strip().split())
teams = []
for i in range(k):
	teams.append([])
for i in range(n):
	(s, t) = map(int, sys.stdin.readline().strip().split())
	teams[t - 1].append(s)
for (i, t) in enumerate(teams):
	teams[i] = psum(sorted(t))
for i in range(q):
	(a, b, c) = map(int, sys.stdin.readline().strip().split())
	if a == 1:
		if teams[c - 1]:
			teams[c - 1].append(b + teams[c - 1][-1])
		else:
			teams[c - 1].append(b)
	elif compare(teams[b - 1], teams[c - 1]):
		print(b)
	else:
		print(c)


(n, k, q) = [int(x) for x in input().split()]
fs = [[] for _ in range(k + 1)]
for _ in range(n):
	(s, t) = [int(x) for x in input().split()]
	fs[t].append(s)
fs = [sorted(team) for team in fs]
ss = [team[:] for team in fs]
for i in range(len(ss)):
	for j in range(1, len(ss[i])):
		ss[i][j] += ss[i][j - 1]
for _ in range(q):
	(a, x, y) = [int(x) for x in input().split()]
	if a == 1:
		fs[y].append(x)
		ss[y].append(x + ss[y][-1]) if ss[y] else ss[y].append(x)
	else:
		lenx = len(fs[x])
		leny = len(fs[y])
		sx = ss[x][-1]
		sy = ss[y][-1]
		while lenx > 0 and leny > 0:
			if sx >= sy:
				leny = 0
				break
			leny -= fs[x][lenx - 1]
			if leny <= 0:
				break
			sy = ss[y][leny - 1]
			if sy >= sx:
				lenx = 0
				break
			lenx -= fs[y][leny - 1]
			if lenx > 0:
				sx = ss[x][lenx - 1]
		if lenx > 0:
			print(x)
		else:
			print(y)


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import sys

def compare(x, y):
	i = len(x)
	j = len(y)
	while i > 0 and j > 0:
		if x[i - 1] >= y[j - 1]:
			return True
		else:
			if i == 1:
				if j > x[0]:
					return False
				else:
					return True
			j -= x[i - 1] - x[i - 2]
			if j < 1:
				return True
		if y[j - 1] >= x[i - 1]:
			return False
		else:
			if j == 1:
				if i > y[0]:
					return True
				else:
					return False
			i -= y[j - 1] - y[j - 2]
	return False if i < 1 else True

def psum(x):
	ans = []
	sum = 0
	for i in x:
		sum += i
		ans.append(sum)
	return ans
(n, k, q) = map(int, sys.stdin.readline().strip().split())
teams = []
for i in range(k):
	teams.append([])
for i in range(n):
	(s, t) = map(int, sys.stdin.readline().strip().split())
	teams[t - 1].append(s)
for (i, t) in enumerate(teams):
	teams[i] = psum(sorted(t))
for i in range(q):
	(a, b, c) = map(int, sys.stdin.readline().strip().split())
	if a == 1:
		if teams[c - 1]:
			teams[c - 1].append(b + teams[c - 1][-1])
		else:
			teams[c - 1].append(b)
	elif compare(teams[b - 1], teams[c - 1]):
		print(b)
	else:
		print(c)


(n, k, q) = [int(x) for x in input().split()]
fs = [[] for _ in range(k + 1)]
for _ in range(n):
	(s, t) = [int(x) for x in input().split()]
	fs[t].append(s)
fs = [sorted(team) for team in fs]
ss = [team[:] for team in fs]
for i in range(len(ss)):
	for j in range(1, len(ss[i])):
		ss[i][j] += ss[i][j - 1]
for _ in range(q):
	(a, x, y) = [int(x) for x in input().split()]
	if a == 1:
		fs[y].append(x)
		ss[y].append(x + ss[y][-1]) if ss[y] else ss[y].append(x)
	else:
		lenx = len(fs[x])
		leny = len(fs[y])
		sx = ss[x][-1]
		sy = ss[y][-1]
		while lenx > 0 and leny > 0:
			if sx >= sy:
				leny = 0
				break
			leny -= fs[x][lenx - 1]
			if leny <= 0:
				break
			sy = ss[y][leny - 1]
			if sy >= sx:
				lenx = 0
				break
			lenx -= fs[y][leny - 1]
			if lenx > 0:
				sx = ss[x][lenx - 1]
		if lenx > 0:
			print(x)
		else:
			print(y)


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import sys

def compare(x, y):
	i = len(x)
	j = len(y)
	while i > 0 and j > 0:
		if x[i - 1] >= y[j - 1]:
			return True
		else:
			if i == 1:
				if j > x[0]:
					return False
				else:
					return True
			j -= x[i - 1] - x[i - 2]
			if j < 1:
				return True
		if y[j - 1] >= x[i - 1]:
			return False
		else:
			if j == 1:
				if i > y[0]:
					return True
				else:
					return False
			i -= y[j - 1] - y[j - 2]
	return False if i < 1 else True

def psum(x):
	ans = []
	sum = 0
	for i in x:
		sum += i
		ans.append(sum)
	return ans
(n, k, q) = map(int, sys.stdin.readline().strip().split())
teams = []
for i in range(k):
	teams.append([])
for i in range(n):
	(s, t) = map(int, sys.stdin.readline().strip().split())
	teams[t - 1].append(s)
for (i, t) in enumerate(teams):
	teams[i] = psum(sorted(t))
for i in range(q):
	(a, b, c) = map(int, sys.stdin.readline().strip().split())
	if a == 1:
		if teams[c - 1]:
			teams[c - 1].append(b + teams[c - 1][-1])
		else:
			teams[c - 1].append(b)
	elif compare(teams[b - 1], teams[c - 1]):
		print(b)
	else:
		print(c)


import os
import sys
(n, k, q) = [int(x) for x in input().split()]
fs = [[] for _ in range(k + 1)]
for _ in range(n):
	(s, t) = [int(x) for x in input().split()]
	fs[t].append(s)
fs = [sorted(team) for team in fs]
ss = [team[:] for team in fs]
for i in range(len(ss)):
	for j in range(1, len(ss[i])):
		ss[i][j] += ss[i][j - 1]
for _ in range(q):
	(a, x, y) = [int(x) for x in input().split()]
	if a == 1:
		fs[y].append(x)
		ss[y].append(x + ss[y][-1]) if ss[y] else ss[y].append(x)
	else:
		lenx = len(fs[x])
		leny = len(fs[y])
		sx = ss[x][-1]
		sy = ss[y][-1]
		while lenx > 0 and leny > 0:
			if sx >= sy:
				leny = 0
				break
			leny -= fs[x][lenx - 1]
			if leny <= 0:
				break
			sy = ss[y][leny - 1]
			if sy >= sx:
				lenx = 0
				break
			lenx -= fs[y][leny - 1]
			if lenx > 0:
				sx = ss[x][lenx - 1]
		if lenx > 0:
			print(x)
		else:
			print(y)


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import bisect

def getwinner(x, y, t, tsa, r):
	turn = [x, y]
	cur = 0
	other = 1
	ts = [tsa[turn[cur]], tsa[turn[other]]]
	ti = [len(t[turn[cur]]) - 1, len(t[turn[other]]) - 1]
	while ti[0] >= 0 and ti[1] >= 0 and (ts[cur] < ts[other]):
		v = t[turn[other]]
		l = t[turn[cur]][ti[cur]]
		rem = min(l, ti[other] + 1)
		newsum = 0
		if ti[other] - rem >= 0:
			newsum = r[turn[other]][ti[other] - rem]
		ts[other] = newsum
		ti[other] -= rem
		cur ^= 1
		other ^= 1
	winner = turn[other]
	loser = turn[cur]
	if ti[cur] >= 0:
		winner = turn[cur]
		loser = turn[other]
	return winner
(n, k, q) = map(int, input().split(' '))
t = [[] for _ in range(k)]
r = [[] for _ in range(k)]
ts = [0] * k
for i in range(n):
	(pi, ti) = map(int, input().split(' '))
	ti -= 1
	t[ti].append(pi)
	ts[ti] += pi
for i in range(k):
	t[i].sort()
for i in range(k):
	if len(t[i]) == 0:
		continue
	r[i].append(t[i][0])
	for j in range(1, len(t[i])):
		r[i].append(r[i][j - 1] + t[i][j])
for i in range(q):
	v = list(map(int, input().split(' ')))
	if v[0] == 1:
		t[v[2] - 1].append(v[1])
		ts[v[2] - 1] += v[1]
		if len(r[v[2] - 1]) > 0:
			r[v[2] - 1].append(r[v[2] - 1][len(r[v[2] - 1]) - 1] + v[1])
		else:
			r[v[2] - 1].append(v[1])
	else:
		print(getwinner(v[1] - 1, v[2] - 1, t, ts, r) + 1)


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import math
import os
import random
import re
import sys
from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


import math
import os
import random
import re
import sys
from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()


from collections import defaultdict

def readints():
	return [int(x) for x in input().strip().split()]

class Team:

	def __init__(self, id, strengths):
		self.id = id
		self.strengths = sorted(strengths)
		self._beatable_sizes = defaultdict(lambda : [self.strengths[0]])
		self._least_winning_index = defaultdict(int)
		self.N = len(self.strengths)
		self.sum = sum(self.strengths)

	def __len__(self):
		return len(self.strengths)

	def __getitem__(self, idx):
		return self.strengths[idx]

	def add(self, strength):
		assert not self.strengths or strength >= self.strengths[-1]
		self.N += 1
		self.sum += strength
		self.strengths.append(strength)

	def simulate_fight(self, opponent, memoize=False):
		return self.id if self.can_beat(opponent, memoize) else opponent.id

	def can_beat(self, opponent, memoize):
		if memoize:
			return self.beatable_size(opponent) >= opponent.N
		else:
			i_self = self.N - 1
			i_opponent = opponent.N - 1
			while i_self >= 0:
				i_opponent -= self[i_self]
				if i_opponent < 0:
					return True
				i_self -= opponent[i_opponent]
			return False

	def beatable_size(self, opponent):
		bs = self._beatable_sizes[opponent]
		lwi = self._least_winning_index
		for i in range(len(bs), self.N):
			for lwi[opponent] in range(lwi[opponent], opponent.N):
				idx = i - opponent[lwi[opponent]]
				if idx < 0 or lwi[opponent] >= bs[idx]:
					break
			else:
				return opponent.N
			bs.append(lwi[opponent] + self[i])
		return bs[-1]

def main():
	team = {}
	(N, K, Q) = readints()
	for n in range(N):
		(s, t) = readints()
		team.setdefault(t, []).append(s)
	for (k, v) in team.items():
		t = Team(k, team[k])
		team[k] = t
	num_matches = defaultdict(int)
	queries = []
	for q in range(Q):
		(qt, *args) = readints()
		if qt == 2:
			key = frozenset(args)
			num_matches[key] += 1
			args += [key]
		queries.append((qt, args))
	memoize_set = set((k for (k, v) in num_matches.items() if v >= 1000))
	for (qt, args) in queries:
		if qt == 1:
			(p, x) = args
			team.setdefault(x, Team(x, [])).add(p)
		else:
			(x, y, key) = args
			print(team[x].simulate_fight(team[y], key in memoize_set))
main()