input.txt

5 6 1 4
2 3
1 2
2 5
4 2
5 5
100 100 0 2
1 77
100 77
100 100 0 0
5 6 0 1
1 2
6 8 1 4
2 3
1 2
2 7
5 2
6 7
5 6 2 5
2 2
4 5
1 3
3 3
3 5
4 2
5 3