3171: 小Qの猫娘工坊

你发现了小Q的猫娘工坊，你已经得知，工坊里一共有 $n$ 只猫娘，从左到右排成一行，坐标从 $1$ 到 $n$，对于初始位于坐标 $i$ 处的猫娘，有一个名字 $s_i$ 和一个灵力值 $v_i$。
小Q并不想让你接近ta的猫娘，除非你能准确叫出每个猫娘的名字。
小Q一共有 $q$ 组询问，对于每组询问，小Q会先使用魔法令区间 $[l,r]$ 中的猫娘按灵力值由小到大或由大到小排序（$l \le r$，若灵力值相同则保持原来的顺序关系），然后询问你位于坐标 $k$ 处的猫娘的名字。
你能准确回答小Q的所有询问吗？

第一行两个正整数 $n,q$，表示猫娘的数量与询问的数量。
接下来 $n$ 行，第 $i$ 行有一个字符串 $s_i$ 和一个正整数 $v_i$，表示初始位于坐标 $i$ 处的猫娘的名字和灵力值。
接下来 $q$ 行，第 $i$ 行有四个正整数 $l_i,r_i,p_i,k_i$，表示待排序的区间的左端点、区间的右端点、操作方式（$1$ 为由小到大排序，$2$ 为由大到小排序）和询问的坐标。

共 $q$ 行，第 $i$ 行一个字符串 $w_i$，代表第 $i$ 个询问的答案。

5 5
qa 15
qb 16
qc 15
qd 11
qe 20
1 2 2 1
2 3 1 2
1 1 2 1
1 5 2 3
1 5 1 3

qb
qa
qb
qa
qc