{"trustable":true,"sections":[{"title":"","value":{"format":"MD","content":"\u003ch3\u003e Read problems statements in \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME45/mandarin/OVERPNT\r\n.pdf\"\u003eMandarin Chinese\u003c/a\u003e, \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME45/russian/OVERPNT\r\n.pdf\"\u003eRussian\u003c/a\u003e and \u003ca target\u003d\"_blank\" href\u003d\"https://www.codechef.com/download/translated/LTIME45/vietnamese/OVERPNT\r\n.pdf\"\u003eVietnamese\u003c/a\u003e as well.\u003c/h3\u003e\r\n\r\n\u003cp\u003eIn competitive programming, one of the common mistakes is using a variable type that stores too few bits, which leads to overflows and underflows.\r\nWe will focus on the \"unsigned int\" type, which makes all calculations modulo 2\u003csup\u003e32\u003c/sup\u003e, always giving a non-negative result between 0 and 2\u003csup\u003e32\u003c/sup\u003e - 1, inclusive.\r\nSample calculations on type \"unsigned int\" are:\u003c/p\u003e\r\n\r\n\u003cpre\u003e7 - 5 \u003d 2, 5 - 7 \u003d 4294967294, 5 * 1,000,000,000 \u003d 705032704\u003c/pre\u003e\r\n\u003cbr\u003e\r\n\u003cp\u003eLimak wants to become a great coder.\r\nRight now he learns the computional geometry.\r\nHe already knows that three points (ax, ay), (bx, by), (cx, cy) are collinear if and only if:\u003c/p\u003e\r\n\r\n\u003cp\u003e(bx - ax) * (cy - ay) \u003d (by - ay) * (cx - ax)\u003c/p\u003e\r\n\r\n\u003cp\u003eWithout thinking which type to use, Limak wrote the following C++ function:\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n\u003ccode\u003e\r\n\ttypedef unsigned int UI;\r\n\tbool areCollinear(UI ax, UI ay, UI bx, UI by, UI cx, UI cy) {\r\n\t\treturn (bx - ax) * (cy - ay) \u003d\u003d (by - ay) * (cx - ax);\r\n\t}\r\n\u003c/code\u003e\r\n\u003c/pre\u003e\r\n\u003cbr\u003e\r\n\r\n\u003cp\u003eIf you are more familiar with Python, you can assume that he wrote:\u003c/p\u003e\r\n\r\n\u003cpre\u003e\r\n\u003ccode\u003e\r\n M \u003d 2 ** 32\r\n def subtract(a, b):\r\n ans \u003d a - b\r\n if ans \u003c 0:\r\n ans +\u003d M\r\n return ans\r\n def mul(a, b):\r\n return a * b % M\r\n def areCollinear(ax, ay, bx, by, cx, cy):\r\n return mul(sub(bx, ax), sub(cy, ay)) \u003d\u003d mul(sub(by, ay), sub(cx, ax))\r\n\u003c/pre\u003e\r\n\u003c/code\u003e\r\n\u003cbr\u003e\r\n\r\n\u003cp\u003eTo show Limak how important it is to watch for overflows, you must find any set of \u003cb\u003eN\u003c/b\u003e distinct points that:\u003c/b\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eAny three distinct points in any order would be treated as collinear by Limak\u0027s function.\u003c/li\u003e\r\n\u003cli\u003eNone three points are collinear (what implies that points are distinct).\u003c/li\u003e\r\n\u003cli\u003eCoordinates are non-negative integers not exceeding 10\u003csup\u003e6\u003c/sup\u003e.\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003cbr\u003e\r\n\r\n\u003cp\u003eIf there are many solutions (valid sets of points), you can print any of them.\r\nThere exists at least one solution for every \u003cb\u003eN\u003c/b\u003e allowed by the constraints.\u003c/p\u003e\r\n\r\n\r\n\r\n\r\n\r\n\r\n\r\n\u003ch3\u003eInput\u003c/h3\u003e\r\n\r\n\u003cp\u003eThe only line of the input contains an integer \u003cb\u003eN\u003c/b\u003e denoting the required number of points.\u003c/p\u003e\r\n\r\n\u003ch3\u003eOutput\u003c/h3\u003e\r\n\r\n\u003cp\u003ePrint \u003cb\u003eN\u003c/b\u003e lines.\r\nThe i-th of them should contain two space-separated integers x\u003csub\u003ei\u003c/sub\u003e and y\u003csub\u003ei\u003c/sub\u003e, denoting coordinates of the i-th point.\r\nIf there are many solutions, you can print any of them.\u003c/p\u003e\r\n\r\n\u003cp\u003eRemember that one of requirements is 0 ≤ x\u003csub\u003ei\u003c/sub\u003e, y\u003csub\u003ei\u003c/sub\u003e ≤ 10\u003csup\u003e6\u003c/sup\u003e.\u003c/p\u003e\r\n\r\n\r\n\r\n\u003ch3\u003eConstraints\u003c/h3\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003e3 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 10\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\u003ch3\u003eSubtasks\u003c/h3\u003e\r\n\r\n\u003cul\u003e\r\n\u003cli\u003eSubtask #1 (50 points) 3 ≤ \u003cb\u003eN\u003c/b\u003e ≤ 5\u003c/li\u003e\r\n\u003cli\u003eSubtask #2 (50 points) original constraints\u003c/li\u003e\r\n\u003c/ul\u003e\r\n\r\n\r\n\r\n\u003ch3\u003eExample\u003c/h3\u003e\r\n\r\n\u003cpre\u003e\u003cb\u003eInput1:\u003c/b\u003e\r\n3\r\n\r\n\u003cb\u003eOutput2:\u003c/b\u003e\r\n106732 139820\r\n210379 490375\r\n42 483426\r\n\r\n\u003cb\u003eInput2:\u003c/b\u003e\r\n4\r\n\r\n\u003cb\u003eOutput2:\u003c/b\u003e\r\n580981 431795\r\n914958 554338\r\n518360 23016\r\n441824 483616\u003c/pre\u003e\r\n\r\n\r\n\r\n\r\n\u003ch3\u003eExplanation\u003c/h3\u003e\r\n\r\n\u003cp\u003e\u003cb\u003eTest case 1.\u003c/b\u003e The provided function areCollinear() should return True for the found three points given in any order (there are 3! \u003d 6 possible orders of 3 points).\r\nLet\u0027s analyze the evaluation of areCollinear(42, 483426, 106732, 139820, 210379, 490375):\u003c/p\u003e\r\n\r\n\u003cp\u003eWithout any overflow errors, the calculations would be:\u003c/p\u003e\r\n\r\n\u003cp\u003e (bx - ax) * (cy - ay) \u003d (106732 - 42) * (490375 - 483426) \u003d 741388810\u003c/p\u003e\r\n\r\n\u003cp\u003e(by - ay) * (cx - ax) \u003d (139820 - 483426) * (210379 - 42) \u003d -72273055222\u003c/p\u003e\r\n\r\n\u003cp\u003eAnd indeed numbers 741388810 and -72273055222 are equal modulo 2\u003csup\u003e32\u003c/sup\u003e. Hence areCollinear would think that they are collinear.\u003c/p\u003e"}}]}