TopCoder

User's AC Ratio

80.0% (4/5)

Submission's AC Ratio

45.8% (11/24)

Description

大頭蕃最近出題目出得太過緩慢,以致於往往出題到半夜一兩點,隔天早上卻又得早起打桌球。
這天是閃光節,大頭蕃在時間0來到學校,由於實在是太累了,他非常想要找間空教室小睡一下。
可是他非常擔心該教室過不久會有人進去放閃光,房間太亮了會睡不着,所以他想要找一間不會被閃到、能夠睡最久的教室。
好在大頭蕃已經預先猜測到了什麼時候會有人在哪間教室放閃光,但是由於他已經累到沒辦法寫程式,只好請你大發慈悲幫個忙,對於大頭蕃想要找教室的時間點P,趕快告訴他夠睡最久的教室編號i,以及能夠睡多久(這樣他才能夠設定鬧鐘)。

此外,一到了時間T,就會有很兇的工友伯伯來鎖教室,在那之前必須趕快起床回家。

Input Format

輸入檔可能包含多筆測試資料,
每筆測試資料的第一列有兩個正整數N,T ,其中N代表教室間數,T代表鎖教室的時間。(1<=N<=100,000;1<=T<=109)
第二列有一個整數M(1<=M<=100,000),代表放閃光的預測表,接下來M列每列有三個整數i,Tai,Tbi(1<=i<=N,0<=Tai<Tbi<=T)代表每一個放閃光的行程(在教室i、從時間Ta到時間Tb)。
然後有個正整數Q(1<=Q<=100,000),代表大頭蕃想問的問題。接下來的Q列每列有一個整數t(0<=t<T)代表大頭蕃想詢問的時刻。

N=T=0時代表輸入結束。

Output Format

對於每個問題請輸出一列,包含兩個整數:能睡最久的教室編號i,以及能睡的時間長度。若同時有許多教室可以睡得最久,那麼大頭蕃會比較希望睡編號比較小的教室。
如果都沒有教室可以睡,請輸出"Oh, no!"(沒有雙引號)

Sample Input

3 5
4
1 1 4
2 3 5
3 0 2
3 1 4
3
0
3
4
0 0

Sample Output

2 3
Oh, no!
1 1

Hints

   0  1  2  3  4  5
--+|--|--|--|--|--|+
 1|   *xxxxxxxx*   |
 2|         *xxxxx*|
 3|*xx*XX*xxxxx*   |
--+----------------+

x代表教室亮度。

Problem Source

原TIOJ1223 / TIOJ 2008例行賽03-Elite (prob E)。Problem Setter:Tmt。

Subtasks

For Testdata: 0 ~ 0, Score: 25
For Testdata: 1 ~ 1, Score: 25
For Testdata: 2 ~ 2, Score: 25
For Testdata: 3 ~ 3, Score: 25
No. Time Limit (ms) Memory Limit (KiB)
0 5000 65536
1 5000 65536
2 5000 65536
3 5000 65536