好きな人のことをよく知りたいと思うのは当然のことだ。そう言いながら彼女は、彼の住所氏名年齢電話番号から、出身地病歴支持政党寝るときの姿勢に至るまで、ありとあらゆる個人情報を調べ上げた。彼女の辞書にプライバシーという言葉はない。彼女のような人を専門用語でストーカーとかヤンデレとか呼んだりするらしいが、そんなことも彼女にとってはどうでもいいことなのだった。
彼のことをもっとよく知るために、彼女は彼のパソコンにスパイウェアを仕掛けた。このスパイウェアは、彼がブラウザでWebページを閲覧している間、彼のマウス操作を記録するのだ。彼女はしばらくの間このスパイウェアを彼に使わせ、そして操作の記録を極秘裏のうちに回収することに成功した。
さて、この操作の記録から、彼がどのWebページを見ていたかを復元するプログラムを作成して欲しい。
全てのページは H * W の大きさであり、左上の座標が (0, 0), 右下の座標が (W, H) となっている。ページはいくつかの (軸に平行な) 長方形のボタンを含む。これらのボタンはリンクになっていて、これらの内側がクリックされたとき、そのボタンに対応するページへと遷移する。
彼が使うブラウザは、以下のようにして閲覧履歴や表示するページを管理する。
ブラウザは、複数のページを格納できる十分に長い1次元配列状のバッファと、そのバッファ内の1つのページを指すポインタを持つ。このポインタが指しているページが、常にユーザに表示される。最初、このバッファにはあらかじめ定められた1つのページのみが格納され、ポインタはそのページを指す。 リンクボタンがクリックされると、現在ポインタが指しているページよりも右側のページは全て削除される。その後で、リンクボタンが指す先のページがバッファの右端に追加され、ポインタは右に一つ移動する。結果として、ユーザはリンクボタンが指す先のページを見ることになる。
ブラウザは特殊なボタンとして、「前のページに戻る」「次のページに進む」の2つのボタンを持つ。「前のページに戻る」ボタンを押すとポインタは左に一つ移動し、「次のページへ進む」ボタンを押すとポインタは右に一つ移動する。どちらの場合も、バッファにそのようなページが格納されていなかった場合は何も起きない。
彼女が回収した彼のブラウザの操作の記録は、以下のような命令からなる。
click x y
座標 (x, y) をクリックしたことを表す。もしクリックした場所にボタンがあれば (ボタンの左端・右端の x 座標をそれぞれx1, x2 として x1 <= x <= x2 であり、かつボタンの上端・下端の y 座標をそれぞれy1, y2 として y1 <= y <= y2 であれば)、そのボタンが押されたものとみなされる。
back
「前のページに戻る」ボタンを押したことを表す。
forward
「次のページに進む」ボタンを押したことを表す。
この他に、特別な命令 show が与えられる。あなたのプログラムは、この命令が与えられる度に、現在のページの名前を出力しなければならない。
ところで、他人のパソコンにスパイウェアを仕掛けることは法に抵触する恐れがあります。偉い人にすっごく怒られるので、真似しないでください。
各データセットの最初の行は整数 n のみからなり、そのデータセット内に現れるページの数を表す。 次の行には整数 W, H が与えられる。
続いてページの情報が n 回与えられる。各ページの情報の最初の行には、ページ名を表す文字列と、そのページに含まれるボタンの数 b[i] が与えられる。続く b[i] 行にはボタンの情報が与えられる。各ボタンの情報は4つの整数と1つの文字列から成り、それぞれボタンの左上の角の x座標・y座標、 右下の角の x座標・y座標、そしてリンク先のページ名を表す。
その次には記録された操作の数 m が与えられる。続く m 行には操作の記録が与えられる。これらのフォーマットは問題文を参照せよ。
１つ目に与えられるページが、最初にバッファに格納されているものとする。
n = 0のとき、入力は終了する。それぞれのデータセットに対して、show 命令が与えられる度に、その時のページ名を1行に出力せよ。
3 800 600 index 1 500 100 700 200 profile profile 2 100 100 400 200 index 100 400 400 500 link link 1 100 100 300 200 index 9 click 600 150 show click 200 450 show back back show forward show 0
profile link index profile