TopCoder

Thumb oreimo anime2 promo 06
yp155136
meruru~

User's AC Ratio

25.0% (3/12)

Submission's AC Ratio

5.4% (13/241)

Description

**測資有誤QQ (應該修正好了 2019/11/18)

某天眼皮醬跟起司豬在討論某種邪教咒語的規律
「聽起來好洗腦喔~」
「怎麼都在那幾個音跳來跳去~」
「你不要再放了,你每天放我都快要可以背起來了!」
「亞八里~亞八里~向姊轉轉~」
「這段咒語的結尾可以直接接到另外那段咒語的開頭耶!」
「不要跟著節奏轉肚皮啦!」
「轉~轉~轉~」
「是說既然可以咒語之間有連結關係,那我們可以把咒語接起來咯~」
「那我們可以把咒語接成多長啊?」

這時候問題就來了
給你一堆邪教咒語,還有之間的連接關係,問你可以把咒語接的多長(咒語可以重複使用)?
為了方便計算,我們把咒語切成許多等長的音

Input Format

每個檔案開頭有一個整數$T$,代表這個檔案接下來有幾筆測資
每筆測資開頭有兩個整數$N,M$,代表有$N$條咒語,咒語之間的關係有$M$個
接下來的一行有$N$個數字$a_{1}, a_{2}, a_{3}...a_{i}...a_{N}$,代表咒語i的長度
接下來$M$行,每行四個數字$s1,t1,s2,t2$,代表咒語$s1$第$t1$個音結束的瞬間可以直接接到$s2$第$t2$個音的前面

1 ≦ $T$ ≦ 10
1 ≦ $N$ ≦ 105
0 ≦ $M$ ≦ 5*105
1 ≦ $a_{i}$ ≦ 108
1 ≦ $s1,s2$ ≦ $N$
1 ≦ $t1$ ≦ $a_{s1}$
1 ≦ $t2$ ≦ $a_{s2}$

有30%的測資1 ≦ $N,M$ ≦ 103 且 1 ≦ $a_{i}$ ≦ 103
有60%的測資1 ≦ $N,M$ ≦ 104 且 1 ≦ $a_{i}$ ≦ 108

Output Format

對每筆測資請輸出重新組合後的咒語最多會有多少個音
如果長度是無限長的話,請輸出"LoveLive!"(不含引號)
每筆測資之間要換行

Sample Input

2
3 3
10 10 10
1 5 2 3
2 7 1 6
2 3 3 5
1 1
10
1 6 1 3

Sample Output

15
LoveLive!

Hints

Problem Source

2015建中校隊入隊考試-複試

Subtasks

No. Testdata Range Score
1 0 30
2 0~1 30
3 0~4 40

Testdata and Limits

No. Time Limit (ms) Memory Limit (KiB) Output Limit (KiB) Subtasks
0 2000 262144 262144 1 2 3
1 2000 262144 262144 2 3
2 5000 262144 262144 3
3 3000 262144 262144 3
4 2000 262144 262144 3