1216 . 好想睡覺 之 好累的大頭蕃
TopCoder
Tags
Description
大頭蕃最近出題目出得太過緩慢，以致於往往出題到半夜一兩點，隔天早上卻又得早起打桌球。
這天是閃光節，大頭蕃在時間0來到學校，由於實在是太累了，他非常想要找間空教室小睡一下。
可是他非常擔心該教室過不久會有人進去放閃光，房間太亮了會睡不着，所以他想要找一間不會被閃到、能夠睡最久的教室。
好在大頭蕃已經預先猜測到了什麼時候會有人在哪間教室放閃光，但是由於他已經累到沒辦法寫程式，只好請你大發慈悲幫個忙，對於大頭蕃想要找教室的時間點P，趕快告訴他夠睡最久的教室編號i，以及能夠睡多久(這樣他才能夠設定鬧鐘)。
此外，一到了時間T，就會有很兇的工友伯伯來鎖教室，在那之前必須趕快起床回家。
Input Format
輸入檔可能包含多筆測試資料，
每筆測試資料的第一列有兩個正整數N,T ，其中N代表教室間數，T代表鎖教室的時間。(1<=N<=100；1<=T<=10,000)
第二列有一個整數M(1<=M<=100,000)，代表放閃光的預測表，接下來M列每列有三個整數i,Tai,Tbi(1<=i<=N,0<=Tai<Tbi<=T)代表每一個放閃光的行程(在教室i、從時間Ta到時間Tb)。
然後有個正整數Q(1<=Q<=10,000)，代表大頭蕃想問的問題。接下來的Q列每列有一個整數t(0<=t<T)代表大頭蕃想詢問的時刻。
N=T=0時代表輸入結束。
Output Format
對於每個問題請輸出一列，包含兩個整數：能睡最久的教室編號i，以及能睡的時間長度。若同時有許多教室可以睡得最久，那麼大頭蕃會比較希望睡編號比較小的教室。
如果都沒有教室可以睡，請輸出"Oh, no!"(沒有雙引號)
Sample Input 1
3 5
4
1 1 4
2 3 5
3 0 2
3 1 4
3
0
3
4
0 0
4
1 1 4
2 3 5
3 0 2
3 1 4
3
0
3
4
0 0
Sample Output 1
2 3
Oh, no!
1 1
Oh, no!
1 1
Hints
0 1 2 3 4 5 --+|--|--|--|--|--|+ 1| *xxxxxxxx* | 2| *xxxxx*| 3|*xx*XX*xxxxx* | --+----------------+
x代表教室亮度。
Problem Source
原TIOJ1216 / TIOJ 2008例行賽03 (prob H)。Problem Setter：Tmt。
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |