First, prepare the following two arrays:

• “the array of positions of columns with walls in the \(i\)-th row in ascending order” for each \(i = 1, 2, \ldots, H\);
• “the array of positions of rows with walls in the \(j\)-th column in ascending order” for each \(j = 1, 2, \ldots, W\);

Here, since \(H\) and \(W\) can be enormous, we cannot explicitly construct arrays \(A_i\) and \(B_i\) for all rows \(i\) and columns \(j\). Instead, we use an associative arrays to explicitly construct arrays \(A_i\) and \(B_j\) for all rows \(i\) and columns \(j\) with one or more walls.

For each instruction, Takahashi keeps moving until he moves \(l_i\) squares or he hits a wall or the edge of the grid. Therefore, in order to find the final position after an instruction, it is sufficient that we can obtain the nearest wall or grid edge in the direction of \(d_i\). This can be found by performing a binary search on an appropriate \(A_i\) or \(B_j\) in a total of \(\mathrm{O}(\log N)\) time.

For example, consider executing the instruction of moving left when the current position of Takahashi is \((R, C)\). The nearest position of wall (the index of column) in his direction is the maximum element in \(A_R\) less than \(C\). If there is no such element, we can see that there is no wall until reaching the edge of the grid in his current direction. Since \(A_R\) is sorted beforehand, we can find the maximum element less than \(C\) (or absence) by binary search.

Therefore, each instruction can be executed in an \(\mathrm{O}(\log N)\) time, so the entire instructions can be processed in a total of \(\mathrm{O}(Q \log N)\). Taking into account the time required to construct \(A_i\) and \(B_j\) (like sorting each element in ascending order of rows and columns), we can still assert that this problem can be solved in a total of \(\mathrm{O}((N+Q)\log N)\) time.

The following is a sample code in C++ language.

#include <iostream>
#include <map>
#include <vector>
#include <algorithm>
using namespace std;

int h, w, n, r, c, Q;
map<int, vector<int>> amp, bmp;

int main(void)
{
  cin >> h >> w >> r >> c >> n;
  for(int i = 1; i <= n; i++){
    int rr, cc;
    cin >> rr >> cc;
    amp[rr].push_back(cc), bmp[cc].push_back(rr);
  }
  for(auto &p : amp) sort(p.second.begin(), p.second.end());
  for(auto &p : bmp) sort(p.second.begin(), p.second.end());
  
  cin >> Q;
  char d; int l;
  for(int i = 1; i <= Q; i++){
    cin >> d >> l;
    if(d == 'L'){
      auto it = amp.find(r); int lb = 0;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      c = max(c-l, lb+1);
    }
    if(d == 'U'){
      auto it = bmp.find(c); int lb = 0;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = lower_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.begin()) it2--, lb = *it2;
      }
      r = max(r-l, lb+1);
    }
    if(d == 'R'){
      auto it = amp.find(r); int ub = w+1;
      if(it != amp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), c);
        if(it2 != vec.end()) ub = *it2;
      }
      c = min(c+l, ub-1);
    }
    if(d == 'D'){
      auto it = bmp.find(c); int ub = h+1;
      if(it != bmp.end()){
        vector<int> &vec = it->second;
        auto it2 = upper_bound(vec.begin(), vec.end(), r);
        if(it2 != vec.end()) ub = *it2;
      }
      r = min(r+l, ub-1);
    }
    cout << r << " " << c << "\n";
  }
  
  return 0;
}