24117번 - かくれんぼ (Hide-and-seek) 다국어

あなたは，JOI 社が発売したテレビゲームソフトを手に入れた．なかなか良くできたゲームであり，そ れなりに楽しみながら毎日プレイしていた．

ある日，ゲーマーの中で「かくれんぼ」と呼称されるステージが出現した．どうやらそのステージには バグがあり，優れたゲーマーでさえもほんのわずかな確率でしかクリアできない物であるらしい．

何度もそのステージに挑戦する中であなたは，とても高速な判断を行うことでクリアできる可能性が有 ることに気づき，プログラムを作成して対処出来るのではないかと考えた．

かくれんぼステージは，多数の障害物が配置された場所が舞台となっている．舞台は長方形で 1 × 1 の正 方形のマスに分かれており，各マスは 1 ≤ x ≤ 100, 000 ，1 ≤ y ≤ 1, 000, 000, 000 を満たす整数 x, y によっ て (x, y) と表現される．(1, 1) は左上隅のマスであり，(x + 1, y + 1) は (1, 1) から右に x，下に y 進んだマス を表現する．

各障害物は y 座標が同じ連続した w 個のマスに置かれる．つまり，障害物は w × 1 個のマスを占める長 方形の形に見える．その中の x 座標が一番小さいマスの座標 (x, y) と，長さ w の組で 1 つの障害物が表現 されている．障害物は 2 ≤ y のマスに配置される．障害物同士が重なることはない．

ステージが始まるとプレーヤーは舞台を動き回る．プレーヤーは障害物のあるマスを含めた任意のマス に移動できる．

一定の時間が経過すると敵が出現し攻撃を行う．プレーヤーはこの時必ず障害物の中に隠れる必要があ る．障害物の中に隠れるには，障害物のあるマスに居ればよい．適切な障害物の中に隠れることでプレー ヤーは攻撃を受けずに済み，敵に反撃するチャンスを得ることが出来る．チャンスを利用することでステー ジがクリアできる．

敵は M 種類の武器（例えば，拳銃，ライフル，無反動砲，電磁投射砲などなど）を所持している．武器 には 1 から M の固有の番号がつけられており，i 番の武器には攻撃力 a_i が設定されている．攻撃力は，そ の数値の分だけ障害物を破壊出来ることを表している．

破壊された障害物の中にプレーヤーが隠れている場合，プレーヤーはダメージを受けることになる．

敵はランダムに選ばれた x を使い，(x, 1) に出現し，下方向に向かってランダムに選択した武器を使い攻 撃する予定だった．ところが，ゲームのバグによって，敵は必ずプレーヤーのいる x 座標を選択し，プレー ヤーに向けて攻撃してしまう事となった．

あなたは自作のプログラムを使い，敵からどの武器を使って攻撃されても良いように，武器毎に攻撃を 受けずに済む最適な隠れ場所を探すことにした．攻撃を受けずに済む最適な隠れ場所は，プレーヤーが反 撃を行いやすいように，もっとも y 座標が小さい所である．また，そのような場所が複数存在する場合に は，その中でもっとも x 座標が小さい所が最適である．

障害物の情報と各武器の攻撃力が与えられたとき，敵が所持する武器毎に最適な隠れ場所を求めるプロ グラムを作成せよ．ただし，どのように隠れても攻撃を受けてしまう場合には，隠れる場所がないという 意味で (-1,-1) を出力せよ．

図 1: 攻撃力が 4 である武器に対応する隠れ方

標準入力から以下の入力を読み込め．

• 1 行目には整数 N と M が空白を区切りとして書かれている．
• 続く N 行のうち i 行目には整数 x_i，y_i，w_i が空白を区切りとして書かれている．
• 続く M 行のうち j 行目には整数 a_j が書かれている．

標準出力に以下のデータを出力せよ．

• データは M 行からなる．j 行目は 2 つの整数 xj と yj が空白区切りで書かれており，j 番目の武器に 対応する最適な隠れ場所の座標が (x_j, y_j) である事を表す．どのように隠れても j 番目の武器の攻撃 を受けてしまう場合は x_j = y_j = −1 とせよ．

• 1 ≤ N ≤ 50, 000 障害物の数
• 1 ≤ M ≤ 50, 000 武器の種類
• 1 ≤ x_i ≤ 100, 000 障害物 i が配置されるマスの中でもっとも小さい x 座標
• 2 ≤ y_i ≤ 1, 000, 000, 000 障害物 i の y 座標
• 1 ≤ w_i + x_i − 1 ≤ 100, 000 w_i は障害物 i の長さ
• 1 ≤ a_j ≤ N 武器 j の攻撃力