#include <algorithm>
#include <iostream>
#include <cassert>
#include <chrono>
#include <vector>
#include <random>
#include <stack>
#include <queue>
#include <set>
#include <map>
#ifdef DEVAL
#define cerr if (false) cerr
#endif
typedef long long llong;
const int MAXN = 300000 + 10;
const int INF = 1e9;
// macros as defined above
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
typedef __gnu_pbds::tree <int, __gnu_pbds::null_type, std::less<int>, __gnu_pbds::rb_tree_tag, __gnu_pbds::tree_order_statistics_node_update> oSet;
std::mt19937 rngNow(std::chrono::high_resolution_clock::now().time_since_epoch().count());
std::mt19937 rng(69420);
int n, q, k;
struct MergeSortTree
{
// struct Treap
// {
// struct Node
// {
// Node *left, *right;
// int subtreeSize, x, cnt, y;
// Node()
// {
// left = right = nullptr;
// }
// Node(int _x, int _y)
// {
// left = right = nullptr;
// subtreeSize = cnt = 1;
// x = _x; y = _y;
// }
// };
// Node *treap;
// void recover(Node *curr)
// {
// if (curr == nullptr)
// {
// return;
// }
// curr->subtreeSize = curr->cnt;
// if (curr->left != nullptr)
// {
// curr->subtreeSize += curr->left->subtreeSize;
// }
// if (curr->right != nullptr)
// {
// curr->subtreeSize += curr->right->subtreeSize;
// }
// }
// void split(Node *curr, Node *&left, Node *&right, int k)
// {
// if (curr == nullptr)
// {
// left = right = nullptr;
// return;
// }
// if (curr->x <= k)
// {
// left = curr;
// split(curr->right, left->right, right, k);
// recover(left);
// } else
// {
// right = curr;
// split(curr->left, left, right->left, k);
// recover(right);
// }
// }
// void merge(Node *&curr, Node *left, Node *right)
// {
// if (left == nullptr)
// {
// curr = right;
// return;
// }
// if (right == nullptr)
// {
// curr = left;
// return;
// }
// if (left->y > right->y)
// {
// curr = left;
// merge(curr->right, left->right, right);
// } else
// {
// curr = right;
// merge(curr->left, left, right->left);
// }
// recover(curr);
// }
// void insert(int value)
// {
// Node *l, *ll, *lr, *r;
// split(treap, l, r, value);
// split(l, ll, lr, value - 1);
// if (lr != nullptr)
// {
// lr->cnt++;
// // std::cout << "increment: " << lr->cnt << '\n';
// recover(lr);
// } else
// {
// lr = new Node(value, rng());
// }
// merge(l, ll, lr);
// merge(treap, l, r);
// }
// void erase(int value)
// {
// Node *l, *ll, *lr, *r;
// split(treap, l, r, value);
// split(l, ll, lr, value - 1);
// assert(lr != nullptr);
// if (lr->cnt > 1)
// {
// lr->cnt--;
// // std::cout << "decrement: " << lr->cnt << '\n';
// recover(lr);
// } else
// {
// lr = nullptr;
// }
// merge(l, ll, lr);
// merge(treap, l, r);
// }
// int countLess(int value)
// {
// int res = 0;
// Node *l, *r;
// split(treap, l, r, value - 1);
// if (l != nullptr) res = l->subtreeSize;
// merge(treap, l, r);
// return res;
// }
// };
// Treap tree[4*MAXN];
oSet tree[4*MAXN];
void insert(int l, int r, int node, int queryPos, int queryValue)
{
tree[node].insert(queryValue);
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) insert(l, mid, 2*node, queryPos, queryValue);
else insert(mid + 1, r, 2*node + 1, queryPos, queryValue);
}
void erase(int l, int r, int node, int queryPos, int queryValue)
{
tree[node].erase(tree[node].find(queryValue));
if (l == r)
{
return;
}
int mid = (l + r) / 2;
if (queryPos <= mid) erase(l, mid, 2*node, queryPos, queryValue);
else erase(mid + 1, r, 2*node + 1, queryPos, queryValue);
}
int query(int l, int r, int node, int queryL, int queryR)
{
if (queryL <= l && r <= queryR)
{
return tree[node].order_of_key(queryL);
}
int res = 0;
int mid = (l + r) / 2;
if (queryL <= mid) res += query(l, mid, 2*node, queryL, queryR);
if (mid + 1 <= queryR) res += query(mid + 1, r, 2*node + 1, queryL, queryR);
return res;
}
void insert(int pos, int value)
{
insert(1, n, 1, pos, value);
}
void erase(int pos, int value)
{
erase(1, n, 1, pos, value);
}
int query(int l, int r)
{
return query(1, n, 1, l, r);
}
void update(int pos, int oldVal, int newVal)
{
erase(pos, oldVal);
insert(pos, newVal);
}
void build(int a[])
{
for (int i = 1 ; i <= n ; ++i)
{
insert(i, a[i]);
}
}
};
struct Store
{
int pos;
int l, r;
int type;
friend bool operator < (const Store &a, const Store &b)
{
return a.pos < b.pos;
}
};
struct Query
{
int year;
int pos;
int idx;
friend bool operator < (const Query &a, const Query &b)
{
return a.year < b.year;
}
};
struct StoreEvent
{
int year;
int idx;
int t;
friend bool operator < (const StoreEvent &a, const StoreEvent &b)
{
return a.year < b.year;
}
};
int a[MAXN];
int prev[MAXN];
int perm[MAXN];
int output[MAXN];
Store store[MAXN];
Query query[MAXN];
std::set <int> active[MAXN];
std::vector <StoreEvent> storeEvent;
MergeSortTree tree;
int searchLast(int value)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (store[mid].pos <= value) l = mid;
else r = mid;
}
return l;
}
int searchFirst(int value)
{
int l = 0, r = n + 1, mid;
while (l < r - 1)
{
mid = (l + r) / 2;
if (store[mid].pos < value) l = mid;
else r = mid;
}
return r;
}
void solve()
{
std::sort(store + 1, store + 1 + n);
for (int i = 1 ; i <= n ; ++i)
{
storeEvent.push_back({store[i].l, i, 0});
storeEvent.push_back({store[i].r + 1, i, 1});
}
for (int i = 1 ; i <= k ; ++i)
{
active[i].insert(-i);
active[i].insert(n + i);
}
for (int i = 1 ; i <= n ; ++i)
{
prev[i] = INF + i;
}
int ptr = -1;
tree.build(prev);
std::sort(query + 1, query + 1 + q);
std::sort(storeEvent.begin(), storeEvent.end());
for (int i = 1 ; i <= q ; ++i)
{
while (ptr + 1 < storeEvent.size() && storeEvent[ptr + 1].year <= query[i].year)
{
ptr++;
const auto &[year, idx, t] = storeEvent[ptr];
if (t == 0)
{
auto it = active[store[idx].type].upper_bound(idx);
int next = *it;
if (next <= n) tree.update(next, prev[next], idx);
prev[next] = idx;
it--;
tree.update(idx, prev[idx], *it);
prev[idx] = *it;
active[store[idx].type].insert(idx);
} else
{
auto it = active[store[idx].type].upper_bound(idx);
int currPrev = prev[idx];
int next = *it;
tree.update(idx, prev[idx], INF + idx);
prev[idx] = INF + idx;
if (next <= n) tree.update(next, prev[next], currPrev);
prev[next] = currPrev;
active[store[idx].type].erase(active[store[idx].type].find(idx));
}
}
if (tree.query(1, n) < k)
{
output[query[i].idx] = -1;
continue;
}
int pw = 0;
while ((1 << pw + 1) <= 1e8)
{
int ll = searchFirst(query[i].pos - (1 << pw + 1));
int rr = searchLast(query[i].pos + (1 << pw + 1));
if (ll > rr || tree.query(ll, rr) < k) pw++;
else break;
}
int l = (pw == 0 ? -1 : (1 << pw)), r = std::min((int)1e8, (1 << pw + 1)), mid;
while (l < r - 1)
{
mid = (l + r) / 2;
int ll = searchFirst(query[i].pos - mid);
int rr = searchLast(query[i].pos + mid);
if (ll > rr || tree.query(ll, rr) < k) l = mid;
else r = mid;
}
output[query[i].idx] = r;
}
}
void input()
{
std::cin >> n >> k >> q;
for (int i = 1 ; i <= n ; ++i)
{
std::cin >> store[i].pos >> store[i].type >> store[i].l >> store[i].r;
}
for (int i = 1 ; i <= q ; ++i)
{
std::cin >> query[i].pos >> query[i].year;
query[i].idx = i;
}
}
void print()
{
for (int i = 1 ; i <= q ; ++i)
{
std::cout << output[i] << '\n';
}
}
void fastIOI()
{
std::ios_base :: sync_with_stdio(0);
std::cout.tie(nullptr);
std::cin.tie(nullptr);
}
int main()
{
fastIOI();
input();
solve();
print();
return 0;
}
