以下，文字定義などは公式解説に従うものとします．

本問題は，実装量が多くなりがちで大変です．ここでは，実装の際に手間を少し減らせる方法を紹介します．

公式解説にもあるように，壁にぶつかる座標を求める際には，\(A_i\) や \(B_j\) に対して二分探索を用います．二分探索をするライブラリとしては，例えばC++だと lower_bound などがありますが，そのようなライブラリを用いて今回の問題のような実装を行うと，範囲の端の要素にアクセスした場合などに範囲外参照を起こす可能性があります．それを除外するためには， グリッドの端に到着した場合は別途場合分けを行う必要があるのですが，実装がやや面倒であり，混乱しやすいです．

そこで，\(A_i\) や \(B_j\) に次のような小細工を入れることにしましょう．

• 陽に持っている配列 \(A_i\) すべてに対して，列番号として \(0\) と \(W+1\) を追加する．
• 陽に持っている配列 \(B_j\) すべてに対して，行番号として \(0\) と \(H+1\) を追加する．

この処理を行うことによって，グリッドの端の処理を壁の処理と全く同じように行うことができ，実装の場合分けを減らすことができるため，楽に書けることもあります．

なお，このように，配列の端に値を追加することで実装を楽にする手法は，しばしば番兵と呼ばれます．

この方法で，最悪計算量のオーダーは変わりませんが，配列に追加した要素の数が多くなったぶん，定数倍が悪くなっていることには注意してください．

実装例（C++）