Description

Format

Input

Output

Samples

3 2 0
2 1 2
1 1
1 3

0
3

Hint

M,N<=3*10^5,Ai<=10^9