{"trustable":true,"prependHtml":"\u003cscript\u003e\n window.katexOptions \u003d {\n delimiters: [\n {left: \u0027\\\\(\u0027, right: \u0027\\\\)\u0027, display: false},\n ]\n };\n\u003c/script\u003e\n","sections":[{"title":"","value":{"format":"HTML","content":"\u003cp\u003ePUBG is a multiplayer online battle royale video game. In the game, up to one hundred players parachute onto an island and scavenge for weapons and equipment to kill others while avoiding getting killed themselves. Airdrop in this game is a key element, as airdrops often carry with them strong weapons or numerous supplies, helping players to survive.\u003c/p\u003e\n\n\u003ccenter\u003e\u003cimg src\u003d\"CDN_BASE_URL/1805df5768875b9ab32fba7555a949ea?v\u003d1715420084\" width\u003d\"300px\"\u003e\u003cbr\u003e\u003ci\u003eAirdrop in the game(?)\u003c/i\u003e\u003c/center\u003e\n\n\u003cp\u003eConsider the battle field of the game to be a two-dimensional plane. An airdrop has just landed at point $(x_0, y_0)$ (both $x_0$ and $y_0$ are integers), and all the $n$ players on the battle field, where $(x_i, y_i)$ (both $x_i$ and $y_i$ are integers) indicates the initial position of the $i$-th player, start moving towards the airdrop with the following pattern:\n\n\u003c/p\u003e\u003cul\u003e\n \u003cli\u003eIf the position of a living player at the beginning of this time unit is not equal to $(x_0, y_0)$, he will begin his next move.\n \u003cul\u003e\n \u003cli\u003eLet\u0027s say he is currently at point $(x, y)$. For his next move, he will consider four points $(x, y - 1)$, $(x, y + 1)$, $(x - 1, y)$ and $(x + 1, y)$.\u003c/li\u003e\n \u003cli\u003eHe will select one of the four points whose Manhattan distance to the airdrop $(x_0, y_0)$ is the smallest to be the destination of his next move. Recall that the Manhattan distance between two points $(x_a, y_a)$ and $(x_b, y_b)$ is defined as $|x_a - x_b| + |y_a - y_b|$.\u003c/li\u003e\n \u003cli\u003eIf two or more points whose Manhattan distance to the airdrop is the same, he will use the following priority rule to break the tie: $(x, y - 1)$ has the highest priority to be selected, $(x, y + 1)$ has the second highest priority, $(x - 1, y)$ has the third highest priority, and $(x + 1, y)$ has the lowest priority.\u003c/li\u003e\n \u003cli\u003eAt the end of this time unit, he arrives at his destination.\u003c/li\u003e\n \u003c/ul\u003e\n \u003c/li\u003e\n \u003cli\u003eIf the position of a living player at the beginning of this time unit is equal to $(x_0, y_0)$, he will continue to fatten his backpack with the supplies in the airdrop and stays at $(x_0, y_0)$.\u003c/li\u003e\n\u003c/ul\u003e\n\n\u003cp\u003eBut the battle is tough and it\u0027s almost impossible for all the players to arrive at the airdrop safely. If two or more players meet at point $(x\u0027, y\u0027)$ other than $(x_0, y_0)$, where both $x\u0027$ and $y\u0027$ are integers, they will fight and kill each other and none of them survive.\u003c/p\u003e\n\n\u003cp\u003eBaoBao is a big fan of the game and is interested in the number of players successfully arriving at the position of the airdrop, but he doesn\u0027t know the value of $x_0$. Given the value of $y_0$ and the initial position of each player, please help BaoBao calculate the minimum and maximum possible number of players successfully arriving at the position of the airdrop for all $x_0 \\in \\mathbb{Z}$, where $\\mathbb{Z}$ is the set of all integers (note that $x_0$ can be positive, zero or negative).\u003c/p\u003e\n\n\u003ch4\u003eInput\u003c/h4\u003e\n\u003cp\u003eThere are multiple test cases. The first line of the input contains an integer $T$, indicating the number of test cases. For each test case:\u003c/p\u003e\n\n\u003cp\u003eThe first line contains two integers $n$ and $y_0$ ($1 \\le n \\le 10^5$, $1 \\le y_0 \\le 10^5$), indicating the number of players and the $y$ value of the airdrop.\u003c/p\u003e\n\n\u003cp\u003eFor the following $n$ lines, the $i$-th line contains two integers $x_i$ and $y_i$ ($1 \\le x_i, y_i \\le 10^5$), indicating the initial position of the $i$-th player.\u003c/p\u003e\n\n\u003cp\u003eIt\u0027s guaranteed that the sum of $n$ in all test cases will not exceed $10^6$, and in each test case no two players share the same initial position.\u003c/p\u003e\n\n\u003ch4\u003eOutput\u003c/h4\u003e\n\u003cp\u003eFor each test case output one line containing two integers $p_\\text{min}$ and $p_\\text{max}$ separated by one space. $p_\\text{min}$ indicates the minimum possible number of players successfully arriving at the position of the airdrop, while $p_\\text{max}$ indicates the maximum possible number.\u003c/p\u003e\n\n\u003ch4\u003eSample\u003c/h4\u003e\n\u003ctable class\u003d\"vjudge_sample\"\u003e\n\u003cthead\u003e\n \u003ctr\u003e\n \u003cth\u003eInput\u003c/th\u003e\n \u003cth\u003eOutput\u003c/th\u003e\n \u003c/tr\u003e\n\u003c/thead\u003e\n\u003ctbody\u003e\n \u003ctr\u003e\n \u003ctd\u003e\u003cpre\u003e3\n3 2\n1 2\n2 1\n3 5\n3 3\n2 1\n2 5\n4 3\n2 3\n1 3\n4 3\n\u003c/pre\u003e\u003c/td\u003e\n \u003ctd\u003e\u003cpre\u003e1 3\n0 3\n2 2\n\u003c/pre\u003e\u003c/td\u003e\n \u003c/tr\u003e\n\u003c/tbody\u003e\n\u003c/table\u003e\n\n\n\u003ch4\u003eHint\u003c/h4\u003e\n\u003cp\u003eWe now explain the first sample test case.\u003c/p\u003e\n\n\u003cp\u003eTo obtain the answer of $p_\\text{min} \u003d 1$, one should consider $x_0 \u003d 3$. The following table shows the position of each player at the end of each time unit when $x_0 \u003d 3$.\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003eTime\u003c/th\u003e\u003cth\u003ePlayer 1\u003c/th\u003e\u003cth\u003ePlayer 2\u003c/th\u003e\u003cth\u003ePlayer 3\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e(1, 2)\u003c/td\u003e\u003ctd\u003e(2, 1)\u003c/td\u003e\u003ctd\u003e(3, 5)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 4)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003eeliminated\u003c/td\u003e\u003ctd\u003eeliminated\u003c/td\u003e\u003ctd\u003e(3, 3)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003eeliminated\u003c/td\u003e\u003ctd\u003eeliminated\u003c/td\u003e\u003ctd\u003e(3, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cp\u003eTo obtain the answer of $p_\\text{max} \u003d 3$, one should consider $x_0 \u003d 2$. The following table shows the position of each player at the end of each time unit when $x_0 \u003d 2$.\u003c/p\u003e\n\n\u003ctable id\u003d\"problem-table\" style\u003d\"border-collapse: collapse; text-align: center;\" align\u003d\"center\"\u003e\n \u003cthead\u003e\n \u003ctr\u003e\u003cth\u003eTime\u003c/th\u003e\u003cth\u003ePlayer 1\u003c/th\u003e\u003cth\u003ePlayer 2\u003c/th\u003e\u003cth\u003ePlayer 3\u003c/th\u003e\u003c/tr\u003e\n \u003c/thead\u003e\n \u003ctbody\u003e\n \u003ctr\u003e\u003ctd\u003e0\u003c/td\u003e\u003ctd\u003e(1, 2)\u003c/td\u003e\u003ctd\u003e(2, 1)\u003c/td\u003e\u003ctd\u003e(3, 5)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e1\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 4)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e2\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 3)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e3\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(3, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003ctr\u003e\u003ctd\u003e4\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003ctd\u003e(2, 2)\u003c/td\u003e\u003c/tr\u003e\n \u003c/tbody\u003e\n\u003c/table\u003e\n\n\u003cstyle type\u003d\"text/css\"\u003e\n#problem-table \u003e thead \u003e tr \u003e th, #problem-table \u003e tbody \u003e tr \u003e td\n{\n padding: 3px 5px;\n border: 1px solid black;\n}\n\u003c/style\u003e\n"}}]}