3211 - 花神游历各国

Input

Output

每次x=1时，每行一个整数，表示这次旅行的开心度

Examples

Input

4

1 100 5 5

5

1 1 2

2 1 2

1 1 2

2 2 3

1 1 4

Output

101

11

11

Hint

对于100%的数据， n ≤ 100000，m≤200000 ,data[i]非负且小于10^9

Time Limit 1 second
Memory Limit 128 MB
Stats
上一题 下一题