TopCoder

User's AC Ratio

100.0% (14/14)

Submission's AC Ratio

58.7% (27/46)

Description

2011年諾貝爾誤理學獎頒給了熱狗神阿思,原因是他製造出一種不穩定的分子。

這種分子只要兩兩碰在一起就會完全轉換成能量,
而產生的能量遠超過E = mc2所得出來的結果,而是E = Kmc2,K被稱為阿思常數。

而這種分子相當不穩定,存在的時間相當短,因此阿思將它命名為 人造暫時存在分子
(Artificial Temporarily Presence Molecule),簡稱ATP分子。

阿思得到誤理學獎後,掀起了研究這種分子的風潮,就連阿思自己的物理實驗室裡頭的研究生也逃不了。
阿思的學生設計了一個實驗,將這些分子放在編號 0 ~ N 的特殊容器裡排成一排,
然後讓某一段的分子融合產生湮滅現象來產生能量,藉由計算能量差來驗證阿思常數的精確數值。
可是儀器本身有點瑕疵,一開始並不會將所有容器都放入1個分子,有些會沒有放到,或是同時放了2個於是就湮滅消失。

所幸每一次實驗,儀器會重複犯錯,也就是說先前放入2個分子的容器,下一次也一樣會
放入2個,因此每一次實驗開始前的分子分布狀態會一模一樣,且每次實驗前儀器都會清
空,所以你可以確定上一次實驗的分子不會影響這次實驗。

而學生會把某一段分子湮滅後所剩餘的分子個數記錄下來,而阿思打算用這些數據寫成論文,
但是他為了檢查學生有沒有偽造部分數據,打算寫個程式檢查。

但是他還有其他事要忙,於是身為偉大的阿思神學弟,你自告奮勇的要來解決這個問題。

如果數據有偽造的現象,請輸出第一次偽造是第幾次實驗。

Input Format

單一檔案內包含多組數據,對於每組數據:

第一行包含兩個數字,N, M,表示有N個容器,且實驗進行了M次。
接下來有M行,每行含三個數字L, R, C,表示學生在這次實驗中,將L到R之間的容器合併,產生湮滅現象後,剩下C個分子。
如果N = M = 0代表檔案結束,請不要對這行進行任何輸出。

Output Format

對每組數據輸出單一一行含一個數字,表示數據第一次偽造是在第幾次實驗。
如果數據都正常,請輸出"He didn't lie."(不含雙引號)

Sample Input

2 3
1 1 1
2 2 1
1 2 1
2 3
1 1 1
2 2 1
1 2 0
10 5
1 2 0
3 4 1
5 6 0
1 6 0
7 10 1
0 0

Sample Output

3
He didn't lie.
4

Hints

對於100%的測試資料,單檔不會超過50組數據。

對於40%的測試資料,N <= 15
對於70%的測試資料,N <= 100,000
對於100%的測試資料,N <= 1,000,000,000

對於10%的測試資料,M = 0
對於30%的測試資料,M <= 15
對於100%的測試資料,M <= 10,000

並不保證L < R

Problem Source

原TIOJ1672 / 建國中學99年校內培訓contest #2 prob 4
problem setter:ATP
source:vijos

Subtasks

For Testdata: 0 ~ 0, Score: 10
For Testdata: 1 ~ 1, Score: 10
For Testdata: 2 ~ 2, Score: 10
For Testdata: 3 ~ 3, Score: 10
For Testdata: 4 ~ 4, Score: 10
For Testdata: 5 ~ 5, Score: 10
For Testdata: 6 ~ 6, Score: 10
For Testdata: 7 ~ 7, Score: 10
For Testdata: 8 ~ 8, Score: 10
For Testdata: 9 ~ 9, Score: 10
No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB)
0 5000 65536 262144
1 5000 65536 262144
2 5000 65536 262144
3 5000 65536 262144
4 5000 65536 262144
5 5000 65536 262144
6 5000 65536 262144
7 5000 65536 262144
8 5000 65536 262144
9 5000 65536 262144