G. Language
time limit per test
4 seconds
memory limit per test
524 megabytes
input
standard input
output
standard output
Examples
Input
3 6 1 0
2
0 1 0
0 1 1
1 2 0
1 2 1
2 0 0
2 0 1
5 10 2 0
2 4
0 1 0
1 2 0
1 2 1
2 0 0
2 0 1
0 3 1
3 4 0
3 4 1
4 0 0
4 0 1
Output
YES
Input
2 4 1 0
0
0 0 0
0 1 1
1 1 0
1 1 1
4 8 1 0
2
0 1 1
1 1 0
1 1 1
0 2 0
2 2 0
2 3 1
3 3 0
3 3 1
Output
NO