K. Tarot reading
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output
Example
Input
8 17 5
1 2 39 39
2 4 32 32
3 6 35 35
4 8 7 25
4 2 6 25
4 6 9 25
4 7 3 25
5 5 30 30
6 3 3 16
6 5 2 16
6 4 3 16
6 7 2 16
6 1 6 16
7 6 15 25
7 8 10 25
8 4 5 8
8 3 3 8
8 7 3
1 5 2
8 6 3
3 2 3
3 1 3
Output
1
1
1
1
1