Description

Format

Input

Output

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

Sample 1

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

Limitation

1s, 128MiB for each test case.

Source

bzoj3211