func_code_string: #include <bits/stdc++.h>   using namespace std;   long long rdtsc() {     long long tmp;     asm( rdtsc  :  =A (tmp));     return tmp;   }   inline int myrand() { return abs((rand() << 15) ^ rand()); }   inline int rnd(int x) { return myrand() % x; }   const long long INF = (long long)1e16 + 1;   const long double EPS = 1e-9;   struct SegmTree {     const static int maxn = (1 << 17);     int a[maxn * 2];     int n;     void build(int _n) {       for (n = 1; n < _n; n <<= 1)         ;       assert(n <= maxn);       for (int i = 1; i < 2 * n; ++i) a[i] = -1;     }     int get(int v) {       int res = -1;       for (v += n; v > 0; v >>= 1)         if (a[v] != -1) res = a[v];       return res;     }     void make(int v, int l, int r, int l0, int r0, int nval) {       if (l >= r0 || l0 >= r) return;       if (l0 <= l && r <= r0) {         a[v] = nval;         return;       }       if (a[v] != -1) a[2 * v] = a[2 * v + 1] = a[v], a[v] = -1;       int m = (l + r) / 2;       make(2 * v, l, m, l0, r0, nval);       make(2 * v + 1, m, r, l0, r0, nval);     }     void make(int l, int r, int nval) { make(1, 0, n, l, r, nval); }   } tree;   const int maxn = (int)1e5 + 10 + 1;   struct Vertex {     int x, y;     int g;     Vertex() {}     Vertex(int _x, int _y, int _g) : x(_x), y(_y), g(_g) {}   };   const int maxg = 4;   const int go[maxg + 1][2] = {{1, 0}, {0, 1}, {-1, 0}, {0, -1}, {0, 0}};   const char chgo[maxg] = { R ,  U ,  L ,  D };   int dir[maxn][2][2];   int dirg[maxn];   struct Event {     int type;     int x;     int l, r;     int id;     Event() {}     Event(int _type, int _x, int _y, int _id)         : type(_type), x(_x), l(_y), r(-1), id(_id) {       assert(type == 1);     }     Event(int _type, int _x, int _l, int _r, int _id)         : type(_type), x(_x), l(_l), r(_r), id(_id) {       assert(type == 2);     }     inline bool operator<(const Event &e) const {       if (x != e.x) return x < e.x;       return type > e.type;     }   };   Event evs[3 * maxn];   int n, b;   void rotate(int &x, int &y) {     int nx = b - y, ny = x;     x = nx, y = ny;   }   int gov[maxn * 2];   void fillGo(int cnt, Vertex *vs) {     for (int rot = 0; rot < maxg; ++rot) {       int m = 0;       for (int i = 0; i < cnt; ++i) {         if (vs[i].g != 2) continue;         evs[m++] = Event(1, vs[i].x, vs[i].y, i);       }       for (int i = 0; i < n; ++i) {         if (dir[i][0][0] == dir[i][1][0]) {           int l = dir[i][0][1], r = dir[i][1][1];           if (l > r) swap(l, r);           evs[m++] = Event(2, dir[i][0][0], l, r, i);         } else {           assert(dir[i][0][1] == dir[i][1][1]);           int x =               (dir[i][0][0] < dir[i][1][0]) ? dir[i][0][0] : (dir[i][1][0] + 1);           evs[m++] = Event(2, x, dir[i][0][1], dir[i][1][1], i);         }       }       sort(evs, evs + m);       tree.build(b + 1);       for (int i = 0; i < m; ++i) {         if (evs[i].type == 1) {           gov[evs[i].id] = tree.get(evs[i].l);         } else {           assert(evs[i].type == 2);           tree.make(evs[i].l, evs[i].r + 1, evs[i].id);         }       }       for (int i = 0; i < cnt; ++i) {         rotate(vs[i].x, vs[i].y);         vs[i].g += 1;         if (vs[i].g == 4) vs[i].g = 0;       }       for (int i = 0; i < n; ++i) {         for (int j = 0; j < 2; ++j) {           rotate(dir[i][j][0], dir[i][j][1]);         }       }     }   }   Vertex vs[maxn * 2 * 2];   int start[maxn][2];   int startDir[maxn];   long long startTime[maxn];   int mynext[maxn * 4];   int price[maxn * 4];   const int maxl = 50;   int pr[maxl][maxn * 4];   long long cs[maxl][maxn * 4];   int sign(int x) {     if (x < 0) return -1;     return !!x;   }   bool solve() {     if (scanf( %d%d , &n, &b) < 2) return 0;     int cnt = 0;     for (int i = 0; i < n; ++i) {       for (int j = 0; j < 2; ++j)         for (int k = 0; k < 2; ++k) scanf( %d , &dir[i][j][k]);       int dx = dir[i][1][0] - dir[i][0][0], dy = dir[i][1][1] - dir[i][0][1];       if (dx == 0) {         assert(dy != 0);         dy /= abs(dy);       } else {         assert(dy == 0);         dx /= abs(dx);       }       dirg[i] = -1;       for (int g = 0; g < maxg; ++g) {         if (go[g][0] == dx && go[g][1] == dy) dirg[i] = g;       }       assert(dirg[i] != -1);       vs[cnt++] = Vertex(dir[i][1][0], dir[i][1][1], dirg[i]);     }     int q;     scanf( %d , &q);     for (int iter = 0; iter < q; ++iter) {       char ch;       scanf(            %d%d %c             %lld ,           &start[iter][0], &start[iter][1], &ch, &startTime[iter]);       startDir[iter] = find(chgo, chgo + maxg, ch) - chgo;       assert(startDir[iter] != maxg);       vs[cnt++] = Vertex(start[iter][0], start[iter][1], startDir[iter]);     }     fillGo(cnt, vs);     int rcnt = cnt;     for (int i = 0; i < cnt; ++i) {       if (gov[i] == -1) {         mynext[i] = rcnt;         if (vs[i].g == 0) {           price[i] = b - vs[i].x;         } else {           if (vs[i].g == 1)             price[i] = b - vs[i].y;           else {             if (vs[i].g == 2)               price[i] = vs[i].x;             else {               assert(vs[i].g == 3);               price[i] = vs[i].y;             }           }         }         vs[rcnt] = Vertex(vs[i].x + go[vs[i].g][0] * price[i],                           vs[i].y + go[vs[i].g][1] * price[i], 4);         mynext[rcnt] = rcnt;         price[rcnt] = 1;         ++rcnt;         continue;       }       int crash = gov[i];       mynext[i] = crash;       price[i] = abs(vs[crash].x - vs[i].x) + abs(vs[crash].y - vs[i].y);     }     for (int i = 0; i < rcnt; ++i) {       pr[0][i] = mynext[i], cs[0][i] = price[i];     }     for (int it = 1; it < maxl; ++it) {       for (int v = 0; v < rcnt; ++v) {         pr[it][v] = pr[it - 1][pr[it - 1][v]];         cs[it][v] = cs[it - 1][v] + cs[it - 1][pr[it - 1][v]];         cs[it][v] = min(cs[it][v], INF);       }     }     for (int iter = 0; iter < q; ++iter) {       int v = iter + n;       long long left = startTime[iter];       for (int it = maxl - 1; it >= 0; --it) {         if (left >= cs[it][v]) {           left -= cs[it][v];           v = pr[it][v];         }       }       {         assert(left <= 3 * b + 5);         int x = vs[v].x, y = vs[v].y;         int nx = vs[pr[0][v]].x, ny = vs[pr[0][v]].y;         if (x != nx && y != ny) {           int dist1 = (vs[v].g & 1) ? (ny - y) : (nx - x);           x += go[vs[v].g][0] * min((int)left, abs(dist1));           y += go[vs[v].g][1] * min((int)left, abs(dist1));           left -= min((int)left, abs(dist1));         }         if (left > 0) {           if (nx != x) x += sign(nx - x) * (int)left;           if (ny != y) y += sign(ny - y) * (int)left;         }         printf( %d %d n , x, y);       }     }     return 1;   }   int main() {     srand(rdtsc());     while (1) {       if (!solve()) break;     }     return 0;   }   