Simple GUI Application

Time Limit : 1 sec, Memory Limit : 65536 KB

Problem C: Simple GUI Application

Advanced Creative Mobile 社(ACM社)では、新しいポータブルコンピュータに搭載するGUIアプリケーションの開発を行うことになった。

下図に示すように、GUIは1つのメインパネルを持ち、その上にいくつかのパネルが配置され、さらにそれらのパネルの上にもいくつかのパネルが配置されるような入れ子構造になっている。パネルはすべて辺が座標軸に平行・垂直な長方形または正方形である。



アプリケーションはパネルの入れ子構造をタグ構造で保持する仕様となっている。パネルを表すタグ構造は、タグ値とそのパネルの上に配置されているパネルのタグ構造のリストを持つ。タグ値はそのパネルの左上の座標 (x1, y1) と 右下の座標 (x2, y2) を示す。

タグ構造の構文規則を以下に示す。ここで、構文の記述に用いる記号の意味を、以下の表のように定める。"<"、">", "," 及び "/" は、字句要素である。


記号意味
::=定義する
{}* {} で囲まれた要素の 0 回以上の繰り返し

タグ構造 ::= 開始タグ タグ値 {タグ構造}* 終了タグ
開始タグ ::= <タグ名>
終了タグ ::= </タグ名>
タグ名   ::= 文字列
タグ値   ::= 整数,整数,整数,整数

タグ名はパネルの名前を示す1文字以上からなる文字列である。

タグ値は、カンマで区切られた4つの整数であり、それぞれパネルの座標を示す x1, y1, x2, y2 である。

例えば、上図に示したGUIは以下のタグ構造で記述される(スペースの関係上2行にまたがっているが、入力は1行で与えられる):

<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140
<text>90,30,170,80</text><button>130,110,170,130</button></primary></main>

このGUIでは、ユーザがある点をタッチすると、その点において最上部にあるパネルが選択される(境界線を含む)。

あなたの仕事は、メインパネルのタグ構造と、タッチされた点のリストを読み込み、以下の情報を出力するプログラムを作成することである。

  • 選択されたパネルの名前
  • そのパネルの直接上に配置されているパネルの数(以下"子の数"と呼ぶ)

なお、入力されるタグ構造について以下のことを仮定してよい。

  • タグ構造に文法エラーはない。
  • パネルがそれを含むパネル(以下"親パネル"と呼ぶ)からはみ出すことはなく、境界にも触れない。
  • 同じ親パネルを持つパネル同士は重ならず、触れない。
  • 同じ名前のパネルはない。

Input

入力は複数のデータセットからなる。各データセットは以下の形式で与えられる:

n
タグ構造
x1 y1
x2 y2
   .
   .
   .
xn yn

n はタッチされた点の数を示す整数である。タグ構造は空白を含まない1行の文字列である。xi, yii 番めにタッチされた点の x 座標と y 座標を表す(座標軸は上図に定めたものとする)。

n ≤ 100、タグ構造の文字列の長さ ≤ 1000 と仮定してよい。また、入力で与えられる x 座標 y 座標は 0 以上 10,000 以下と仮定してよい。

n が 0 のとき入力の終わりとする。

Output

各データセットに対して、選択された順番にパネルの名前と子の数を出力せよ。各名前と子の数を1つの空白で区切って1行に出力せよ。何も選択されない場合(タッチされた点にパネルがない場合)は、"OUT OF MAIN PANEL 1"と出力せよ。

Sample Input

5
<main>10,10,190,150<menu>20,20,70,140</menu><primary>80,20,180,140</primary></main>
10 10
15 15
40 60
2 3
130 80
0

Output for the Sample Input

main 2
main 2
menu 0
OUT OF MAIN PANEL 1
primary 0

Source: University of Aizu, ACM-ICPC Japan Domestic Contest 2009 Warm Up I , Aizu-Wakamatsu, Japan, 2009-05-16
Problem Setter:  Yutaka Watanobe