---category_name: easyproblem_code: PROTEPOIproblem_name: 'Protecting The Poison'languages_supported:- ADA- ASM- BASH- BF- C- 'C99 strict'- CAML- CLOJ- CLPS- 'CPP 4.3.2'- 'CPP 4.9.2'- CPP14- CS2- D- ERL- FORT- FS- GO- HASK- ICK- ICON- JAVA- JS- 'LISP clisp'- 'LISP sbcl'- LUA- NEM- NICE- NODEJS- 'PAS fpc'- 'PAS gpc'- PERL- PERL6- PHP- PIKE- PRLG- PYPY- PYTH- 'PYTH 3.4'- RUBY- SCALA- 'SCM chicken'- 'SCM guile'- 'SCM qobi'- ST- TCL- TEXT- WSPCmax_timelimit: '3'source_sizelimit: '50000'problem_author: admin3problem_tester: kingofnumbersdate_added: 18-05-2017tags:- admin3- easy- geometry- greedy- snackdown- snckpa17- sortingeditorial_url: 'https://discuss.codechef.com/problems/PROTEPOI'time:view_start_date: 1495992600submit_start_date: 1495992600visible_start_date: 1495992600end_date: 1735669800current: 1497284129layout: problem---All submissions for this problem are available.### Read problems statements in [Mandarin Chinese](http://www.codechef.com/download/translated/SNCKPA17/mandarin/PROTEPOI.pdf), [Russian](http://www.codechef.com/download/translated/SNCKPA17/russian/PROTEPOI.pdf) and [Vietnamese](http://www.codechef.com/download/translated/SNCKPA17/vietnamese/PROTEPOI.pdf) as well.The kingdom of the snakes is an **N**x**N** grid. Their most-valued possession is a huge collection of poison, which is stored in the central **K**x**K** grid. It is guaranteed that both **N** and **K** are odd. What we mean by 'central' is this: suppose in the **N**x**N** grid, (i, j) refers to the cell in the i-th row and j-th column and (1,1) refers to the top-left corner and (N,N) refers to the bottom-right corner. Then the poison is stored in the **K**x**K** square whose top-left corner is **( (N - K)/2 + 1, (N - K)/2 + 1 )**.But there are thieves who want to steal the poison. They cannot enter the **N**x**N** 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 **K**x**K** grid, some of the poison will stick to the arrow, and if it exits the **N**x**N** 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 **N**x**N** 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 **K**x**K** grid), or it shouldn't ever enter the **K**x**K** 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 i-th of which contains four integers: **HXi, HYi, TXi, TYi**. (**HXi, HYi**) is the cell which contains the head of the i-th snake. (**TXi, TYi**) is the cell which contains the tail of the i-th 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 i-th 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** ≤ 109- 1 ≤ **K** ≤ **N**-2- Both **N** and **K** will be odd integers- 1 ≤ **M** ≤ 105- 1 ≤ **HXi, HYi, TXi, TYi** ≤ **N**- It is guaranteed that at least one of (**HXi = TXi**), and (**HYi = TYi**) will be true for all i- None of the cells in the **K**x**K** grid will be occupied by any snake### Example<pre><b>Input:</b>27 3 71 1 6 11 2 3 25 2 5 22 4 2 66 2 6 45 6 5 77 1 7 47 3 71 1 6 11 2 3 25 2 5 22 6 2 66 2 6 45 6 5 77 1 7 4<b>Output:</b>3-1</pre>### ExplanationThe first example corresponds to:Note that the top-left corner cell of the **N**x**N** 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.