\(X=2 \times 10^5\) とおきます。

\(H \le W\) の場合が解ければ \(H > W\) の場合も解くことができます。以降 \(H \le W\) とします。

このとき、\(H \le \sqrt X\) が成り立ちます。

ここで、\(H\) 個の deque を持ちます。\(i\) 個目の deque には、\(a_{i,1},a_{i,2},\dots,a_{i,W}\) をこの順番で入れます。

1 p c のクエリが来た場合、\(p\) 個目の deque の末尾を \(S\) に加え削除し、\(p\) 個目の deque の先頭に c を挿入すればよいです。計算量は \(\mathrm{O}(1)\) です。

2 p c のクエリが来た場合、\(H\) 個目の deque の \(p\) 番目の要素を \(S\) に加え、\(i+1\) 個目の deque の \(p\) 番目の要素を \(i\) 個目の deque の \(p\) 番目の要素に変更し、\(1\) 個目の deque の \(p\) 個目の要素を c に変更すればよいです。計算量は \(\mathrm{O}(H)\) です。

よって、この問題を \(\mathrm{O}(Q\sqrt X)\) で解くことができます。