{"trustable":false,"sections":[{"title":"","value":{"format":"HTML","content":"\u003cdiv\u003e\r\n\t\u003cp\u003e\r\n\t\t\u003cimg align\u003d\"left\" height\u003d\"198\" src\u003d\"http://acmicpc-live-archive.uva.es/nuevoportal/data/p5000.jpg\" width\u003d\"323\" /\u003e\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tKing\u003cem\u003eMotashota\u003c/em\u003e\u003cem\u003e \u003c/em\u003eis in a war against the mighty \u003cem\u003eBachchaloks\u003c/em\u003e. He has formed a well-trained army of snipers, and planning to use them as much as possible. In one of the missions, he has \u003cstrong\u003e\u003cem\u003eS \u003c/em\u003e\u003c/strong\u003esnipers. They will be dispatched to get rid of the soldiers guarding the bank of the river \u0026#39;\u003cem\u003eNodi\u003c/em\u003e\u0026#39;.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tFrom satellite images, \u003cem\u003eMotashota \u003c/em\u003ehas located positions of all enemy soldiers. Now, the plan is, snipers will take their positions. They are excellent swimmers, so, you can assume that they won\u0026#39;t get caught, while taking position. Upon order from \u003cem\u003eMotashota\u003c/em\u003e, they will start shooting enemy soldiers. A sniper can shoot a soldier, if euclidean distance between the soldier and sniper is no more than \u003cstrong\u003e\u003cem\u003eD\u003c/em\u003e\u003c/strong\u003e. After the snipers get rid of all the soldiers, they can proceed with the operation. So, it is important for them to position the snipers in such a way that, all soldiers are within the range of at least one sniper.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tIn addition, when snipers start shooting, the guards will be alert, and thus, snipers can\u0026#39;t change their position, they can only continue shooting from their position.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tThe river bank is defined by the horizontal line \u003cstrong\u003e\u003cem\u003ey \u003d k\u003c/em\u003e\u003c/strong\u003e. All points \u003cem\u003e(x,y)\u003c/em\u003e where \u003cem\u003ey\u0026gt;k\u003c/em\u003e is in the enemy territory, and if \u003cem\u003ey\u0026lt;k\u003c/em\u003e, then it\u0026#39;s on the water. You will be given location of \u003cstrong\u003e\u003cem\u003eN\u003c/em\u003e\u003c/strong\u003e soldiers, strictly in the enemy territory, you have to place \u003cstrong\u003e\u003cem\u003eS \u003c/em\u003e\u003c/strong\u003esoldiers in the water, so that, they can kill all soldiers. For security reasons, the snipers should be as far from the bank as possible. For any sniper in position \u003cstrong\u003e\u003cem\u003e(x\u003csub\u003ei\u003c/sub\u003e,y\u003csub\u003ei\u003c/sub\u003e)\u003c/em\u003e\u003c/strong\u003e, the distance from the bank is \u003cstrong\u003e\u003cem\u003e|y\u003csub\u003ei\u003c/sub\u003e-k|\u003c/em\u003e\u003c/strong\u003e. If, for all snipers, the minimum of them is \u003cstrong\u003e\u003cem\u003eM\u003dmin{|y\u003csub\u003ei\u003c/sub\u003e-k|}\u003c/em\u003e\u003c/strong\u003e, you have to maximize \u003cstrong\u003e\u003cem\u003eM\u003c/em\u003e\u003c/strong\u003e.\u003c/p\u003e\r\n\t\u003cp\u003e\r\n\t\tBoth the soldiers and snipers are really superstitious. They will stay only in integer coordinates.\u003c/p\u003e\r\n\u003c/div\u003e"}},{"title":"Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFirst line contains an integer \u003cstrong\u003e\u003cem\u003eT(\u003c/em\u003e1\u0026le;\u003cem\u003eT\u003c/em\u003e\u0026le;100)\u003c/strong\u003e, the number of test cases.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThis is followed by \u003cstrong\u003e\u003cem\u003eT\u003c/em\u003e\u003c/strong\u003e test cases. Each test case starts with four integers, \u003cstrong\u003e\u003cem\u003ek(\u003c/em\u003e-10\u003csup\u003e8\u003c/sup\u003e\u003cem\u003e\u0026le;k\u0026le;\u003c/em\u003e10\u003csup\u003e8\u003c/sup\u003e\u003cem\u003e)\u003c/em\u003e\u003c/strong\u003e,\u0026nbsp; \u003cstrong\u003e\u003cem\u003eN(\u003c/em\u003e1\u0026le;\u003cem\u003eN\u003c/em\u003e\u0026le;10000\u003cem\u003e)\u003c/em\u003e\u003c/strong\u003e, \u003cstrong\u003e\u003cem\u003eS(\u003c/em\u003e1\u0026le;\u003cem\u003eS\u003c/em\u003e\u0026le;10000\u003cem\u003e) \u003c/em\u003e\u003c/strong\u003eand \u003cstrong\u003e\u003cem\u003eD(\u003c/em\u003e1\u0026le;\u003cem\u003eD\u003c/em\u003e\u0026le;10\u003csup\u003e9\u003c/sup\u003e\u003cem\u003e)\u003c/em\u003e\u003c/strong\u003e, the position of the bank, number of guards and number of snipers, and the range of the snipers.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThis is followed by \u003cstrong\u003e\u003cem\u003eN\u003c/em\u003e\u003c/strong\u003e lines, each containing a pair of integers \u003cstrong\u003e\u003cem\u003e(x\u003csub\u003ei\u003c/sub\u003e, y\u003csub\u003ei\u003c/sub\u003e)\u003c/em\u003e\u003c/strong\u003e the position of \u003cstrong\u003e\u003cem\u003ei\u003c/em\u003e\u003c/strong\u003e\u003csup\u003eth\u003c/sup\u003e guard \u003cstrong\u003e(-10\u003csup\u003e8 \u003c/sup\u003e\u0026le; \u003cem\u003ex\u003csub\u003ei\u003c/sub\u003e\u003c/em\u003e \u0026le; 10\u003csup\u003e8\u003c/sup\u003e, \u003cem\u003ek\u003c/em\u003e \u0026lt; \u003cem\u003ey\u003csub\u003ei\u003c/sub\u003e\u003c/em\u003e \u0026le; 10\u003csup\u003e8\u003c/sup\u003e)\u003c/strong\u003e.\u003c/p\u003e\r\n\u003cp\u003e\r\n\tThere is a blank line before each test case.\u003c/p\u003e"}},{"title":"Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tFor each test case, output the case number followed by an integer, \u003cstrong\u003e\u003cem\u003eM\u003c/em\u003e\u003c/strong\u003e, which is defined in the statement. If the snipers can\u0026rsquo;t kill all guards, output: \u0026ldquo;IMPOSSIBLE\u0026rdquo;.\u003c/p\u003e"}},{"title":"Sample Input","value":{"format":"HTML","content":"\u003cp\u003e\r\n\t2\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\t0 3 2 4\u003cbr /\u003e\r\n\t1 1\u003cbr /\u003e\r\n\t3 2\u003cbr /\u003e\r\n\t9 1\u003cbr /\u003e\r\n\t\u003cbr /\u003e\r\n\t0 3 1 4\u003cbr /\u003e\r\n\t1 1\u003cbr /\u003e\r\n\t3 2\u003cbr /\u003e\r\n\t9 1\u003c/p\u003e"}},{"title":"Sample Output","value":{"format":"HTML","content":"\u003cp\u003e\r\n\tCase 1: 2\u003cbr /\u003e\r\n\tCase 2: IMPOSSIBLE\u003c/p\u003e"}}]}