Description

Format

Input

Output

Samples

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

4
0
25

Limitation

n, Q <= 100,000.