Protecting The Poison

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
The kingdom of the snakes is an NxN grid. Their mostvalued possession is a huge collection of poison, which is stored in the central KxK grid. It is guaranteed that both N and K are odd. What we mean by 'central' is this: suppose in the NxN grid, (i, j) refers to the cell in the ith row and jth column and (1,1) refers to the topleft corner and (N,N) refers to the bottomright corner. Then the poison is stored in the KxK square whose topleft corner is ( (N  K)/2 + 1, (N  K)/2 + 1 ).
But there are thieves who want to steal the poison. They cannot enter the NxN grid, but they can shoot arrows from outside. These arrows travel across a row (from left to right, or right to left), or across a column (top to bottom or bottom to top) in a straight line. If the arrow enters the KxK grid, some of the poison will stick to the arrow, and if it exits the NxN grid after that, the thieves will have successfully stolen some of the poison.
As the King of the snakes, you want to thwart these attempts. You know that the arrows will break and stop if they hit a snake's scaly skin, but won't hurt the snakes. There are some snakes already guarding the poison. Each snake occupies some consecutive cells in a straight line inside the NxN grid. That is, they are either part of a row, or part of a column. Note that there can be intersections between the snakes. A configuration of snakes is 'safe', if the thieves cannot steal poison. That is, no matter which row or column they shoot arrows from, either the arrow should hit a snake and stop (this can happen even after it has entered and exited the KxK grid), or it shouldn't ever enter the KxK grid.
The King has other duties for the snakes, and hence wants to remove as many snakes as possible from this configuration, such that the remaining configuration is still 'safe'. Help him find the minimum number of snakes he needs to leave behind to protect the poison.
Input
 The first line contains a single integer, T, the number of testcases.
 The first line of each testcase contains three integers: N, K and M, where N is the size of the entire square grid, K is the size of the square containing the poison, and M is the number of initial snakes.
 M lines follow, the ith of which contains four integers: HX_{i}, HY_{i}, TX_{i}, TY_{i}. (HX_{i}, HY_{i}) is the cell which contains the head of the ith snake. (TX_{i}, TY_{i}) is the cell which contains the tail of the ith snake. It is guaranteed that both these cells will either lie in the same row, or same column. And hence the cells in between them, including these two cells, represents the ith snake.
Output
 For each testcase, output a single integer in a new line: The minimum number of the snakes that the king can keep and still protect the poison. If it is not possible to protect the poison even with all the snakes, output 1.
Constraints
 1 ≤ T ≤ 4
 3 ≤ N ≤ 10^{9}
 1 ≤ K ≤ N2
 Both N and K will be odd integers
 1 ≤ M ≤ 10^{5}
 1 ≤ HX_{i}, HY_{i}, TX_{i}, TY_{i} ≤ N
 It is guaranteed that at least one of (HX_{i} = TX_{i}), and (HY_{i} = TY_{i}) will be true for all i
 None of the cells in the KxK grid will be occupied by any snake
Example
Input: 2 7 3 7 1 1 6 1 1 2 3 2 5 2 5 2 2 4 2 6 6 2 6 4 5 6 5 7 7 1 7 4 7 3 7 1 1 6 1 1 2 3 2 5 2 5 2 2 6 2 6 6 2 6 4 5 6 5 7 7 1 7 4 Output: 3 1
Explanation
The first example corresponds to:
Note that the topleft corner cell of the NxN grid is by definition, (1,1). The inner square contains the poison, and the seven snakes are shown in different colours. The green snake is the 1st snake in the input.
We can remove all but 3 snakes and protect the poison. One such configuration is this:
You can check that no arrow can enter the inner poison square and exit the outer square without hitting a snake. Hence is it safe. Also, you cannot do this with fewer snakes. Hence 3 is the answer.
The second testcase corresponds to:
You can check that even with all the snakes, this is not a safe configuration, because the thieves can shoot an arrow down the 5th column, and they can steal poison. Hence, the answer is 1.
Author:  admin3 
Tester:  kingofnumbers 
Editorial  https://discuss.codechef.com/problems/PROTEPOI 
Tags  admin3, easymedium, geometry, greedy, snackdown, snckpa17, sorting 
Date Added:  18052017 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 