Input

4 4 5
1 1 1 1
1 2
2 4
1 4
2 3
D 4
C 3 5
C 1 4
D 2
D 1

Output

3
5
6
6
5

Nguồn: LMH'1920