{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"### Read problems statements in [Mandarin Chinese](https://www.codechef.com/download/translated/COOK128/mandarin/SANITIZE.pdf), [Russian](https://www.codechef.com/download/translated/COOK128/russian/SANITIZE.pdf), and [Bengali](https://www.codechef.com/download/translated/COOK128/bengali/SANITIZE.pdf) as well.\r\n\r\n**This is an Interactive Problem.**\r\n\r\nChef found a dirty-looking square plate in his kitchen. Obviously, it is full of germs. Specifically, there are $N$ germs lying in the whole plate. The plate has dimensions $M\\times M$ and can be imagined as a 2-dimensional square space bounded by the lines $X\u003d0$, $Y\u003d0$, $X\u003dM$ and $Y\u003dM$. Chef knows that each germ lies at a point with integer coordinates within this plate and no two germs lie at the same point. But he doesn\u0027t know the exact location of the germs. Each germ has a unique integer ID between $1$ and $N$.\r\n\r\nChef wants to sanitize this plate, i.e., make it germ-free. But because of low budget, he can afford only $N$ ml of sanitizer. Each germ requires $1$ ml of sanitizer to be killed. So, he needs to be careful not to waste even a single drop of it!\r\n\r\nLuckily, he also has a germ sensor with him which works as follows $-$\r\n\r\nIt send a laser beam of light along a straight line $A\\cdot x+B\\cdot y\u003dC$ and returns two things:\r\n- The ID of the germ having the shortest perpendicular distance to this line. If there are multiple such germs, any of them may be chosen.\r\n- The distance of this germ from the line. \r\n\r\nBut again, because of low budget, he is using a cheap model which can be used at most $2N$ times.\r\n\r\nHelp him kill all the germs. You can use the sensor or apply sanitizer in an arbitrary order. Note that the sensor does not sense killed germs.\r\n\r\n### Interaction:\r\n- The first line of input contains an integer $T$ - the number of test cases.\r\n- For each test case, first read a single line containing two integers $N$ and $M$ - the number of germs and the size of the plate.\r\n- Then you may ask queries in the following format $-$\r\n - To use the sensor, print a single line containing $4$ space separated integers $1$, $A$, $B$, $C$ satisfying the constraints $-128\\leq A,B\\leq 128$ and $-10^9\\leq C\\leq 10^9$ where $A\\cdot x+B\\cdot y\u003dC$ is the line you wish to query. If you ask an invalid query or exceed $2N$ queries of this type, the grader returns $-1$. Otherwise, the grader returns two space separated integers $U$ and $D$, where $U$ is the ID of the germ closest to this line and $D$ is the perpendicular distance of the germ from the line multiplied by $\\sqrt{A^2+B^2}$. It can be shown that $D$ will always be an integer under the given constraints and scaling factor.\r\n - To apply $1$ ml of sanitizer at the point $(X, Y)$, print a single line containing $3$ space separated integers $2$, $X$, $Y$ satisfying the constraints $0\\leq X, Y\\leq M$. If there is any germ present at this point, it will be killed. Then the grader returns a single integer $V$. If you ask an invalid query or exceed $N$ queries of this type, $V\u003d-1$. Otherwise, if all the germs are killed after this query then $V\u003d1$ else $V\u003d0$. As soon as you receive $1$, the test case ends and you should continue solving the remaining test cases.\r\n- If you receive $-1$ from the grader, terminate the program immediately to receive the Wrong Answer verdict otherwise you may receive any verdict.\r\n\r\n**Don\u0027t forget to flush your output after printing each line!**\r\n\r\n### Constraints: \r\n- $1\\leq T\\leq 1024$\r\n- $1\\leq M\\leq 10^9$\r\n- $1\\leq N\\leq 4096$\r\n- All germs lie at points with integer coordinates within the plate.\r\n- No two germs lie at the same point.\r\n- No two germs have the same ID.\r\n- ID of each germ lies between $1$ and $N$ inclusive.\r\n- The sum of $N$ over all test cases does not exceed $4096$.\r\n\r\n### Example:\r\n```\r\nYou Grader\r\n\r\n 1\r\n 2 10\r\n1 1 1 2\r\n 1 4\r\n1 -1 2 -5\r\n 2 3\r\n2 1 5\r\n 0\r\n1 3 0 1\r\n 2 23\r\n2 8 0\r\n 1\r\n```\r\n\r\n### Explanation:\r\nThere are $2$ germs lying on a $10\\times 10$ plate. The germs lie on the points $(1, 5)$ and $(8, 0)$ and have IDs $1$ and $2$, respectively.\r\n\r\nThe first query is a sensor query with the line $x+y\u003d2$. The perpendicular distance of the first germ from this line is $2\\sqrt{2}$ units and the distance of the second germ is $3\\sqrt{2}$ units. Since the first germ is closer, $U\u003d1$ and $D\u003d2\\sqrt{2}\\times \\sqrt{1^2+1^2}\u003d4$ is returned.\r\n\r\nThe second query is a sensor query with the line $-x+2y\u003d-5$. The perpendicular distance of the first germ from this line is $\\frac{14\\sqrt{5}}{5}$ units and the distance of the second germ is $\\frac{3\\sqrt{5}}{5}$ units. Since the second germ is closer, $U\u003d2$ and $D\u003d\\frac{3\\sqrt{5}}{5}\\times \\sqrt{(-1)^2+2^2}\u003d3$ is returned.\r\n\r\nThe third query is applying sanitizer at the point $(1,5)$. The first germ lies at this point and is killed. Since, there is still $1$ germ alive, $V\u003d0$ is returned.\r\n\r\nThe fourth query is a sensor query with the line $3x\u003d1$. The only germ alive is the second germ which is at a distance of $\\frac{23}{3}$ units from this line. So, $U\u003d2$ and $D\u003d\\frac{23}{3}\\times \\sqrt{3^2+0^2}\u003d23$ is returned.\r\n\r\nThe fifth query is applying sanitizer at the point $(8,0)$. The second germ lies at this point and is killed. Since, all germs are killed, $V\u003d1$ is returned."}}]}