Поезд пассаЖирный

#include <iostream>
#include <cstdio>
#include <map>
#include <cassert>
#include <algorithm>
#include <deque>

using namespace std;

typedef struct stree* pSTree;

struct stree
{
    long long x;
    pSTree L, R;
    stree(int _x)
    {
        x = _x;
        L = nullptr;
        R = nullptr;
    }
    stree(pSTree p)
    {
        x = p->x;
        L = p->L;
        R = p->R;
    }
};

pSTree build(int L, int R)
{
    pSTree v = new stree(0);
    if (L == R - 1)
        return v;
    int mid = (L + R) / 2;
    v->L = build(L, mid);
    v->R = build(mid, R);
    return v;
}

int get_x(pSTree v)
{
    if (v)
        return v->x;
    return -1;
}

pSTree update(pSTree v, int L, int R, int x, long long y)
{
    if (L > x || R <= x)
        return v;
    else if (L == R - 1)
        return new stree(y);
    int mid = (L + R) / 2;
    pSTree new_v = new stree(v);
    new_v->L = update(new_v->L, L, mid, x, y);
    new_v->R = update(new_v->R, mid, R, x, y);
    new_v->x = max(get_x(new_v->L), get_x(new_v->R));
    return new_v;
}

long long get_minimal(pSTree v, int L, int R, long long b)
{
    if (get_x(v) < b)
        return -1;
    if (L == R - 1)
        return L;
    int mid = (L + R) / 2;
    if (get_x(v->L) >= b)
        return get_minimal(v->L, L, mid, b);
    else
        return get_minimal(v->R, mid, R, b);
}

struct ticket
{
    int c; long long a, b;
    ticket(int _c, int _a, int _b)
    {
        c = _c; a = _a; b = _b;
    }
    bool operator<(const ticket& other) const
    {
        if (a != other.a)
            return a < other.a;
        if (b != other.b)
            return b < other.b;
        return c < other.c;
    }
    ticket() {}
};

struct event
{
    long long time; int c; int type;
    event(int _time, int _c, int _type)
    {
        time = _time;
        c = _c;
        type = _type;
    }
    bool operator<(const event& other) const
    {
        if (time != other.time)
            return time < other.time;
        return type < other.type;
    }
};

void print(pSTree v, int L, int R)
{
    if (L == R - 1)
        cout << v->x << " ";
    else
    {
        int mid = (L + R) / 2;
        print(v->L, L, mid);
        print(v->R, mid, R);
    }
}

int main()
{
    int n, s, m;
    cin >> n >> s >> m;
    pSTree segment_tree = build(0, s);
    vector<event> events;
    vector<deque<ticket> > deques(s);
    vector<ticket> tickets;
    for (int i = 0; i < m; i++)
    {
        int c; long long a, b;
        cin >> c >> a >> b;
        c--; //b--;
        events.push_back(event(a, c, 1));
        events.push_back(event(b, c, -1));
        tickets.push_back(ticket(c, a, b));
    }
    sort(events.begin(), events.end());
    sort(tickets.begin(), tickets.end());
    for (int i = 0; i < m; i++)
        deques[tickets[i].c].push_back(tickets[i]);
    for (int i = 0; i < s; i++)
    {
        deques[i].push_back(ticket(i, 1791791791, 1791791792));
        segment_tree = update(segment_tree, 0, s, i, deques[i].front().a);
    }
    map<int, pSTree> strees;
    strees[0] = segment_tree;
    if (m)
    {
        int lst = events[0].time;
        for (int i = 0; i < 2 * m; i++)
        {
            if (events[i].time != lst)
                strees[lst] = segment_tree;
            if (events[i].type == 1)
            {
                segment_tree = update(segment_tree, 0, s, events[i].c, -1);
                deques[events[i].c].pop_front();
            }
            else
                segment_tree = update(segment_tree, 0, s, events[i].c, deques[events[i].c].front().a);
            lst = events[i].time;
        }
        strees[lst] = segment_tree;
    }
    else
        strees[0] = segment_tree;
    strees[1791791791] = segment_tree;
    long long p = 0;
    int q;
    cin >> q;
    for (int i = 0; i < q; i++)
    {
        long long x, y;
        cin >> x >> y;
        x += p; y += p;
        if (x < 1 || y > n)
            p = 0;
        else
        {
            auto it = strees.upper_bound(x);
            it--;
            pSTree needed = it->second;
            p = get_minimal(needed, 0, s, y) + 1;
        }
        cout << p << endl;
    }
    return 0;
}