input

2 4 4
3
1 2 3
3
2 3 4

output

1

input

1 5 3
4 1 2 1 2

output

1